栈和队列OJ练习题及解答

前言

        上一篇博客已经讲到了栈和队列的数据结构，概括一下：栈后进先出（Last In First Out）、队列先进先出（First In First Out）。那么，接下来就来讲讲，关于栈和队列的相关练习题，进一步掌握栈和队列的使用。

一. 用队列实现栈

1. 题目描述

        请你仅使用两个队列实现一个后入先出（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 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

2. 解题思路

        根据上述题目描述，我们需要用两个队列来模拟栈后进先出（Last In First Out），那么问题就在于达到先进后出的效果，怎么如数据和出数据。

        首先队列出数据的话是从队头出，为了达到后出的效果，需要把其他的数据暂时存储起来，这个时候我们的第二个队列的作用就出现了，可以把在其他的数据转移到第二个队列，记录第一个队列头数据，最后清空第一个队列，达到这样的效果。如图1-1所示：

图1-1 双队列模拟栈读取删除数据

        输入的话就将所有数据录入到非空的队列，确保顺序性。

        关于进阶——用一个队列模拟栈：队列里入数据还是一样入，出数据的话就先把队列中前面的数据尾插到原队列，按照这个思路，我们需要知道需要尾插多少次，就在模拟栈的结构里增加一个记录数据总数的整形变量，每次删除数据都尾插数据总数减一次。如图1-2所示：

图1-2 单队列模拟栈出数据

3. 解题代码

        解题代码采用两个队列模拟栈的思路，有兴趣的小伙伴可以尝试单队列模拟。

3.1. 基础代码

        因为需要用队列模拟栈，而C语言不像C++那样能够直接使用库中的队列，所以这里直接提供给大家队列的代码。代码如下：

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode 
{ struct QListNode* _next; QDataType _data; 
}QNode; // 队列的结构 
typedef struct Queue 
{ QNode* _front; QNode* _rear; 
}Queue; // 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->_front = q->_rear = NULL;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);if(QueueEmpty(q)){return 0;}else{QNode* cur = q->_front;int count = 0;while(cur){++count;cur = cur->_next;}return count;}
}// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if(newnode == NULL){perror("QueuePush malloc fail");return;}newnode->_data = data;newnode->_next = NULL;if(q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_next = newnode;q->_rear = q->_rear->_next;}
}// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));if(q->_front == q->_rear){free(q->_front);q->_front = q->_rear = NULL;}else{QNode* next = q->_front->_next;free(q->_front);q->_front = next;}
}// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_front->_data;
}// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_rear->_data;
}// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);//用cur遍历链表QNode* cur = q->_front;//遍历while(cur){//保存下一个位置节点QNode* next = cur->_next;free(cur);//释放内存//移动cur = next;}//队列中指针置为NULLq->_front = q->_rear = NULL;
}

3.2. 题目要求的函数实现

3.2.1. 栈的结构

        栈里面包含两个队列，如下所示：

typedef struct {Queue q1;Queue q2;
} MyStack;

3.2.2. 初始化栈

        为栈的结构开辟空间，并将队列初始化，代码如下：

MyStack* myStackCreate() {MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(st->q1));QueueInit(&(st->q2));return st;
}

3.2.3. 销毁栈

        首先释放栈中队列所开辟的空间然后释放栈开辟的空间，代码如下：

void myStackFree(MyStack* obj) {QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));free(obj);
}

3.2.4. 判断栈是否为空

        检查两个队列里是否存在数据，都没有栈就为空，这里直接调用队列为空的函数即可，代码如下：

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}

3.2.5. 入栈

        向非空的队列入数据，代码如下：

void myStackPush(MyStack* obj, int x) {assert(obj);//如果队列1不为空，则向队列1中录入数据if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1), x);}else//反之就录入数据到队列2{QueuePush(&(obj->q2), x);}
}

3.2.6. 出栈

        根据2.解题思路，代码如下：

int myStackPop(MyStack* obj) {assert(obj);//假设非空的队列为队列2Queue* emp = &(obj->q1);Queue* noemp = &(obj->q2);//如果队列2为空，就交换队列指针if(QueueEmpty(noemp)){emp = &(obj->q2);noemp = &(obj->q1);}//将非空队列前面的数据储存到另一个队列while(QueueSize(noemp) > 1){int x = QueueFront(noemp);QueuePop(noemp);QueuePush(emp, x);}//记录最后一个队列并输出int ret = QueueFront(noemp);QueuePop(noemp);return ret;
}

3.2.7. 访问栈顶数据

        向非空的队列访问最后储存的数据，代码如下：

int myStackTop(MyStack* obj) {assert(obj);//如果队列1为空就访问队列1末尾if(QueueEmpty(&(obj->q1))){return QueueBack(&(obj->q2));}else//反之访问队列2末尾{return QueueBack(&(obj->q1));}
}

3.3. 运行结果

        判题无误：

图1-3 队列模拟栈题解结果

二. 用栈实现队列

1. 题目描述

        请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

2. 解题思路

        用两个栈模拟队列的先进先出（First In First Out），因为栈只能从末尾读取数据，如果要像队列那样保持数据进入的顺序就需要找到队头数据，问题就相当于有两个杯子怎么喝到水杯底部的水。

        所以我们将栈分为入数据的栈和出数据的栈，需要入数据的时候就把出数据的栈的数据放到入数据的栈中然后入数据，反之亦然。如图2-1所示：

图2-1 栈模拟队列1

        这样每次进入数据都需要倒弄栈中的数据时间复杂度为O（N），那么如何降低时间复杂度呢？其实我们不难发现，没必要一直倒弄两个栈中的数据，如果出队列的时候出数据的栈没有数据在将数据倒入出栈栈即可。这样，入队列不需要把出栈的数据倒回去了。如图2-2所示：

图2-2 栈模拟队列2

3. 解题代码

        本题解法直接采用进阶解法。

3.1. 基础代码

        因为需要使用栈的结构，所以这里提供栈的相关代码：

#define INIT 4// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps); 
// 入栈 
void StackPush(Stack* ps, STDataType data); 
// 出栈 
void StackPop(Stack* ps); 
// 获取栈顶元素 
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数 
int StackSize(Stack* ps); 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps); 
// 销毁栈 
void StackDestroy(Stack* ps); // 初始化栈 
void StackInit(Stack* ps)
{assert(ps);STDataType* newnode = (STDataType*)malloc(sizeof(STDataType) * INIT);if(newnode == NULL){perror("StackInit malloc fail");exit(1);}ps->_a = newnode;ps->_top = 0;ps->_capacity = INIT;
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);//容量不足扩容if(ps->_top == ps->_capacity){STDataType* newnode = (STDataType*)realloc(ps->_a, sizeof(STDataType) * ps->_capacity * 2);if(newnode == NULL){perror("StackInit malloc fail");exit(1);}ps->_a = newnode;ps->_capacity *= 2;}//入栈ps->_a[ps->_top] = data;++ps->_top;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);if(!StackEmpty(ps)){--ps->_top;}
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);return ps->_a[ps->_top - 1];//栈顶元素在top的上一位
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{return ps->_top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;
}

3.2. 题目要求的函数实现

3.2.1. 队列结构

typedef struct {Stack st_push;Stack st_pop;
} MyQueue;

3.2.2. 队列初始化

MyQueue* myQueueCreate() {//开辟队列结构的空间MyQueue* qu = (MyQueue*)malloc(sizeof(MyQueue));if(qu == NULL){perror("malloc fail");return NULL;}//初始化两个栈StackInit(&(qu->st_pop));StackInit(&(qu->st_push));//返回队列空间指针return qu;
}

3.2.3. 销毁队列

void myQueueFree(MyQueue* obj) {//分别释放栈开辟的空间StackDestroy(&(obj->st_pop));StackDestroy(&(obj->st_push));//释放队列的空间free(obj);
}

3.2.4. 队列判空

bool myQueueEmpty(MyQueue* obj) {//两个栈都没数据，队列才为空return StackEmpty(&(obj->st_pop)) &&  StackEmpty(&(obj->st_push));
}

3.2.5. 队列入数据

void myQueuePush(MyQueue* obj, int x) {assert(obj);//记录入队列的栈指针，也可以不计，这里方便读者理解简化了Stack* _push = &(obj->st_push);//将数据录入入栈StackPush(_push, x);
}

3.2.6. 队列出数据

int myQueuePop(MyQueue* obj) {//记录入队列的栈指针，也可以不计，这里方便读者理解简化了Stack* _pop = &(obj->st_pop);Stack* _push = &(obj->st_push);//如果出数据的栈为空，就将入数据的栈中数据导入到出数据的栈if(StackEmpty(_pop)){while(!StackEmpty(_push)){int tmp = StackTop(_push);StackPop(_push);StackPush(_pop, tmp);}}//记录需要出队列的数据，删除并输出int ret = StackTop(_pop);StackPop(_pop);return ret;
}

3.2.7.  队列获取头数据

        直接从出数据的栈中获取栈顶元素，没有元素就将入数据栈中元素导入，代码如下：

int myQueuePeek(MyQueue* obj) {Stack* _pop = &(obj->st_pop);Stack* _push = &(obj->st_push);//如果出数据的栈为空，就将入数据的栈中数据导入到出数据的栈if(StackEmpty(_pop)){while(!StackEmpty(_push)){int tmp = StackTop(_push);StackPop(_push);StackPush(_pop, tmp);}}//输出出数据栈头数据int ret = StackTop(_pop);return ret;
}

3.3. 运行结果

        结果无误：

图2-3 栈模拟队列的结果

三. 设计循环队列

1. 题目描述

        设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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 的范围内；
• 请不要使用内置的队列库。

2. 解题思路

2.1. 顺序表模拟

        如果用循序表模拟循环队列，则需要两个指针，指针一指向队列的头，一个指向数组的尾部。入数据从数组尾部进入，队列头用来删除数据，数组开辟的大小为顺序链表的容量。如果循环队列悟空用两个指针指向同一位置来表示，那么想要表示队列为满有两种方式：（1）在队列中增加一个变量记录数组中存在的数据个数。（2）开辟数组大小的时候多开一个空出的空间，那么数组为满的表示为尾指针加一等于头指针。

图3-1 顺序表模拟循环队列

2.2. 链表模拟

        如果用链表模拟就比较麻烦，需要先将链表的空间全部开好，那么剩下的各种操作与顺序表模拟循环队列相同。相比较起来，单向链表模拟如果需要读取队尾数据会比较麻烦，需要将尾指针遍历到尾指针之前的节点，所以使用双向链表模拟会更好，但是那从空间上来说不如顺序表模拟。如果找一个变量记录数据个数，插入的时候按照双向链表尾插，只是限制最后插入的节点个数未必不可行。

3. 解题代码

3.1. 题目要求的函数实现

        根据2.1.的解题思路。

3.1.1. 循环队列的结构

//定义存储数据的类型
typedef int QueueDataType;typedef struct {QueueDataType* a; //顺序表位置int pcur;  //头指针int ptail; //尾指针int size;  //限制的循环队列大小
} MyCircularQueue;

3.1.2. 循环队列初始化

        包括开辟空间，各项指针置为0，记录队列容量，代码如下：

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(cq == NULL){perror("malloc fail");return NULL;}cq->a = (QueueDataType*)malloc(sizeof(QueueDataType) * (k + 1));cq->pcur = cq->ptail = 0;cq->size = k;return cq;
}

3.1.3. 判断队列是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return obj->ptail == obj->pcur;
}

3.1.4. 判断队列中数据是否满了

        向这总增加的都需要用总容量取模，防止溢出。

bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);return (obj->ptail + 1) % (obj->size + 1) == obj->pcur;
}

3.1.5. 向队列中增加数据

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);//队列满员了就无法添加if(myCircularQueueIsFull(obj)){return false;}else{obj->a[obj->ptail++] = value;obj->ptail %= (obj->size + 1);return true;}
}

3.1.6. 从队列中删除数据

bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);//如果队列为空则删除失败if(myCircularQueueIsEmpty(obj)){return false;}else{++obj->pcur;obj->pcur %= (obj->size + 1);return true;}
}

3.1.7. 从队头获取数据

int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);//队列为空返回-1if(myCircularQueueIsEmpty(obj)){return -1;}else//反之返回数据{return obj->a[obj->pcur];}
}

3.1.8. 从队尾获取数据

int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);//为空返回-1if(myCircularQueueIsEmpty(obj)){return -1;}else//队尾指针-1+k+1最后取模得到后一位的地址{return obj->a[(obj->ptail + obj->size) % (obj->size + 1)];}
}

3.2. 运行结果

        结果无误：

图3-2 

作者结语

        虽然说代码能够解开谜题，但是用文本的方式真的很难把题目短时间说清楚。具体细节还需要读者自己体会，这里最多算是抛了一个砖。

        感谢大家看到这里，那也说明写博客的时间没有白费。