【Leetcode】队列的性质与应用

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

分析：

目前没有学习C++，所以先用C语言实现。那么就要手撕一个队列。例子：输入1 2 3 4，输出 4 3 2 1，根据队列的性质先进先出，所以先要进行移数据只剩一个，然后出数据，来回倒腾。

题解：

#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<stdbool.h>typedef int QDataType;//这是结点的结构，但是队列是FIFO，所以要记录头指针和尾指针，方便尾入和头出
typedef struct QueueNode {struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue {QNode* head;//有多个数据就可以再使用一个结构体QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);//队列的初始化
void QueueDestroy(Queue* pq);//队列的销毁
void QueuePush(Queue* pq, QDataType x);//队列的尾部插入数据
void QueuePop(Queue* pq);//队列的头部删除数据
bool QueueEmpty(Queue* pq);//判断队列为不为空
int QueueSize(Queue* pq);//知道队列有几个有效元素
QDataType QueueFront(Queue* pq);//返回队列的首个元素
QDataType QueueBack(Queue* pq);//返回队列的尾元素void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;//队列的初始化将两个指针置为空pq->size = 0;//有效元素为0
}void QueueDestroy(Queue* pq)
{assert(pq);//将一个结点指针指向头节点，作为循环的条件QNode* cur = pq->head;while (cur){QNode* del = cur->next;//一个要删除的结点free(cur);cur = del;//指向下一个结点}//销毁时及时将两个指针置为空，避免野指针的出现pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//malloc申请新的结点if (newnode == NULL){perror("malloc fail");//申请失败报错并返回return;}//如果为空队列，那么就要将指针同时指向新的结点if (pq->head == NULL){pq->head = pq->tail = newnode;}else//这里没加else语句，那么if执行了的话就会混乱{pq->tail->next = newnode;pq->tail = newnode;//同时将尾指针指向新的结点}//将尾结点的next指向新的结点newnode->data = x;//新的结点进行赋值newnode->next = NULL;pq->size++;//有效元素进行加1
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//空的队列就不能删除QNode* del = pq->head;pq->head = pq->head->next;//将头指针指向下个结点free(del);//释放空间del = NULL;//这里要考虑只有一个节点的时候，tail可能会是野指针if (pq->head == NULL){pq->tail = NULL;}pq->size--;//有效元素减1
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//创建两个队列
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {//对队列进行初始化MyStack* newStack = (MyStack*)malloc(sizeof(MyStack));if (newStack == NULL){perror("malloc fail");return NULL;}QueueInit(&newStack->q1);QueueInit(&newStack->q2);return newStack;
}void myStackPush(MyStack* obj, int x) {//如果一个队列为空，那么就放入另一个队列if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//利用假设法找出有数据的队列Queue* emptyq = &obj->q1;Queue* nonemptyq = &obj->q2;if (!QueueEmpty(&obj->q1)){emptyq = &obj->q2;nonemptyq = &obj->q1;}//进行倒元素，直到剩下一个元素while (QueueSize(nonemptyq)> 1){QueuePush(emptyq, QueueFront(nonemptyq));QueuePop(nonemptyq);}int top = QueueFront(nonemptyq);QueuePop(nonemptyq);return top;
}int myStackTop(MyStack* obj) {//哪一个不为空就返回哪一个if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return  QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//malloc几次，就要释放几次QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

622. 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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

提示：

所有的值都在 0 至 1000 的范围内；

操作数将在 1 至 1000 的范围内；

请不要使用内置的队列库。

分析：

这道题目可以使用数组实现，这是一个空间固定的数组，如何判断这个数组是满还是空呢？可以多开一个空间作为缓冲位置。

每次插入之前要判断是否满了，每次删除之前要判断是否空了。
还要考虑rear在队尾时如何判满？rear在队头时如何找到最后一个数？front在队尾时如何判断为多少？

题解：

typedef struct {int* s;int front;int rear;int k;
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (obj == NULL){perror("malloc fail");return NULL;}//创建数组时，多创建一个空间，以便进行循环obj->s = (int*)malloc(sizeof(int) * (k + 1));if (obj->s == NULL){perror("malloc fail");return NULL;}//将头指针和尾指针置为空，将长度记住obj->front = obj->rear = 0;obj->k = k;return obj;
}
//如果头指针和尾指针相等，代表为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
//为满的情况：1. rear在front前面，直接进行加1是否相等，相等则满了
//2. rear在front后面，考虑rear在队尾，那么要将rear指向下标0，就要进行模运算，相等就满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素，如果为满就返回假if (myCircularQueueIsFull(obj))return false;obj->s[obj->rear] = value;//让rear指向下个位置，考虑rear在队尾，那么就要进行模运算obj->rear = (obj->rear + 1) % (obj->k + 1);  return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素，如果为空就返回假if (myCircularQueueIsEmpty(obj))return false;//要将front指向下一个，但是要考虑front在队尾，进行模运算obj->front = (obj->front + 1) % (obj->k + 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {//队列为空返回-1if (myCircularQueueIsEmpty(obj))return -1;return obj->s[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {//队列为空返回-1if (myCircularQueueIsEmpty(obj))return -1;//考虑rear在队头的情况，在队头就赋值为队尾元素，其它情况就返回前一个元素int tail = obj->rear == 0?obj->s[obj->k]:obj->s[obj->rear - 1];return tail;
}void myCircularQueueFree(MyCircularQueue* obj) {//申请两个空间就要释放两个空间free(obj->s);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/