【数据结构】栈和队列（链表模拟队列）

学习本章节必须具备单链表的前置知识，

建议提前学习：点击链接学习：单链表各种功能函数细节详解

本章节是学习用单链表模拟队列

1. 单链表实现队列思路如下

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

1.1 使用数组还是链表模拟队列结构？

因为需要模拟队列先进先出的特性：队头只能出，队尾只能进

若使用 数组模拟，每次 pop 队头操作，就需要全部元素向前面移动，时间复杂度为 O(n)

综上，因为需要考虑位置变化，选择链表实现队列较优

1.2. 需要使用什么类型的链表模拟队列？

单向

带头 / 不带头都可以 ：因为哨兵位主要用于双向链表找尾，为了方便删除，这里差别不大

不循环

我们下面实现的是 单向不带头不循环链表

实际上，单向或双向，循环或不循环，带头或不带头完全取决于你自己要实现一个功能的需求，不是说一定要固定使用哪一个套，需要灵活选择使用

1.3. 单向链表实现队列的链表节点结构体创建：

typedef int QDataType;
typedef struct QueueNode
{QDataType value;            // 节点数据struct QueueNode* next;     // 指向下一个节点
}QNode;

1.4. 考虑效率，创建头尾指针结构体

因为队列需要：队头 push，队尾 pop

涉及到对链表的尾部操作必须意识到：需要先进行 找尾操作，时间复杂度为 O(n)

方案：因为涉及头尾频繁操作：可以直接同时定义头指针 phead 和尾指针 ptail

技巧：同类型的变量可以封装成一个结构体

因为 phead 和 ptail 是可以不断变化的，每个相关函数都需要同时传递 phead 和 ptail 两个变量

则可以将多个同类型的变量 封装成一个结构体，方便操作

这样，传递变量时直接传递一个结构体的指针就行了

typedef struct Queue
{QNode* phead;QNode* ptail;
}Queue;

// 区别：减少了传递变量的数量，利于协助开发
// void QueuePush(QNode* phead, QNode* ptail);
void QueuePush(Queue* pq);
// void QueuePop(QNode* phead, QNode* ptail);
void QueuePop(Queue* pq);

1.5. Push / Pop ：入队和出队操作

Push 在队尾入队，Pop 在队头出队

void QueuePop(Queue* pq)
{assert(pq);// pop 的删除操作 需要分类讨论：链表节点个数为 0、为 1、为 两个以上// 为 0 ：直接判空，退出操作：phead == ptail == NULLassert(pq->phead);    // 头节点为空 就一定代表为空了// 为 1：phead == ptail  但是 phead != NULL 的情况：即一定指向一个节点if (pq->phead == pq->ptail && pq->phead != NULL) {free(pq->phead);pq->phead = pq->ptail = NULL;}else // 为 两个以上：先记录第二个节点，free 掉头节点，更新头节点{QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}
}

为什么 ” 头节点为空或尾节点为空就一定代表链表为空了 “？

1.6. 观察上面代码：有需要判断链表节点数量的需求，为了简化代码与优化过程，可以直接定义一个 size ，放进结构体中，时刻记录链表节点数量

// 结构体更改：
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 加入 size 后 的 Push 和 Pop 函数
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}

2. 综上所述，最终代码：

Queue.c

#include"Queue.h"// Push 入队，Pop 出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}// 初始化
void  QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 销毁链表：就是 单链表的 销毁操作
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULLpq->size = 0;
}// Front 返回队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead); // 若链表为空 自然没有头节点;return pq->phead->value;
}// Back 返回队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail); // 若链表为空 自然没有尾节点;return pq->ptail->value;
}// Empty 判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}// Size 返回节点数量
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
typedef struct QueueNode
{QDataType value;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化
void  QueueInit(Queue* pq);   // Push 入队，Pop 出队
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);// Front 队头元素，Back 队尾元素
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);// Empty 判断是否为空，Size 返回节点数量
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);// 销毁链表
void QueueDestory(Queue* pq);

Main.c

#include"Queue.h"int main()
{Queue q;   // 创建队列结构体QueueInit(&q); // 初始化：用于初始化链表的头尾节点：phead  /  ptailfor (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5QueuePush(&q, i); }// 一个个读取队列元素while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestory(&q);return 0;
}

3. LeetCode：225.队列实现栈

使用两个队列实现栈

核心思路：

保持一个队列存数据，一个队列为空

push 入数据，入到不为空的队列

pop 出数据，将非空队列中前 n-1 个数据导入空队列

代码实现

// 以下均是 链式队列的 相关函数，复制粘贴过来罢了
///
typedef int QDataType;
typedef struct QueueNode
{QDataType value;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}// 初始化
void  QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 销毁链表：就是 单链表的 销毁操作
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULLpq->size = 0;
}// Front 返回队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead); // 若链表为空 自然没有头节点;return pq->phead->value;
}// Back 返回队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail); // 若链表为空 自然没有尾节点;return pq->ptail->value;
}// Empty 判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}// Size 返回节点数量
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
// 以上均是 链式队列的 相关函数，复制粘贴过来罢了
//////
// 下面是题目主体
typedef struct {Queue q1, q2; // 创建两个队列
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); // 创建一个栈QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}void myStackPush(MyStack* obj, int x) {// push 到 不为空的 队列if(QueueEmpty(&(obj->q1))) {QueuePush(&(obj->q2), x);}else {QueuePush(&(obj->q1), x);}
}int myStackPop(MyStack* obj) {// 找到非空的 队列，将 size-1 个元素放进 另一个空队列，同时最后一个元素pop掉// 有两种情况：q1 为空，q2 不为空, q2 为空，q1 不为空// 可以先假设，后调整// 先假设 队列1 为空，队列2 不为空，后面判断后调整Queue* pEmptyQ = &(obj->q1);Queue* pNonEmptyQ = &(obj->q2);if(!QueueEmpty(&(obj->q1))){pEmptyQ = &(obj->q2);pNonEmptyQ = &(obj->q1);}// 将不为空队列 的前 n-1 个元素放进 空队列中while(QueueSize(pNonEmptyQ) > 1) {int x = QueueFront(pNonEmptyQ);QueuePush(pEmptyQ, x);QueuePop(pNonEmptyQ);}int t = QueueFront(pNonEmptyQ);QueuePop(pNonEmptyQ);return t;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&(obj->q1))) {return QueueBack(&(obj->q2));}else {return QueueBack(&(obj->q1));}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2)); // 两个都为空才是栈空
}void myStackFree(MyStack* obj) {if(QueueEmpty(&(obj->q1))) {QueueDestory(&(obj->q2));}else if(QueueEmpty(&(obj->q2))) {QueueDestory(&(obj->q1));}
}

4. LeetCode：223.栈实现队列

使用两个栈模拟队列

思路

定义一个 pushStack ：专门用来接收 push入队列的数据

定义一个 popStack ：专门用来 pop 队列数据

当 popStack 为空时，此时需要 pop 操作，则将 pushStack 的数据全部放进 popStack ，补充数据（注意是全部）；若popStack 不为空，则进行 pop 操作即可

当需要 push 操作，直接往 pushStack 中放数据即可