栈和队列（一）

2023-11-26 13:17:28

栈和队列（一）

绪论
栈的数据类型
栈的初始化
栈的判断
- 栈的判空
- 栈的判满
入栈操作
未完待续：感谢各位的支持！

绪论

栈和队列本质上也是线性表，因此具有线性表的基本性质，关于线性表的性质在**单链表（一）**一文中有介绍，这里就不再赘述

那么 栈和队列 和普通的数组和链表有什么区别呢，就是他们的的操作是受限的，我们之前谈到的单链表是可以在任意位置操作的。但是栈只能在序列的末尾进行操作，队列只能在序列的两端进行操作

以上是栈和队列的逻辑结构，接下来讨论物理结构，根据顺序存储和链式存储，有以下几种类型的栈和队列：

本文先只讨论栈，讨论完物理结构以后，就是栈的基本操作，一般来说有以下的基本操作：

栈的数据类型

首先，栈只能在序列的末端入栈和出栈，因此我们需要知道末端元素的位置；如果是链栈，还需要知道底端的位置。这是因为顺序栈是数组来实现的，数组的底端默认是第一个内存空间了。

所以我们要创建一个控制表，用这个控制表来控制一个数组或者是链表的操作，所以我们把创建控制表称为栈的初始化。

但是在初始化前，首先要了解栈的数据类型。顺序栈和链栈由哪些部分组成，这样我们在初始化操作才可以清晰。

顺序栈需要有一个单元存放开辟的数组空间的指针，有一个单元存放顶端元素的位置，这样的话才可以只对顶端元素进行操作：

链栈首先要有结点类型，每一个结点都有数据域和指针域。为了体现栈这个逻辑结构。因此还要一个链栈控制表控制链表的顶端和底端 （这里的底端代表了单链表的头结点）：

//顺序栈的数据类型定义
#define MAXSIZE 5
typedef int DataType;
typedef struct SqStack{
	DataType *data;
	int top;
}SQSTACK,*PSQSTACK;

//链栈的数据类型定义
typedef int DataType;
typedef struct Node{
	DataType data;
	struct Node *next;
}NODE,*PNODE;

typedef struct Stack{
	PNODE top;
	PNODE bottom;
}STACK,*PSTACK;

栈的初始化

所谓初始化，就是从无到有的过程。以上的数据类型的图只是展现了栈如果存在逻辑上的图是怎么样的，但实际上如果不初始化，那么那些内存空间都是没有分配的。就好像 i n t int int 类型是存在的，但是如果你不分配空间存放 i n t int int 类型，那么在内存空间（实际上）还是不存在的。

//顺序栈的初始化
PSQSTACK Init_Sqstack()
{
	PSQSTACK SQ = (PSQSTACK)malloc(sizeof(SQSTACK));//开辟栈的控制表
	if(SQ == NULL)
	{
		printf("分配空间失败！");
		return NULL;
	}
	SQ->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);//开辟数组空间存放元素
	if(SQ->data == NULL)
	{
		printf("初始化失败！");
		exit(-1);//如果数组分配失败，则退出程序
	}
	SQ->top = 0;//将top置为 0 
	return SQ;
}

//链栈的初始化
PSTACK Init_Sqstack()
{
	PSTACK SQ = (PSTACK)malloc(sizeof(STACK));//开辟链栈控制表
	if(SQ!=NULL)
	{
		SQ->top = (PNODE)malloc(sizeof(NODE));//开辟结点类型
		SQ->bottom = SQ->top;//底部指向顶部
		SQ->top->next = NULL;//底部（顶部）的next指向空
	}
	else
	{
		printf("分配空间失败！\n");
	}
	return SQ;//如果为NULL则返回NULL
}

栈的判断

为什么需要栈的判断呢，是因为之后有很多操作需要首先判断才能进行操作，因此把栈的判断也定义为接口，方便以后写接口的时候不用重复写代码。

栈的判空

对于顺序栈来说，如果 t o p top top 是 0 0 0 的话，则可以判定该栈是空栈
对于链栈来说，如果 t o p top top 和 b o t t o m bottom bottom 指向同一个结点的话，则说明他们都指向头结点，则可以判断该链栈是空栈

对于以上两种情况的图解，我们可以在栈的初始化里面看到。因为当栈初始化完成的时候是没有任何元素在栈里面的，因此初始化完成后的状态就是栈空的时候的状态。

//顺序栈的判空
bool Empty_Stack(PSQSTACK SQ)
{
	if(SQ->top == 0)
	{
		return true;
	}
	return false;
}

//链栈的判空
bool Empty_Stack(PSTACK SQ)
{
	if(SQ->top == SQ->bottom)
	{
		return true;
	}
	else
	{
		return false;
	}
}

栈的判满

首先链栈是链式存储，因此只要分配内存成功就可以继续存储，所以链栈没有满栈的情况。

顺序栈是用数组来存储元素的，而数组有预定义的大小，因此当数组存满元素的时候，该栈就满了。

//顺序栈判满
bool Full_Stack(PSQSTACK SQ)
{
	if(SQ->top == MAXSIZE)
	{
		return true;
	}
	else
		return false;
}

入栈操作

首先我们在一开始分析逻辑结构的时候便明确，栈只能在序列的末端进行操作，所以添加元素入栈的时候，只能在栈的 t o p top top 端进行操作：

而且在入栈之前，特别是顺序栈，要判断栈有没有满，如果栈满了就不可以继续添加元素入栈了。

链栈入栈之前，首先要创造结点，把待入栈的值放入结点的数据域中，然后再进行一系列操作就可以入栈：

首先用 p n e w pnew pnew 指针开辟一个新结点，再把 v a l val val 值存放到新结点的数据域
然后 p n e w pnew pnew 指针的 n e x t next next 域指向原链表的 t o p top top 结点
最后让 t o p top top 指针指向 p n e w pnew pnew结点即可

//顺序栈入栈
bool Push_Stack(PSQTACK PS,DataType val)
{
	if(Full_Stack(PS))
	{
		printf("The Stack is Full!\n");//栈满则入栈失败
		return false;
	}
	else
	{
		PS->data[PS->top] = val;//首先当前位置存储元素
		PS->top++;//将top移动到下一个位置
		return true;
	}
}

//链栈入栈
bool Push_Stack(PSTACK SQ,DataType val)
{
	PNODE pnew = (PNODE)malloc(sizeof(NODE));//开辟结点
	if(pnew == NULL)
	{
		printf("分配结点空间失败！\n");
		return false;
	}
	pnew->data = val;//数据域存放数据
	pnew->next = SQ->top;//pnew的next指向top结点
	SQ->top = pnew;//top指针指向pnew，作为新的top结点
	return true;
}

码农公寓