数据结构:栈与队列奇妙之旅(图文带你欣赏栈和队列的魅力)

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,我们无法利用这个条件判断队空还是队满!!!该怎么解决这个问题呢?有两种方法:

  1. 少用一个数据元素空间,以队尾指示器加 l等于队头指示器判断队满,即队满条件为:
    (q-> rear+l)%MAXNUM=q->front
  2. 使用一个计数器记录队列中元素的总数(实际上是队列长度)。

第一种方法示例代码:

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->frontpointer->rear的值不一样。

原因: 如上图所示,当创建空链队时,队列头指针、尾指针都指向上图中黑色节点(这个黑色节点相当于顺序队列的-1,是一个初始节点),当链队列添加元素后尾指针会改变它指向的节点,此时pointer->rear的值是它指向的尾结点的地址。而当队列删除元素时,改变的是黑色节点的next指针(这样做是为了使头指针满足它的特点,具体看上边队列特点),这样pointer->front的值永远是黑色节点的地址。所以pointer->frontpointer->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;
}

栈和队列讲到这里就结束了。理解后还是需要多练习啊。也希望我的这篇博客能够帮助到你!同时也欢迎各位朋友们评论留言,数据结构系列博客会持续更新,一起加油啊!冲冲冲!!!



这篇关于数据结构:栈与队列奇妙之旅(图文带你欣赏栈和队列的魅力)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程