【排排站：探索数据结构中的队列奇象】（上）:https://developer.aliyun.com/article/1424895
四、队列面试题
1. 用队列实现栈。OJ链接
- 栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。
- 队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。
思路：
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中 queue1用于存储栈内的元素，queue2作为入栈操作的辅助队列。
入栈操作时，首先将元素入队到 queue2 ，然后将 queue1的全部元素依次出队并入队到 queue2此时 queue2的前端的元素即为新入栈的元素，再将 queue1和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保 queue1的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1的前端元素并返回即可（不移除元素）。
由于 queue1用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1是否为空即可。
typedef struct { int* stk; int stkSize; int stkCapacity; } Stack; Stack* stackCreate(int cpacity) { Stack* ret = malloc(sizeof(Stack)); ret->stk = malloc(sizeof(int) * cpacity); ret->stkSize = 0; ret->stkCapacity = cpacity; return ret; } void stackPush(Stack* obj, int x) { obj->stk[obj->stkSize++] = x; } void stackPop(Stack* obj) { obj->stkSize--; } int stackTop(Stack* obj) { return obj->stk[obj->stkSize - 1]; } bool stackEmpty(Stack* obj) { return obj->stkSize == 0; } void stackFree(Stack* obj) { free(obj->stk); } typedef struct { Stack* inStack; Stack* outStack; } MyQueue; MyQueue* myQueueCreate() { MyQueue* ret = malloc(sizeof(MyQueue)); ret->inStack = stackCreate(100); ret->outStack = stackCreate(100); return ret; } void in2out(MyQueue* obj) { while (!stackEmpty(obj->inStack)) { stackPush(obj->outStack, stackTop(obj->inStack)); stackPop(obj->inStack); } } void myQueuePush(MyQueue* obj, int x) { stackPush(obj->inStack, x); } int myQueuePop(MyQueue* obj) { if (stackEmpty(obj->outStack)) { in2out(obj); } int x = stackTop(obj->outStack); stackPop(obj->outStack); return x; } int myQueuePeek(MyQueue* obj) { if (stackEmpty(obj->outStack)) { in2out(obj); } return stackTop(obj->outStack); } bool myQueueEmpty(MyQueue* obj) { return stackEmpty(obj->inStack) && stackEmpty(obj->outStack); } void myQueueFree(MyQueue* obj) { stackFree(obj->inStack); stackFree(obj->outStack); }
2. 用栈实现队列。OJ链接
将一个栈当作输入栈，用于压入 push\ 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
typedef struct { int* stk; int stkSize; int stkCapacity; } Stack; Stack* stackCreate(int cpacity) { Stack* ret = malloc(sizeof(Stack)); ret->stk = malloc(sizeof(int) * cpacity); ret->stkSize = 0; ret->stkCapacity = cpacity; return ret; } void stackPush(Stack* obj, int x) { obj->stk[obj->stkSize++] = x; } void stackPop(Stack* obj) { obj->stkSize--; } int stackTop(Stack* obj) { return obj->stk[obj->stkSize - 1]; } bool stackEmpty(Stack* obj) { return obj->stkSize == 0; } void stackFree(Stack* obj) { free(obj->stk); } typedef struct { Stack* inStack; Stack* outStack; } MyQueue; MyQueue* myQueueCreate() { MyQueue* ret = malloc(sizeof(MyQueue)); ret->inStack = stackCreate(100); ret->outStack = stackCreate(100); return ret; } void in2out(MyQueue* obj) { while (!stackEmpty(obj->inStack)) { stackPush(obj->outStack, stackTop(obj->inStack)); stackPop(obj->inStack); } } void myQueuePush(MyQueue* obj, int x) { stackPush(obj->inStack, x); } int myQueuePop(MyQueue* obj) { if (stackEmpty(obj->outStack)) { in2out(obj); } int x = stackTop(obj->outStack); stackPop(obj->outStack); return x; } int myQueuePeek(MyQueue* obj) { if (stackEmpty(obj->outStack)) { in2out(obj); } return stackTop(obj->outStack); } bool myQueueEmpty(MyQueue* obj) { return stackEmpty(obj->inStack) && stackEmpty(obj->outStack); } void myQueueFree(MyQueue* obj) { stackFree(obj->inStack); stackFree(obj->outStack); }
3. 设计循环队列。OJ链接
顺序队列的假溢出问题
解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。
- 初始时：Q->front = Q->rear=0。
- 队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
- 队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
- 队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。
出队入队时，指针都按照顺时针方向前进1，如下图所示：
那么，循环队列队空和队满的判断条件是什么呢？
显然，队空的条件是 Q->front == Q->rear 。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图( d1 ）所示，此时可以看出队满时也有 Q ->front == Q -> rear 。为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图 ( d2 ）所示。
- 队满条件： (Q->rear + 1)%Maxsize == Q->front
- 队空条件仍： Q->front == Q->rear
- 队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear
（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。
typedef struct { int front; int rear; int capacity; int *elements; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); obj->capacity = k + 1; obj->rear = obj->front = 0; obj->elements = (int *)malloc(sizeof(int) * obj->capacity); return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if ((obj->rear + 1) % obj->capacity == obj->front) { return false; } obj->elements[obj->rear] = value; obj->rear = (obj->rear + 1) % obj->capacity; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->rear == obj->front) { return false; } obj->front = (obj->front + 1) % obj->capacity; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->rear == obj->front) { return -1; } return obj->elements[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->rear == obj->front) { return -1; } return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->rear == obj->front; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1) % obj->capacity == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->elements); free(obj); }
