【数据结构】你真的了解栈和队列吗？

admin管理员组

文章数量:1794759

【数据结构】你真的了解栈和队列吗？

1. 栈

1.1 概念与结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的底层结构选型： 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1.2 栈的实现

stack.h

代码语言：javascript代码运行次数：0运行复制

typedef int STDataType;
typedef struct Stack
{
	STDataType * a;
	int top;
	int capacity;
}ST;

// 初始化栈
void STInit(ST * ps);
// 销毁栈
void STDestroy(ST * ps);
// 入栈
void STPush(ST * ps, STDataType x);
//出栈
void STPop(ST * ps);
//取栈顶元素
STDataType STTop(ST * ps);
//获取栈中有效元素个数
int STSize(ST * ps);
//栈是否为空
bool STEmpty(ST * ps);

上面这部分是栈实现所需要的一些方法，其中具体的方法由读者自己先来尝试实现，如有不会的可以在讨论区询问，将会由作者或者其它积极的读者来解答❤️❤️❤️

2. 队列

2.1 概念与结构

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

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

队列的底层结构选型： 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.2 队列的实现

Queue.h

代码语言：javascript代码运行次数：0运行复制

typedef int QDataType;
//队列结点结构
typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;
//队列结构
typedef struct Queue
{
	QNode * phead;
	QNode * ptail;
	int size;
}Queue;
//初始化队列
void QueueInit(Queue * pq);
//销毁队列
void QueueDestroy(Queue * pq);
// 入队列，队尾
void QueuePush(Queue * pq, QDataType x);
// 出队列，队头
void QueuePop(Queue * pq);
//取队头数据
QDataType QueueFront(Queue * pq);
//取队尾数据
QDataType QueueBack(Queue * pq);
//队列判空
bool QueueEmpty(Queue * pq);
//队列有效元素个数
int QueueSize(Queue * pq);

上面这部分是队列实现所需要的一些方法，其中具体的方法由读者自己先来尝试实现，如有不会的可以在讨论区询问，将会由作者或者其它积极的读者来解答❤️❤️❤️

3. 栈和队列的算法题

3.1 有效的括号

/

3.2 用队列实现栈

/

3.3用栈实现队列

/

3.4 设计循环队列

/

循环队列的概念与结构： 实际中还有一种特殊的队列叫循环队列，环形队列首尾相连成环，环形队列可以使用数组实现，也可以使用循环链表实现

思考：队列满的情况下，为什么Q.rear不存储数据？

答案：为了能使用Q.rear = Q.front来区别是队空还是队满，我们常常认为出现左图时的情况即为队满的情况，但是这是不行的。因为初始的情况下，队列虽然为空，但是Q.rear = Q.front，所以应该用右图这种方式，有一个地方不存储数据，此时队列满了则：rear+1=front。

4. 结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-21，如有侵权请联系 cloudcommunity@tencent 删除前往查看数据结构队列链表数据数组

本文标签： 数据结构你真的了解栈和队列吗