---

前言

本期和大家分享的是栈、队列以及表的特点以及其数据结构的具体是实现过程，这几种数据结构在工程应用中极其广泛，所以必须理解其本质以及每个数据结构之间的区别以及联系；下面就来具体看一下吧！

一、栈、队列和表之间的区别？

栈、队列和表的区别:(1)表允许操作结构中任意一个元素；(2)栈、队列是一种特殊的表状结构,只允许访问表两端的元素；

二 、栈

1.基本概念

	(1)栈顶:允许入栈出栈的一端称为栈顶(2)栈底:不允许入栈出栈的一端称为栈底(3)入栈:数据放入栈中(4)出栈:从栈中取出数据栈的特点：先进后出、后进先出	FILO满栈：指针指向有内容的地址。因此，进栈是先移动指针再存；出栈是先出数据再移动指针空栈：指针指向没有内容的地址。因此，进栈是先存再移动指针；出栈是先移动指针再出数据减栈：指针向地址减小的方向移动。因此，进栈指针向下移动；出栈是指针向上移动增栈：指针向地址增加的方向移动。因此，进栈指针向上移动；出栈是指针向下移动

满减栈：指针一开始指向有内容的地址，进栈先向下移动指针后再将内容存进去，出栈先移动数据再向上移动指针。
满增栈：指针一开始指向有内容的地址，进栈先向上移动指针后再将内容存进去，出栈先移动数据再向下移动指针。
空减栈：指针一开始指向没有内容的地址，进栈先将内容存进去后再向下移动指针，出栈先向上移动指针再移动数据。
空增栈：指针一开始指向没有内容的地址，进栈先将内容存进去后再向上移动指针，出栈先向下移动指针再移动数据。

2.顺序栈

顺序栈的实现如下：
还是先来介绍一下数据结构的定义：
理解顺序栈呢，首先必须理解顺序表，顺序表的存储结构是连续的，所以顺序栈的存储方式也是连续的，其实就是在数组存储的基础上加上了栈先进后出的逻辑顺序；

#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef int DataType;typedef struct stack 
{DataType *pData;int Top;int tLen;
}SeqStack;extern SeqStack *CreateSeqStack(int MaxLen);
extern int IsEmptySeqStack(SeqStack *pTmpStack);
extern int IsFullSeqStack(SeqStack *pTmpStack);
extern int PushSeqStack(SeqStack *pTmpStack, DataType TmpData);
extern DataType PopSeqStack(SeqStack *pTmpStack);
extern int DestroySeqStack(SeqStack **ppTmpStack);#endif

具体的代码实现过程：

#include "seqstack.h"
/* 创建一个顺序栈 */
SeqStack *CreateSeqStack(int MaxLen)
{SeqStack *pTmpStack = NULL;pTmpStack = malloc(sizeof(SeqStack));if (NULL == pTmpStack){perror("fail to malloc");return NULL;}pTmpStack->Top = 0;pTmpStack->tLen = MaxLen;								//栈的总容量pTmpStack->pData = malloc(sizeof(DataType) * MaxLen);	//可以和顺序表空间申请对比一下(完全一致)if (NULL == pTmpStack->pData){perror("fail to malloc");return NULL;}return pTmpStack;
}

/* 判断栈是否为空 */
int IsEmptySeqStack(SeqStack *pTmpStack)
{return pTmpStack->Top == 0 ? 1 : 0;
}/* 判断栈是否为满 */
int IsFullSeqStack(SeqStack *pTmpStack)
{return pTmpStack->Top == pTmpStack->tLen ? 1 : 0;
}

/* 压栈 */
int PushSeqStack(SeqStack *pTmpStack, DataType TmpData)
{if (IsFullSeqStack(pTmpStack)){return -1;}pTmpStack->pData[pTmpStack->Top] = TmpData;pTmpStack->Top++;return 0;
}

/* 出栈 */
DataType PopSeqStack(SeqStack *pTmpStack)
{if (IsEmptySeqStack(pTmpStack)){return -1;}pTmpStack->Top--;return pTmpStack->pData[pTmpStack->Top];
}

/* 销毁栈空间 */
int DestroySeqStack(SeqStack **ppTmpStack)
{free((*ppTmpStack)->pData);free(*ppTmpStack);*ppTmpStack = NULL;return 0;
}

3.链式栈

链式栈就是通过链表来实现一个栈的操作；栈的结构是先进后出，所以可以使用尾插法将数据入栈(压栈)，然后在头节点处可以进行出栈操作，从而实现一个链式栈的结构；链式栈的原理是建立在链表的原理上的，所以存储方式是通过链表来存储的；
链式栈的实现过程如下：
头文件：

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int DataType;		//存储的数据类型typedef struct node			//存储数据节点的类型 
{DataType Data;struct node *pNext;}StackNode;typedef struct stack		//栈头
{StackNode *pHead;		//管理整个栈的头指针int cLen;				//当前长度int tLen;				//最大长度}LinkStack;extern LinkStack *CreateLinkStack(int MaxLen);
extern int IsEmptyLinkStack(LinkStack *pTmpStack);
extern int IsFullLinkStack(LinkStack *pTmpStack);
extern int PushLinkStack(LinkStack *pTmpStack, DataType TmpData);
extern DataType PopLinkStack(LinkStack *pTmpStack);
extern int DeatroyLinkStack(LinkStack **pTmpStack);#endif

具体实现过程：

#include "linkstack.h"
/* 创建一个链式栈 */
LinkStack *CreateLinkStack(int MaxLen)
{LinkStack *pTmp = NULL;pTmp = malloc(sizeof(LinkStack));if (NULL == pTmp){perror("fail to malloc");return NULL;}pTmp->pHead = malloc(sizeof(StackNode) * MaxLen);if (NULL == pTmp->pHead){perror("fail to malloc");return NULL;}pTmp->pHead->pNext = NULL;pTmp->cLen = 0;pTmp->tLen = MaxLen;return pTmp;
}

/* 判断栈是否为空 */
int IsEmptyLinkStack(LinkStack *pTmpStack)
{return pTmpStack->cLen == 0;
}

/* 判断栈是否为满 */
int IsFullLinkStack(LinkStack *pTmpStack)
{return pTmpStack->cLen == pTmpStack->tLen; 
}

/* 压栈 */
int PushLinkStack(LinkStack *pTmpStack, DataType TmpData)
{if (IsFullLinkStack(pTmpStack)){printf("栈区空间已满\n");return -1;}StackNode *pTmpNode = NULL;pTmpNode = malloc(sizeof(LinkStack));if (NULL == pTmpNode){perror("fail to malloc");}pTmpNode->Data = TmpData;pTmpNode->pNext = pTmpStack->pHead->pNext;pTmpStack->pHead->pNext = pTmpNode;pTmpStack->cLen++;return 0;
}

/* 出栈 */
DataType PopLinkStack(LinkStack *pTmpStack)
{if (IsEmptyLinkStack(pTmpStack)){printf("栈区空间已空\n");}StackNode *pTmpNode = NULL;DataType TmpData;pTmpNode = pTmpStack->pHead->pNext;pTmpStack->pHead->pNext = pTmpNode->pNext;pTmpStack->cLen--;TmpData = pTmpNode->Data;free(pTmpNode);return TmpData;
}

/* 释放栈区空间(销毁栈区) */
int DeatroyLinkStack(LinkStack **pTmpStack)
{StackNode *pTmpNode = NULL;StackNode *pFreeNode = NULL;pTmpNode = (*pTmpStack)->pHead;pFreeNode = pTmpNode;while (pTmpNode != NULL){pTmpNode = pTmpNode->pNext;free(pFreeNode);pFreeNode = pTmpNode;}free(*pTmpStack);*pTmpStack = NULL;return 0;
}

---

总结

本期和大家主要分享的栈的基本概念；在学习了顺序表和链式表的基础上，将顺序表和链式表的数据结构套用在栈中，以此实现了顺序栈和链式栈，是两种不同方式实现的栈的这种数据结构；顺序栈的缺点是插入元素的个数是有限的，但是链式栈继承了链表的优势，在理论上来讲它的数据存储个数是无限的（只要系统空间够用）；本期的分享就到这里结束啦，希望小伙伴们练习起来哦！
最后，各位小伙伴们如果喜欢我的分享可以点赞收藏哦，你们的认可是我创作的动力，一起加油！