【栈和队列】算法题 ---- 力扣（一）https://developer.aliyun.com/article/1621386
三、用栈实现队列
上一个题让我们用队列来实现栈，这个用两个栈来实现队列。
定义两个栈
思路：
往PushST中插入数据，再将数据导入到PopST中，出栈即可；
入队列：往PushST中插入数据
出队列：判断栈PopST是否为空？如果PopST栈为空，就将栈PushST中数据导入到栈PopST中去，再让栈PopST出栈操作；如果不为空，直接让栈PopST出栈操作即可。
取队头数据：和出队列操作一样，只是不需要出栈操作，只取数据
分析：
假设依次插入了1，2，3三个数据，现在出栈一次，再插入一个数据4，最后取队头数据，依次出栈。
出栈一次，PopST为空，就将PushST中数据导入到PopST中去。
依次导入
出栈；
再插入数据4
取队头数据：
最后依次出队列
现在，PopST栈为空，就要先将PushST中数据先导入到PopST中。
再出队列
力扣题代码如下：
typedef int SType; typedef struct Stack { SType* arr; int size; //栈顶 int num; //空间大小 }Stack; //初始化 void STInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->size = ps->num = 0; } //判断栈是否为空 bool STEmpty(Stack* ps) { assert(ps); return ps->size == 0; } //入栈 void STPush(Stack* ps, SType x) { assert(ps); //判断空间大小是否足够 if (ps->num <= ps->size) { int newnum = (ps->num == 0) ? 4 : ps->num * 2; SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack)); if (tmp == NULL) { perror("realloc filed"); exit(1); } ps->arr = tmp; ps->num = newnum; } ps->arr[ps->size++] = x; } //出栈 void STPop(Stack* ps) { assert(ps); //不能传NULL assert(!STEmpty(ps)); //栈不能为空 ps->size--; } //取栈顶数据 SType STtop(Stack* ps) { return ps->arr[ps->size - 1]; } //获取栈中数据个数 int STSize(Stack* ps) { assert(ps); return ps->size; } //栈的销毁 void STDesTroy(Stack* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->size = ps->num = 0; } typedef struct { Stack s1; Stack s2; } MyQueue; //初始化 MyQueue* myQueueCreate() { MyQueue* Queue=(MyQueue*)malloc(sizeof(MyQueue)); STInit(&Queue->s1); STInit(&Queue->s2); return Queue; } //插入数据 void myQueuePush(MyQueue* obj, int x) { assert(obj); STPush(&obj->s1, x); } int myQueuePop(MyQueue* obj) { assert(obj); if(STEmpty(&obj->s2)) { //把s1中数据导入到s2 while(!STEmpty(&obj->s1)) { STPush(&obj->s2,STtop(&obj->s1)); STPop(&obj->s1); } } int ret=STtop(&obj->s2); STPop(&obj->s2); return ret; } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->s2)) { //把s1中数据导入到s2 while(!STEmpty(&obj->s1)) { STPush(&obj->s2,STtop(&obj->s1)); STPop(&obj->s1); } } return STtop(&obj->s2); } bool myQueueEmpty(MyQueue* obj) { return (STEmpty(&obj->s1)) && (STEmpty(&obj->s2)); } void myQueueFree(MyQueue* obj) { if(obj) free(obj); obj=NULL; }
四、设计循环队列
设计循环队列，这里使用数组来设计
这里会设计到的一些问题：
插入数据，如何判断空间是否满了？
这里多申请一个空间，便于判断空间是否满了
删除数据，如何去删？
这里，删除front指向的数据，就是队头数据
详细代码如下：
typedef struct { int* arr; int front; int rear; int num; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); pq->arr = malloc((k + 1) * sizeof(int)); pq->front = pq->rear = 0; pq->num = k; return pq; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return (obj->rear == obj->front); } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1) % (obj->num + 1) == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) // 队列满了 { return false; } // 插入数据 obj->arr[obj->rear++] = value; obj->rear %= (obj->num + 1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return false; } obj->front++; obj->front %= (obj->num + 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; int ret=obj->rear-1; if(obj->rear==0) { ret=obj->num; } return obj->arr[ret]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); free(obj); obj = NULL; }
感谢各位大佬支持并指出问题，
如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！
