初级数据结构:栈和队列
目录
一、栈
(一)、栈的定义
(二)、栈的功能
(三)、栈的实现
1.栈的初始化
2.动态扩容
3.压栈操作
4.出栈操作
5.获取栈顶元素
6.获取栈顶元素的有效个数
7.检查栈是否为空
8.栈的销毁
9.完整代码
二、队列
(一)、队列的定义
(二)、队列的功能
(三）、队列的实现
1、队列初始化
2、队尾入队列
3、队头出队列
4、获取队列头部元素
5、获取队列尾部元素
6、获取队列有效元素个数
7、检查队列是否为空
8、队列的销毁
(四)、循环队列
三、栈和队列的比较
一、栈
(一)、栈的定义
栈是一种遵循后进先出（LIFO，Last In First Out）原则的数据结构。栈的主要操作包括入栈（Push）和出栈（Pop）。入栈操作是将元素添加到栈顶，这一过程中，栈顶指针上移，新元素被放置在栈顶位置；出栈操作则是移除栈顶元素，同时栈顶指针下移。此外，还可以通过获取栈顶元素（Top）操作来查看栈顶元素但不将其移除。
形象的来说，压栈操作就像堆叠盘子，一个盘子放在另一个盘子上。当你想取出盘子时，你必定会从顶部取出。如果从中间取盘子，那就有盘子打烂的风险，这也就是出栈操作。
栈也是一种线性表，在对于表达式求值和符号匹配等方面有很大用途。
如果你已经学完了顺序表，那么栈的实现对你来说轻而易举。
(二)、栈的功能
1、压栈（Push）：将一个元素添加到栈顶。比如我们往弹夹里装子弹的动作就相当于入栈操作。
2、出栈（Pop）：从栈顶移除一个元素。对应弹夹射击时弹出子弹的过程。
3、获取栈顶元素（Peek）：获取栈顶元素，但不将其从栈中移除。这就像是我们查看弹夹最上面的子弹是什么类型，但不把它射出。
4、获取栈中有效元素个数（Size）：就像我们查看弹夹中的子弹数目。
5、判断栈是否为空（IsEmpty）：检查栈中是否没有元素。当弹夹里没有子弹时，就可以说栈为空。
(三)、栈的实现
对于栈来说，我们可以使用数组或者链表来实现栈。相对而言，使用数组来实现栈比用链表来实现更优。因为进行栈的压栈操作时，数组尾部插入数据的代价更小。而如果使用双向链表又过于麻烦。因此，我们对于栈的结构体定义如下:
typedef struct Stack
{
int* data;//动态数组
int top;//指向栈顶元素，在后续的初始化中，将其初始化为0还是-1，决定着top指向栈顶元素还是指向栈顶元素后一位
int capicity;//容量大小
}Stack;1.栈的初始化
和顺序表一样，我们需要先进行动态内存申请一定的空间代码如下:
void StackInit(Stack* ps)
{
//动态内存申请4个整形空间，空间申请小一些方便检查后续扩容是否正确
int* ptr = (int*)malloc(sizeof(int) * 4);
if (ptr == NULL)
{
//判断空间是否申请成功，失败则打印错误信息
perror("StackInit::malloc");
return;
}
ps->data = ptr;
ps->capicity = 4;
//我这里是让top指向栈顶元素的后一位，看自己的想法
//这里top的指向如何会影响后续获取栈顶元素功能实现的代码
ps->top = 0;
}2.动态扩容
这个动态扩容由于我们使用数组来实现栈，因此动态扩容函数与顺序表基本一致，代码如下:
void Expansion(Stack* ps)
{
assert(ps);
if (ps->top == ps->capicity)
{
printf("空间不足\n");
int* ptr = (int*)realloc(ps->data, sizeof(int) * (ps->capicity * 2));
if (ptr == NULL)
{
perror("Expansion::realloc");
return;
}
ps->data = ptr;
capicity*=2;
}
}3.压栈操作
实质上就是顺序表的尾插。代码如下:
void StackPush(Stack* ps)
{
assert(ps);
//判断是否需要扩容
Expansion(ps);
printf("请输入数字\n");
//如果你的top初始化为-1，那么这里就需要先top++，再赋值
scanf("%d", &ps->data[ps->top]);
printf("入栈成功\n");
ps->top++;
}4.出栈操作
实质上就是顺序表的尾删，直接使top指针往前移一步，等下次压栈操作后，数据覆盖即可达到出栈作用，代码如下:
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)
{
ps->top--;
printf("出栈成功\n");
}
else
{
printf("栈中无元素\n");
}
}5.获取栈顶元素
因为我们这里top初始化为0，所以top一直指向栈顶元素后一位，如果我们想要获取栈顶元素就需要使top减一，代码如下:
int StackTop(Stack* ps)
{
assert(ps);
return ps->data[ps->top-1];
}6.获取栈顶元素的有效个数
直接返回top即可，代码如下:
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}7.检查栈是否为空
当top与初始化的top数相等时，栈就为空，代码如下:
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
{
return 0;
}
else
{
return ps->top;
}
}8.栈的销毁
和顺序表的销毁一致，先释放栈的空间，然后将指针data置空，容量也即capicity和top都置为0。代码如下:
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capicity = 0;
ps->top = 0;
printf("销毁成功\n");
}至此，一个基础的栈就实现了，完整代码如下。
9.完整代码
stack.h中:
#pragma once
#pragma warning(disable : 4996)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct Stack
{
int* data;
int top;
int capicity;
}Stack;
// 初始化栈
void StackInit(Stack* ps);
//动态扩容
void Expansion(Stack* ps);
// 入栈
void StackPush(Stack* ps);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
int StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);Fstack.c中：
#include"stack.h"
void StackInit(Stack* ps)
{
int* ptr = (int*)malloc(sizeof(int) * 4);
if (ptr == NULL)
{
perror("StackInit::malloc");
return;
}
ps->data = ptr;
ps->capicity = 4;
ps->top = 0;
}
void Expansion(Stack* ps)
{
assert(ps);
if (ps->top == ps->capicity)
{
printf("空间不足\n");
int* ptr = (int*)realloc(ps->data, sizeof(int) * (ps->capicity * 2));
if (ptr == NULL)
{
perror("Expansion::realloc");
return;
}
ps->data = ptr;
ps->capicity*=2;
}
}
void StackPush(Stack* ps)
{
assert(ps);
Expansion(ps);
printf("请输入数字\n");
scanf("%d", &ps->data[ps->top]);
printf("入栈成功\n");
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)
{
ps->top--;
printf("出栈成功\n");
}
else
{
printf("栈中无元素\n");
}
}
int StackTop(Stack* ps)
{
assert(ps);
return ps->data[ps->top-1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
{
return 0;
}
else
{
return ps->top;
}
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capicity = 0;
ps->top = 0;
printf("销毁成功\n");
}
stack.h:
#include"stack.h"
Stack ps;
int main()
{
// 初始化栈
StackInit(&ps);
int a,b;
do
{
printf("请输入数字\n");
scanf("%d", &a);
switch (a)
{
case 1:
// 入栈
StackPush(&ps);
break;
case 2:
// 出栈
StackPop(&ps);
break;
case 3:
// 获取栈顶元素
b = StackTop(&ps);
printf("栈顶元素：%d\n", b);
break;
case 4:
// 获取栈中有效元素个数
printf("%d\n", StackSize(&ps));
break;
case 5:
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
printf("%d\n", StackEmpty(&ps));
break;
case 0:
// 销毁栈
StackDestroy(&ps);
printf("退出\n");
break;
}
} while (a);
return 0;
}二、队列
(一)、队列的定义
在数据结构的大家庭中，队列是一位独特而重要的成员。想象一下，在超市结账的队伍里，先来的顾客排在前面先结账离开，后来的顾客则依次在队尾加入等待，这就是典型的 “先进先出（FIFO，First In First Out）原则，而队列正是这种原则在计算机领域的完美体现。
队列作为一种特殊的线性表，它的操作被严格限定在两端进行。一端被称为队尾（rear），专门用于插入新元素，就像新顾客加入结账队伍的末尾；另一端是队头（front），负责删除元素，恰似排在队伍最前面的顾客完成结账后离开。这种操作受限的特性，赋予了队列先进先出的独特性质，也使得它在众多算法和实际应用中发挥着关键作用 。无论是操作系统中的任务调度、网络通信中的数据包处理，还是广度优先搜索算法中的节点遍历，队列都扮演着至关重要的角色
和栈一样，它的实现同样可以使用数组和链表来实现。因为上述我们使用了数组来实现栈，故此次队列的实现我们采用链表来实现，也即链式队列。
在链式队列中，每个节点包含数据域和指针域，数据域用于存储队列元素，指针域则指向下一个节点。队列通过两个指针来管理：头指针（front）指向链表的头节点，代表队头；尾指针（rear）指向链表的尾节点，代表队尾 。
入队操作时，创建一个新节点存储新元素，然后将其插入到链表的尾部，同时更新尾指针指向新节点；出队操作则是删除链表头部的节点，返回该节点的数据，并更新头指针指向下一个节点。比如，有一个初始为空的链式队列，当元素 3 入队时，创建一个新节点存储 3，此时头指针和尾指针都指向这个新节点 。接着元素 4 入队，创建新节点并插入到链表尾部，尾指针更新指向新节点。当出队时，删除头指针指向的节点（包含元素 3），头指针移动到下一个节点（包含元素 4） 。
链式队列的优点是不需要预先知道队列的最大容量，因为链表可以动态地分配内存，避免了顺序队列可能出现的溢出问题；而且在进行插入和删除操作时，只需要修改指针，不需要移动大量元素，效率较高。然而，链式队列也有缺点，由于每个节点都需要额外的指针域来指向下一个节点，这会占用更多的内存空间；并且链表不支持随机访问，访问特定位置的元素需要从头开始遍历链表，时间复杂度较高 。
(二)、队列的功能
1、队尾入队列
2、队头出队列
3、获取队列头部元素
4、获取队列尾部元素
5、获取队列有效元素个数
6、检查队列是否为空
(三）、队列的实现
因为链式队列需要头指针和尾指针，因此我们不能只像链表那样只用一个结构体。我们需要再使用一个结构体以使进行函数传参时更方便，故结构体的构造如下：
//节点
typedef struct QueueNode
{
int data;
struct QueueNode* next;
}Qnode;
typedef struct Queue
{
//头指针
Qnode* head;
//尾指针
Qnode* tail;
//计数存储数据个数
int size;
}Queue;1、队列初始化
void QueueInit(Queue* q)
{
assert(q);
q->head = NULL;
q->tail = NULL;
q->size = 0;
}因为还未存储数据，故头指针和尾指针都置空，以防止野指针出现。不要忘记将size也初始化为0；
2、队尾入队列
先看图：
如果我们是往队列中插入第一个节点，此时头指针和尾指针都指向空。我们就需要将头指针和尾指针都指向新节点，再将节点的next指针指向NULL；
而如果我们插入新节点时，队列中已有数据存储，也即有节点存在，将上述两图结合起来看，第一张代表插入新节点前，第二张代表插入新节点后。我们需要先使尾指针指向的节点的next指针指向新节点，再让尾指针指向新节点，最后再使新节点置空即可。代码如下：
void QueuePush(Queue* q)
{
assert(q);
//申请新节点
Qnode* ptr = (Qnode*)malloc(sizeof(Qnode));
if (ptr == NULL)
{
perror("QueuePush::malloc");
return;
}
printf("请输入数字\n");
scanf("%d", &ptr->data);
//提前将新节点next指针置空
ptr->next = NULL;
//判断队列是否为空
if (q->head == NULL && q->tail == NULL)
{
q->head = q->tail = ptr;
}
else
{
q->tail->next = ptr;
q->tail = ptr;
}
q->size++;
}3、队头出队列
先看代码：
void QueuePop(Queue* q)
{
assert(q);
//判断头指针是否为空，为空那还出什么队列
assert(q->head);
//先存储头指针指向的节点的下一个节点的位置
Qnode* headnext = q->head->next;
//释放头指针指向的节点空间
free(q->head);
//再让头指针指向之前存储的节点
q->head = headnext;
//如果队列中只有一个节点，那释放空间后，头指针是空，但
//尾指针没有被置为空，而是处于野指针状态，因此也要将
//尾指针置空
if (q->head == NULL)
{
q->tail = NULL;
}
q->size--;
printf("出队列成功\n");
}
4、获取队列头部元素
我们知道在链式队列中，链表头即是队头，链表尾即是队尾。获取队列头部元素即可以直接通过头指针获取。代码如下：
int QueueFront(Queue* q)
{
assert(q);
if (q->head == NULL)
{
printf("队列无元素\n");
return NULL;
}
return q->head->data;
}5、获取队列尾部元素
和获取队列头部元素一致，更改指针即可。代码如下：
int QueueBack(Queue* q)
{
assert(q);
if (q->tail == NULL)
{
printf("队列无元素\n");
return NULL;
}
return q->tail->data;
}6、获取队列有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}7、检查队列是否为空
为空返回0，不为空返回非零结果。
int QueueEmpty(Queue* q)
{
assert(q);
return q->size;
}
8、队列的销毁
队列的销毁和链表的销毁一致，遍历一遍，在遍历中存储下一个节点的位置，销毁当前节点，更新条件即可。代码如下：
void QueueDestroy(Queue* q)
{
assert(q);
Qnode* ptr = q->head;
if (q->head == NULL)
{
return;
}
while (ptr)
{
Qnode* ptrnext = ptr->next;
free(ptr);
ptr = ptrnext;
}
q->head = q->tail = NULL;
printf("队列销毁成功\n");
q->size = 0;
}至此，一个基础的队列就完成了，完整代码如下：
9、完整代码
queue.h:
#pragma once
#pragma warning(disable : 4996)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//节点
typedef struct QueueNode
{
int data;
struct QueueNode* next;
}Qnode;
typedef struct Queue
{
//头指针
Qnode* head;
//尾指针
Qnode* tail;
//计数存储数据个数
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
int QueueFront(Queue* q);
// 获取队列队尾元素
int QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);Fqueue.c:
#include"queue.h"
void QueueInit(Queue* q)
{
assert(q);
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
void QueuePush(Queue* q)
{
assert(q);
//申请新节点
Qnode* ptr = (Qnode*)malloc(sizeof(Qnode));
if (ptr == NULL)
{
perror("QueuePush::malloc");
return;
}
printf("请输入数字\n");
scanf("%d", &ptr->data);
//提前将新节点next指针置空
ptr->next = NULL;
//判断队列是否为空
if (q->head == NULL && q->tail == NULL)
{
q->head = q->tail = ptr;
}
else
{
q->tail->next = ptr;
q->tail = ptr;
}
q->size++;
}
void QueuePop(Queue* q)
{
assert(q);
//判断头指针是否为空，为空那还出什么队列
assert(q->head);
//先存储头指针指向的节点的下一个节点的位置
Qnode* headnext = q->head->next;
//释放头指针指向的节点空间
free(q->head);
//再让头指针指向之前存储的节点
q->head = headnext;
//如果队列中只有一个节点，那释放空间后，头指针是空，但
//尾指针没有被置为空，而是处于野指针状态，因此也要将
//尾指针置空
if (q->head == NULL)
{
q->tail = NULL;
}
q->size--;
printf("出队列成功\n");
}
int QueueFront(Queue* q)
{
assert(q);
if (q->head == NULL)
{
printf("队列无元素\n");
return NULL;
}
return q->head->data;
}
int QueueBack(Queue* q)
{
assert(q);
if (q->tail == NULL)
{
printf("队列无元素\n");
return NULL;
}
return q->tail->data;
}
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
int QueueEmpty(Queue* q)
{
assert(q);
return q->size;
}
void QueueDestroy(Queue* q)
{
assert(q);
Qnode* ptr = q->head;
if (q->head == NULL)
{
return;
}
while (ptr)
{
Qnode* ptrnext = ptr->next;
free(ptr);
ptr = ptrnext;
}
q->head = q->tail = NULL;
printf("队列销毁成功\n");
q->size = 0;
}
queue.c:
#include"queue.h"
Queue Que;
int main()
{
int a;
// 初始化队列
QueueInit(&Que);
do
{
printf("输入数字\n");
scanf("%d", &a);
switch (a)
{
case 1:
// 队尾入队列
QueuePush(&Que);
break;
case 2:
// 队头出队列
QueuePop(&Que);
break;
case 3:
// 获取队列头部元素
printf("%d\n",QueueFront(&Que));
break;
case 4:
// 获取队列队尾元素
printf("%d\n",QueueBack(&Que));
break;
case 5:
// 获取队列中有效元素个数
printf("%d\n",QueueSize(&Que));
break;
case 6:
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
printf("%d\n",QueueEmpty(&Que));
break;
case 0:
// 销毁队列
QueueDestroy(&Que);
break;
}
} while (a);
return 0;
}(四)、循环队列
在了解顺序队列时，我们提到了假溢出问题，而循环队列就是为了解决这个问题而引入的。循环队列是一种特殊的顺序队列，它将顺序队列的首尾相连，把存储队列元素的表从逻辑上看成一个环。
在循环队列中，我们仍然使用front指针指示队头位置，rear指针指示队尾位置。当rear指针到达数组末尾时，如果数组前面还有空闲空间，它可以重新回到数组开头，继续利用前面的空闲空间。例如，假设我们有一个大小为 5 的循环队列数组，初始时front和rear都为 0 。当进行入队操作时，rear指针依次移动到 1、2、3、4 位置。当rear到达 4 时，如果再进行入队操作，rear就会回到 0 位置（通过取模运算实现）。
判断循环队列是否为空和满的条件与普通顺序队列有所不同。在循环队列中，当front等于rear时，表示队列为空；而当(rear + 1) % 队列容量 == front时，表示队列已满。这里的取模运算保证了rear指针在到达数组末尾时能够回到开头，实现循环的效果。
三、栈和队列的比较
栈和队列虽然都是线性数据结构，但它们在很多方面存在差异：
- 进出顺序：栈遵循后进先出（LIFO）原则，最后进入栈的元素最先出栈；而队列遵循先进先出（FIFO）原则，最先进入队列的元素最先出队 。例如，在程序调用栈中，函数调用是按照后进先出的顺序进行的，而在网络请求队列中，请求是按照先进先出的顺序被处理的。
- 插入删除操作：栈的插入（入栈）和删除（出栈）操作都在栈顶进行；队列的插入（入队）操作在队尾进行，删除（出队）操作在队头进行 。比如，往栈中添加元素就像往一摞盘子上放盘子，只能放在最上面，从栈中取出元素也只能从最上面取；而队列中添加元素就像排队买票，新来的人站在队伍末尾，离开的人从队伍最前面离开。
- 遍历数据速度：栈只能从栈顶开始遍历，若要访问栈底元素，需要依次弹出栈顶元素，遍历过程中需要开辟临时空间来保存数据状态，以确保遍历前后数据的一致性；队列基于地址指针进行遍历，可以从队头或队尾开始遍历，但不能同时进行双向遍历，遍历过程中不会改变数据结构，所以无需开辟额外空间，遍历速度相对较快 。例如，在遍历一个包含 100 个元素的栈时，如果要获取栈底元素，需要将栈顶的 99 个元素依次弹出并保存，然后才能访问栈底元素，最后再将弹出的元素依次压回栈中；而遍历一个包含 100 个元素的队列时，从队头开始遍历，直接按照顺序访问每个元素即可。
- 限定条件：栈只允许在一端进行插入和删除操作；队列允许在一端插入，在另一端删除操作 。这是它们最基本的操作限制，决定了它们在不同场景下的适用性。例如，在实现表达式求值时，利用栈的特性可以方便地处理运算符优先级；而在实现任务调度时，利用队列的特性可以保证任务按照提交顺序依次执行。
- 应用场景：栈常用于处理具有后进先出特性的问题，如函数调用、表达式求值、括号匹配等；队列常用于处理具有先进先出特性的问题，如网络请求处理、消息队列、任务调度等 。例如，在编译器中，使用栈来处理函数调用和递归，确保函数的正确返回和局部变量的正确管理；在分布式系统中，使用消息队列来异步处理消息，提高系统的吞吐量和响应速度。
如果你认为你已经对栈和队列掌握完全，那你可以尝试做一下下面的题目看看：
1.有效的括号
2.用队列实现栈
3.用栈实现队列
4.设计循环队列