三、用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
连接：https://leetcode-cn.com/problems/implement-queue-using-stacks
1.题干分析
用两个栈来才实现队列，一个栈先入数据，另一个栈用来存第一个栈的数据，如：第一个栈如1,2,3,4，第二个栈从第一个栈的栈顶拿数据入，即为4,3,2,1；，这时候在取第二个栈的栈顶数据，就符合原来1,2,3,4先进先出的顺序，即队列的特点
2.动图解析
3.代码实现
typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity; }ST; //栈的初始化 void StackInit(ST* ps); //栈的销毁 void StackDestroy(ST* ps); //栈的栈顶插入 void StackPush(ST* ps, STDataType x); //栈的删除 void StackPop(ST* ps); //取栈顶的数据 STDataType StackTop(ST* ps); //栈的元素个数 int StackSize(ST* ps); //判断栈是不是空 bool StackEmpty(ST* ps); //栈的初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //栈的销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //栈的栈顶插入 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } //栈的删除 void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } //取栈顶的数据 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } //栈的元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是不是空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } typedef struct { ST pushST; ST popST; } MyQueue; //队列的创建 MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushST); StackInit(&q->popST); return q; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); } //取队头数据 int myQueuePop(MyQueue* obj) { //如果popST中没有数据，将pushST中的数据导过去 //popST中的数据就符合先进先出的顺序了 if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } //返回队列开头的元素 int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); } //判断队列是否为空 bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); } //队列销毁 void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj); }
四、设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
链接：https://leetcode-cn.com/problems/design-circular-queue
1.题干分析
什么是循环队列？循环队列与普通队列的差异是什么？
普通队列我们可以采用链表和顺序表的方式进行实现，之前的博客中说到，顺序表实现队列，由于数据在出队列的时候需要每次挪动数据代价比较大；因而我们选择了链表来实现；
如果非要采用顺序存储呢？建议采用循环队列的形式；
假设：初始化创建空队时，令head（头指针）和tail（尾指针）为0；，每当插入新的数据时，尾指针tail增1；每当删除队列头数据时，头指针head减1；在非空队列中，head始终指向队列的头，tail始终指向队列的尾的下一个位置；如下图所示;
循环队列，就是头尾相接 ；如果是链表，实现循环，我们可以想到一个循环链表，尾结点不指向空，指向头结点就可以了；那么数组怎么实现头尾相接呢？
重点：
循环队列，无论使用数组实现还是链表实现，都要多开一个空间，也就意味着，要是存K个数据的循环队列，要开k+1个空间，否则无法判空和判满；
开辟k个空间：
满和空条件都是一样的，无法判端满；（数组也是如此）
开辟k+1个空间：
2. 代码实现
①数组实现
typedef struct { int* a; int k; int front; int tail; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->a = (int*)malloc(sizeof(int)*(k+1));//开辟k+1个空间 cq->front = cq->tail = 0; cq->k = k; return cq; } //入数据 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->tail] = value; ++obj->tail; obj->tail %= (obj->k+1); return true; } //出数据 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; ++obj->front; obj->front%=(obj->k+1); return true; } //取队头 int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } //取队尾 int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; if(obj->tail ==0) return obj->a[obj->k]; else return obj->a[obj->tail-1]; /* int i = (obj->tail + obj->k) % (obj->k+1); return obj->a[i]; */ } //判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail; } //判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1) % (obj->k+1) == obj->front; } //销毁 void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
② 链表实现
相比数组，链表不可以直接malloc k+1个节点；我们需要通过循环去开辟；
typedef int CirQDataType; typedef struct CirQNode { CirQDataType Data; struct CirQNode* next; }CirQNode; typedef struct { int k; CirQNode* head; CirQNode* tail; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); //循环队列的初始化 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); CirQNode* cur = (CirQNode*)malloc(sizeof(CirQNode)); cq->k = k; cq->head = cq->tail = cur; //创建好一个结点后，在后面循环创建k个结点 while(k--) { CirQNode* newnode = (CirQNode*)malloc(sizeof(CirQNode)); CirQNode* NewTail = cq->tail;//记录新的尾 NewTail->next = newnode;//把申请的结点链到新的尾上 newnode->next = cq->head;//新结点链到头结点 cq->tail=newnode;//自己成为新的尾 } cq->tail=cq->tail->next;//让tail回到原来的位置，也可不加，因为循环，只是个人看着不舒服 cq->head = cq->tail; return cq; } //循环队列的入数据 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; //依次入数据，tail向后走 obj->tail->Data = value; obj->tail = obj->tail->next; return true; } //循环队列的出数据 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->head = obj->head->next; return true; } //循环队列取队头数据 int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->head->Data; } //循环队列取队尾数据 int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; //tail的前有个位置的结点就是队尾的数据 CirQNode* prev = obj->head; while(prev->next != obj->tail) { prev = prev->next; } return prev->Data; } //循环队列判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head == obj->tail; } //循环队列判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->tail->next == obj->head; } //循环队列销毁 void myCircularQueueFree(MyCircularQueue* obj) { while(obj->head != obj->tail) { CirQNode* cur = obj->head->next; free(obj->head); obj->head = cur; } free(obj->head); free(obj); }
