初级数据结构:栈和队列

目录

一、栈

(一)、栈的定义

(二)、栈的功能

(三)、栈的实现

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指针在到达数组末尾时能够回到开头，实现循环的效果。

三、栈和队列的比较

栈和队列虽然都是线性数据结构，但它们在很多方面存在差异：

1. 进出顺序：栈遵循后进先出（LIFO）原则，最后进入栈的元素最先出栈；而队列遵循先进先出（FIFO）原则，最先进入队列的元素最先出队 。例如，在程序调用栈中，函数调用是按照后进先出的顺序进行的，而在网络请求队列中，请求是按照先进先出的顺序被处理的。
2. 插入删除操作：栈的插入（入栈）和删除（出栈）操作都在栈顶进行；队列的插入（入队）操作在队尾进行，删除（出队）操作在队头进行 。比如，往栈中添加元素就像往一摞盘子上放盘子，只能放在最上面，从栈中取出元素也只能从最上面取；而队列中添加元素就像排队买票，新来的人站在队伍末尾，离开的人从队伍最前面离开。
3. 遍历数据速度：栈只能从栈顶开始遍历，若要访问栈底元素，需要依次弹出栈顶元素，遍历过程中需要开辟临时空间来保存数据状态，以确保遍历前后数据的一致性；队列基于地址指针进行遍历，可以从队头或队尾开始遍历，但不能同时进行双向遍历，遍历过程中不会改变数据结构，所以无需开辟额外空间，遍历速度相对较快 。例如，在遍历一个包含 100 个元素的栈时，如果要获取栈底元素，需要将栈顶的 99 个元素依次弹出并保存，然后才能访问栈底元素，最后再将弹出的元素依次压回栈中；而遍历一个包含 100 个元素的队列时，从队头开始遍历，直接按照顺序访问每个元素即可。
4. 限定条件：栈只允许在一端进行插入和删除操作；队列允许在一端插入，在另一端删除操作 。这是它们最基本的操作限制，决定了它们在不同场景下的适用性。例如，在实现表达式求值时，利用栈的特性可以方便地处理运算符优先级；而在实现任务调度时，利用队列的特性可以保证任务按照提交顺序依次执行。
5. 应用场景：栈常用于处理具有后进先出特性的问题，如函数调用、表达式求值、括号匹配等；队列常用于处理具有先进先出特性的问题，如网络请求处理、消息队列、任务调度等 。例如，在编译器中，使用栈来处理函数调用和递归，确保函数的正确返回和局部变量的正确管理；在分布式系统中，使用消息队列来异步处理消息，提高系统的吞吐量和响应速度。

如果你认为你已经对栈和队列掌握完全，那你可以尝试做一下下面的题目看看：

1.有效的括号

2.用队列实现栈

3.用栈实现队列

4.设计循环队列