栈

定义： 栈(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->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;
}

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