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

这篇具有很好参考价值的文章主要介绍了【数据结构】栈和队列（链表模拟队列）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

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 == NULL
	assert(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;  // 最后别忘了头尾指针置为 NULL
	pq->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  /  ptail

	for (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5
		QueuePush(&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;  // 最后别忘了头尾指针置为 NULL
	pq->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 中放数据即可

演示： push 2 次，pop 1 次，push 3 次， pop 3 次

【若文章有什么错误，欢迎评论区讨论或私信指出】 文章来源地址https://www.toymoban.com/news/detail-859505.html

到了这里，关于【数据结构】栈和队列（链表模拟队列）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

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

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

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

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

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

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

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

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

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

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

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

Queue.c

Queue.h

Main.c

3. LeetCode：225.队列实现栈

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

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

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

代码实现

4. LeetCode：223.栈实现队列

使用两个栈模拟队列

思路

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

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

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

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

演示： push 2 次，pop 1 次，push 3 次， pop 3 次

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

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

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

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

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

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

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

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

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

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

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

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

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

Queue.c

Queue.h

Main.c

3. LeetCode：225.队列实现栈

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

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

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

代码实现

4. LeetCode：223.栈实现队列

使用 两个栈 模拟队列

思路

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

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

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

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

演示： push 2 次，pop 1 次，push 3 次， pop 3 次

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

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

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

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

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

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

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

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

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

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

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

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

使用两个栈模拟队列

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

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

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