数据结构：栈与队列奇妙之旅（图文带你欣赏栈和队列的魅力）
2021/5/4 10:29:00
本文主要是介绍数据结构：栈与队列奇妙之旅（图文带你欣赏栈和队列的魅力），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
栈
定义： 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。
例： 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。
例： 一叠书或一叠盘子。
栈的抽象数据类型的定义如下：
顺序栈
由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：
typedef int datatype;
#define MyStacksize 10
typedef struct mystack
{
datatype data[MyStacksize] = { 0 };
int top;
}MyStack;
初始状态：
当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
完整代码
include <stdio.h>
typedef int datatype;
#define MyStacksize 10
typedef struct mystack
{
datatype data[MyStacksize] = { 0 };
int top;
}MyStack;
void initstack(MyStack* sta)//创建空栈
{
sta->top = -1;
}
bool stackempty(MyStack* sta)//判断栈空
{
return sta->top == -1;
}
bool stackfull(MyStack* sta)//判断栈满
{
return sta->top == MyStacksize - 1;
}
void push(MyStack* sta,datatype element)//压栈
{
if (stackfull(sta)) {
printf("栈满，压栈失败！！！");
return;
}
else {
sta->top++;
sta->data[sta->top] = element;
}
}
datatype pop(MyStack* sta)//出栈
{
if (stackempty(sta)) {
printf("栈空，出栈失败！！！");
return NULL;
}
else {
datatype element;
element = sta->data[sta->top]; //取得栈顶元素
sta->data[sta->top] = 0; //删除栈顶元素
sta->top--; //更新栈顶指针
return element;
}
}
datatype stacktop(MyStack* sta)//取栈顶元素
{
if (stackempty(sta)) {
printf("栈空，取出失败！！！");
return NULL;
}
else {
return sta->data[sta->top];
}
}
int main()//主函数只给出初始化和部分测试代码，可自己在主函数添加具体测试调用函数
{
MyStack* sta=(MyStack*)malloc(sizeof(MyStack));
initstack(sta); //创建空栈
printf("%d\n", sta->top);
if (stackempty(sta)) //判断栈是否为空
printf("栈空！！！\n");
else
printf("栈不空！！！\n");
push(sta, 10); //压栈
printf("%d\n", stacktop(sta));
if (stackfull(sta)) //判断栈满
printf("栈满！！！\n");
else
printf("栈未满！！！\n");
printf("%d\n",pop(sta)); //出栈
for (int i = 0; i < 10; i++) {//连续压栈
push(sta, i);
}
printf("%d\n", pop(sta));
return 0;
}
链栈
定义： 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针
链栈存储单元：
typedef int datatype;
typedef struct mystack
{
datatype data;//栈顶指针存放栈长，其它存放元素数据
mystack* next;
}MyStack;
例：
链栈特点：
- 链式栈无栈满问题，空间可扩充
- 插入与删除仅在栈顶处执行
- 链式栈的栈顶在链头
- 适合于多栈操作
压栈算法：
其实就是上一篇文章所讲的单链表的头插法，不断更新栈顶指针指向的节点。
void push(MyStack* top, datatype element)//压栈
{
MyStack* sta = (MyStack*)malloc(sizeof(MyStack));//为新元素分配内存，创造节点
sta->data = element;
sta->next = NULL;
sta->next = top->next; //连接新节点与原栈顶节点
top->next = sta; //更新栈顶节点
top->data++; //更新栈长
}
完整代码
typedef int datatype;
typedef struct mystack
{
datatype data;
mystack* next;
}MyStack;
MyStack* initstack()//创建空栈
{
MyStack* top = (MyStack*)malloc(sizeof(MyStack));
top->data = -1;
top->next = NULL;
return top;
}
bool stackempty(MyStack* top)//判断栈空
{
return top->data == -1;
}
void push(MyStack* top, datatype element)//压栈
{
MyStack* sta = (MyStack*)malloc(sizeof(MyStack));
sta->data = element;
sta->next = NULL;
sta->next = top->next;
top->next = sta;
top->data++;
}
datatype pop(MyStack* top)//出栈
{
if (stackempty(top)) {
printf("栈空，出栈失败！！！");
return NULL;
}
else {
datatype element;
MyStack* sta;
sta = top->next; //取栈顶节点
element = sta->data;
top->next = sta->next; //删除栈顶元素
top->data--; //更新栈长
free(sta); //释放删除的节点所占内存
return element;
}
}
datatype stacktop(MyStack* top)//取栈顶元素
{
if (stackempty(top)) {
printf("栈空，取出失败！！！");
return NULL;
}
else {
return top->next->data;
}
}
int main()//主函数只给出初始化和部分测试代码，可自己在主函数添加具体测试调用函数
{
MyStack* top = initstack(); //创建空链栈
printf("%d\n",top->data);
if (stackempty(top)) //判断栈空
printf("栈空！！！\n");
else
printf("栈不空！！！\n");
push(top, 10); //将10压栈
printf("%d\n", stacktop(top));
printf("%d\n", pop(top)); //弹出栈顶指向的节点元素
for (int i = 0; i < 10; i++) { //连续压栈
push(top, i);
}
printf("%d\n", stacktop(top));
return 0;
}
小结： 栈数据结构理解起来并不是太难，但是要熟练运用还是有一定难度的，要多练哦！
队列
定义： 队列(Queue) 是一种只在表的一端进行插入，而在另一端进行删除的数据结构。
- 队头(front) 允许删除的一端，永远指向第一个元素前一个位置。
- 队尾(rear) 允许插入的一端，永远是指向队列最后一个元素
- 先进先出(First In First Out)的线性表，简称FIFO表
- 空队列 当队列中没有元素
顺序队列
定义： 队列的顺序存储结构简称顺序队列
存储结构：
typedef int datatype;
#define MyQueuesize 10
typedef struct mystack
{
datatype data[MyQueuesize] = { 0 };
int front;
int rear;
}MyQueue;
顺序队列特点：
- 队列中亦有上溢和下溢现象。
- 此外，顺序队列中还存在“假上溢” 现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
队尾指针为5，队头指针为1，此时尾指针已经指向了顺序队列最后一个元素，但可以看到0，1两个
并没有被使用，此时就为假上溢。
部分操作代码：
void initQueue(MyQueue* que)//创建空队列
{
que->front = -1;
que->rear = -1;
}
bool Queueempty(MyQueue* que)//判断队空
{
return que->front == que->rear;
}
bool Queuefull(MyQueue* que)//判断队满
{
return que->rear == MyQueuesize - 1;
}
循环队列
为了解决假上溢问题，引进循环队列，即把向量空间想象为一个首尾相接的圆环，在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MAXNUM-1）时，其加1操作的结果是指向向量的下界0。
但是引进的循环队列又出现了新的问题，看图：
即队空和队满的时都满足q->front==q->rear，我们无法利用这个条件判断队空还是队满！！！该怎么解决这个问题呢？有两种方法：
- 少用一个数据元素空间，以队尾指示器加 l等于队头指示器判断队满，即队满条件为:
(q-> rear+l)％MAXNUM=q->front - 使用一个计数器记录队列中元素的总数（实际上是队列长度）。
第一种方法示例代码：
bool Queueempty(MyQueue* que)//判断队空
{
return que->front == que->rear;
}
bool Queueempty(MyQueue* que)//判断队满
{
return (que->rear + 1) % MyQueuesize == que->front;
}
第二种方法示例代码：
typedef int datatype;
#define MyQueuesize 10
typedef struct mystack //存储结构
{
datatype data[MyQueuesize] = { 0 };
int front;
int rear;
int count;
}MyQueue;
bool Queueempty(MyQueue* que)//判断队空
{
return que->count == 0;
}
bool Queuefull(MyQueue* que)//判断队满
{
return que->count == MyQueuesize ;
}
好了这个问题顺利解决！
循环队列的其他操作代码：
void enterQueue(MyQueue* que, datatype element)//入队
{
if (Queuefull(que)) {
printf("队列已满，入队失败！！！\n");
}
else {
que->rear = (que->rear + 1) % MyQueuesize;
que->count++;
que->data[que->rear] = element;
printf("入队成功！\n");
}
}
datatype deletQueue(MyQueue* que) //出队列
{
if (Queueempty(que)) {
printf("队列已空，出队失败！！！\n");
return NULL;
}
else {
que->front = (que->front + 1) % MyQueuesize;
que->count--;
datatype element = que->data[que->front]; //取队头元素
que->data[que->front] = 0; //删除队头元素
printf("出队成功！\n");
return element;
}
}
int main() //主函数只给出初始化和部分测试代码，可自己在主函数添加具体测试调用函数
{
MyQueue* que = (MyQueue*)malloc(sizeof(MyQueue));
return 0;
}
链队列
定义： 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。
存储结构：
将头指针与尾指针封装在一个结构体中便于操作。
typedef int datatype;
typedef struct myQueue //元素节点
{
datatype data;
myQueue* next;
}MyQueue;
typedef struct queue //头指针尾指针
{
myQueue* front;
myQueue* rear;
}myqueue;
判断队空
链队队空条件是pointer->front->next == NULL && pointer->rear->next == NULL而不是pointer->front == pointer->rear这是因为当队空的时候pointer->front和pointer->rear的值不一样。
原因： 如上图所示，当创建空链队时，队列头指针、尾指针都指向上图中黑色节点（这个黑色节点相当于顺序队列的-1，是一个初始节点），当链队列添加元素后尾指针会改变它指向的节点，此时
pointer->rear的值是它指向的尾结点的地址。而当队列删除元素时，改变的是黑色节点的next指针（这样做是为了使头指针满足它的特点，具体看上边队列特点），这样pointer->front的值永远是黑色节点的地址。所以pointer->front和pointer->rear的值不一样，不能作为判断队空的条件。
bool Queueempty(myqueue* pointer)//判断队空
{
return pointer->front->next == NULL && pointer->rear->next == NULL;
}
出队列：
此功能需要注意的就是当队列只剩一个元素时，即pointer->front->next == pointer->rear，而你要删除此元素，就需要先改变尾指针指向的节点，再删除，释放最后一个元素节点的内存。因为如果你不改变的话，则尾指针是指向最后一个元素节点的，而你删除释放最后一个元素节点的内存后，此时pointer->rear->next是一个野指针（野指针的危害就不用我说了吧！！！），会导致程序无法正常运行！！！
datatype deletQueue(myqueue* pointer)
{
MyQueue* p;
if (Queueempty(pointer)) {
printf("队列已空，出队失败！！！\n");
return NULL;
}
else {
p = pointer->front->next;
if (p == pointer->rear) {
pointer->rear = pointer->front;
pointer->front->next = NULL;
}
datatype element = p->data;
pointer->front->next = p->next;
free(p);
printf("出队成功！\n");
return element;
}
}
其它操作示例代码
#include<stdio.h>
typedef int datatype;
typedef struct myQueue //元素节点
{
datatype data;
myQueue* next;
}MyQueue;
typedef struct queue //头指针尾指针
{
myQueue* front;
myQueue* rear;
}myqueue;
void initQueue(myqueue* pointer)//创建空队列
{
pointer->front = (MyQueue*)malloc(sizeof(MyQueue));
pointer->rear = pointer->front;
pointer->front->next = NULL;
}
void enterQueue(myqueue* pointer, datatype element)//入队
{
MyQueue* que = (MyQueue*)malloc(sizeof(MyQueue));
que->data = element;
que->next = NULL;
pointer->rear->next = que;
pointer->rear = que;
printf("入队成功！\n");
}
int main() //主函数只给出初始化和部分测试代码，可自己在主函数添加具体测试调用函数
{
myqueue* pointer = (myqueue*)malloc(sizeof(myqueue));
initQueue(pointer);
return 0;
}
栈和队列讲到这里就结束了。理解后还是需要多练习啊。也希望我的这篇博客能够帮助到你！同时也欢迎各位朋友们评论留言，数据结构系列博客会持续更新，一起加油啊！冲冲冲！！！
这篇关于数据结构：栈与队列奇妙之旅（图文带你欣赏栈和队列的魅力）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
