数据结构|??数据结构之栈（图文版详解）??
目录
一，写在前面
二，栈的定义
1，栈的定义
2，进栈出栈变化形式
三，栈的抽象数据类型
四，栈顺序存储结构及实现
1，栈的顺寻存储结构
2，栈的顺序存储结构——进栈操作
3，栈的顺序存储结构——出栈操作
五，两栈共享空间
六，栈的链式存储结构及实现
1，栈的链式存储结构
2，栈的链式存储结构——进栈操作
3， 栈的链式存储结构——出栈操作
七，全部代码
1，顺序栈
2，两栈共享空间
3，链栈
一，写在前面
不知道大家有投有玩过手枪，估计都投有。现在和平年代，上哪去玩这种危险的 真东西，就是仿真玩具也大都被限制了.我高中在军训时，也算是一次机会，几个老兵和我们学生聊天，让我们学习了下关于枪的知识。
在你准备用枪的时候，那基本到了不是你死就是我亡的时刻，突然手枪明明有子弹却打不出来，这不是要命吗?而左轮手枪就不存在这问题，这一颗不行，转到下颗就可以 了，人总不会倒霉到六颗全是臭弹， 当然，后来子弹质量基本过关了，由于弹夹可以 8颗颗甚至20颗子弹，比左轮手枪的只能放6颗子弹要多，所以后来普及率更高的弹夹手枪。
文章图片
文章图片
二，栈的定义 1，栈的定义
在我们软件应用 ，栈这种后进先出数据结构的应用是非常普遍的。比如你用浏览器上网时不管什么浏览器都有 个"后退"键，你点击后可以接访问顺序的逆序加载浏览过的网页。比如你本来看着新闻好好的，突然看到有个链接说，有个可以让 你年薪100万的工作，你毫不犹豫点击它， 跳转进去一看，这都是啥呀，具体内容我 也就不说了，骗人骗得一点水平都没有 时你还想回去继续看新闻 就可以点击左 上角的后退 。即使你从一个网页开始 连续点了几十个链接跳转 你点"后退'，页面跳转到前一步。
文章图片
很多类似的软件，比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作，也是用栈这种方式来实现的，当然不同的软件具体实现代会有很 大差异，不过原理其实都是一样的。
栈( stack )是限定仅在表尾进行插入和删除操作的线性表
我们把允许插入和删除的一端称为栈顶 top ，另一端称为栈底 bottom。不含任何数据元素的栈称为空栈，又称为后进先出 （Last In Filrst Out） 的线性表，简 LlFO 结构。
栈的插入操作，叫作进栈，也称压栈、类似子弹入弹夹。
栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹。
文章图片
2，进栈出栈变化形式
最先进栈的元素，是不是就只能是最后出栈呢?三，栈的抽象数据类型
举例来说，如果我们现在是有3个整型数字元素 1，2.3以次进栈，会有哪些出栈次序呢?
第一种: 1，2，3进，再 3，2，1出。这是最简单的最好理解的 一种，出栈次序为 321 。
第二种: 1进， 1出， 2进,2出， 3进， 3出。也就是进一 就出一个，出 枝次序为 123 。
第三种: 1进，2进， 2出， 1出， 3进，3出。出栈次序为 213。
第四种：1进，1出，2进，3进，3出，2出。出栈次序为132。
第五种：1进，2进，2出，3进，3出，1出。出栈次序为231。
从这个简单的例子就能看出，只是3个元素,就有5种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。这个知识点一定要弄明白。 从这个简单的例子就能看出，只是3个元素，就有5种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的.这个知识点一定要弄明白。
对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为 push和 pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。 对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化.特别是插入和删除操作，我们改名为推和POP，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。
ADT 栈(stack)
Data同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
operationInitStack(*S)：初始化操作，建立一个空栈S.
DestoryStack (*S)：若栈存在，则销毁它。
ClearStack(*s)：将栈清空。
StackEmpty (s):若栈为空，返回true，否则返回false。
GetTop (s, *e):若栈存在且非空，用e返回S的栈顶元素。
Push(*S,e):若栈S存在，插入新元素e到栈s中并威为栈顶元素。
Pop (*s,*e):删除栈S中栈顶元素,并用e返回其值。
StackLength(S):返回栈s的元素个数。endADT四，栈顺序存储结构及实现 1，栈的顺寻存储结构
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，想想看,对于栈这种只能一头插入删除的线性表来说,用数组哪一端来作为栈顶和栈底比较好?
对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
我们定义一个 top变量来指示栈顶元素在数组中的位置,这 top就如同中学物理学过的游标卡尺的游标，如图，它可以来回移动，意味着栈顶的 top可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize，则栈顶位置top 必须小于 StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为 top等于一1。
文章图片
栈的结构定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int SElemType;
/* SElemType类型根据实际情况而定，这里假设为int *//* 顺序栈结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top;
/* 用于栈顶指针 */
}SqStack;
若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如图 若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如图
文章图片
2，栈的顺序存储结构——进栈操作
文章图片
/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE -1) /* 栈满 */
{
return ERROR;
}
S->top++;
/* 栈顶指针增加一 */
S->data[S->top]=e;
/* 将新插入元素赋值给栈顶空间 */
return OK;
}3，栈的顺序存储结构——出栈操作
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==-1)
return ERROR;
*e=S->data[S->top];
/* 将要删除的栈顶元素赋值给e */
S->top--;
/* 栈顶指针减一 */
return OK;
}两者没有涉及到任何循环语句,因此时间复杂度均是0(1)。五，两栈共享空间
其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。 其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题.不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦.对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
文章图片
我们的做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素,就是两端点向中间延伸。 我们的做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处.这样，两个栈如果增加元素，就是两端点向中间延伸。
其实关键思路是:它们是在数组的两端，向中间靠拢。top1和 top2是栈1和栈2的栈顶指针,可以想象，只要它们俩不见面,两个栈就可以一直使用。
从这里也就可以分析出来，栈1为空时，就是 top1等于-1时; 而当top2等于n时，即是栈2为空时,那什么时候栈满呢?
想想极端的情况，若栈2是空栈,栈1的 top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时,为栈2满。但更多的情况，其实就是我刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即 top1 + 1 == top2为栈满。
两栈共享空间的结构的代码如下: 两栈共享空间的结构的代码如下：
/* 两栈共享空间结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top1;
/* 栈1栈顶指针 */
int top2;
/* 栈2栈顶指针 */
}SqDoubleStack;
对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下:
/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
if (S->top1+1==S->top2) /* 栈已满，不能再push新元素了 */
return ERROR;
if (stackNumber==1)/* 栈1有元素进栈 */
S->data[++S->top1]=e;
/* 若是栈1则先top1+1后给数组元素赋值。 */
else if (stackNumber==2) /* 栈2有元素进栈 */
S->data[--S->top2]=e;
/* 若是栈2则先top2-1后给数组元素赋值。 */
return OK;
}因为在开始已经判断了是否有栈满的情况，所以后面的 top1+1或top2-1是不担心溢出问题的。
对于两栈共享空间的pop方法,参数就只是判断栈1栈2的参数stackNumber,代码如下:
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if (stackNumber==1)
{
if (S->top1==-1)
return ERROR;
/* 说明栈1已经是空栈，溢出 */
*e=S->data[S->top1--];
/* 将栈1的栈顶元素出栈 */
}
else if (stackNumber==2)
{
if (S->top2==MAXSIZE)
return ERROR;
/* 说明栈2已经是空栈，溢出 */
*e=S->data[S->top2++];
/* 将栈2的栈顶元素出栈 */
}
return OK;
}事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时,也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。有人赚钱，就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。六，栈的链式存储结构及实现 1，栈的链式存储结构
讲完了栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。想想看，栈只是栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?由于单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢，所以比较好的办法是把栈顶放在单链表的头部(如图所示)。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。
文章图片
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
但对于空栈来说，链表原定义是头指针指向空,那么链栈的空其实就是 top=NULL的时候。 但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=空的时候。
代码如下：
/* 链栈结构 */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;
2，栈的链式存储结构——进栈操作
对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如图4所示代码如下。
文章图片
/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data=https://www.it610.com/article/e;
s->next=S->top;
/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
S->top=s;
/* 将新的结点s赋值给栈顶指针，见图中② */
S->count++;
return OK;
}3， 栈的链式存储结构——出栈操作
至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位，最后释放p即可，如图所示。
文章图片
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top;
/* 将栈顶结点赋值给p，见图中③ */
S->top=S->top->next;
/* 使得栈顶指针下移一位，指向后一结点，见图中④ */
free(p);
/* 释放结点p */
S->count--;
return OK;
}七，全部代码 1，顺序栈
#include "stdio.h"
#include "stdlib.h"#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;
typedef int SElemType;
/* SElemType类型根据实际情况而定，这里假设为int *//* 顺序栈结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top;
/* 用于栈顶指针 */
}SqStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}/*构造一个空栈S */
Status InitStack(SqStack *S)
{
/* S.data=https://www.it610.com/article/(SElemType *)malloc(MAXSIZE*sizeof(SElemType));
*/
S->top=-1;
return OK;
}/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{
S->top=-1;
return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqStack S)
{
if (S.top==-1)
return TRUE;
else
return FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(SqStack S)
{
return S.top+1;
}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{
if (S.top==-1)
return ERROR;
else
*e=S.data[S.top];
return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE -1) /* 栈满 */
{
return ERROR;
}
S->top++;
/* 栈顶指针增加一 */
S->data[S->top]=e;
/* 将新插入元素赋值给栈顶空间 */
return OK;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==-1)
return ERROR;
*e=S->data[S->top];
/* 将要删除的栈顶元素赋值给e */
S->top--;
/* 栈顶指针减一 */
return OK;
}/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{
int i;
i=0;
while(i<=S.top)
{
visit(S.data[i++]);
}
printf("\n");
return OK;
}int main()
{
int j;
SqStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;
j<=10;
j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
return 0;
}2，两栈共享空间
#include "stdio.h"
#include "stdlib.h"#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;
typedef int SElemType;
/* SElemType类型根据实际情况而定，这里假设为int *//* 两栈共享空间结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top1;
/* 栈1栈顶指针 */
int top2;
/* 栈2栈顶指针 */
}SqDoubleStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}/*构造一个空栈S */
Status InitStack(SqDoubleStack *S)
{
S->top1=-1;
S->top2=MAXSIZE;
return OK;
}/* 把S置为空栈 */
Status ClearStack(SqDoubleStack *S)
{
S->top1=-1;
S->top2=MAXSIZE;
return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqDoubleStack S)
{
if (S.top1==-1 && S.top2==MAXSIZE)
return TRUE;
else
return FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(SqDoubleStack S)
{
return (S.top1+1)+(MAXSIZE-S.top2);
}/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
if (S->top1+1==S->top2) /* 栈已满，不能再push新元素了 */
return ERROR;
if (stackNumber==1)/* 栈1有元素进栈 */
S->data[++S->top1]=e;
/* 若是栈1则先top1+1后给数组元素赋值。 */
else if (stackNumber==2) /* 栈2有元素进栈 */
S->data[--S->top2]=e;
/* 若是栈2则先top2-1后给数组元素赋值。 */
return OK;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if (stackNumber==1)
{
if (S->top1==-1)
return ERROR;
/* 说明栈1已经是空栈，溢出 */
*e=S->data[S->top1--];
/* 将栈1的栈顶元素出栈 */
}
else if (stackNumber==2)
{
if (S->top2==MAXSIZE)
return ERROR;
/* 说明栈2已经是空栈，溢出 */
*e=S->data[S->top2++];
/* 将栈2的栈顶元素出栈 */
}
return OK;
}Status StackTraverse(SqDoubleStack S)
{
int i;
i=0;
while(i<=S.top1)
{
visit(S.data[i++]);
}
i=S.top2;
while(i=MAXSIZE-2;
j--)
Push(&s,j,2);
}printf("栈中元素依次为：");
StackTraverse(s);
printf("当前栈中元素有：%d \n",StackLength(s));
Pop(&s,&e,2);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
for(j=6;
j<=MAXSIZE-2;
j++)
Push(&s,j,1);
printf("栈中元素依次为：");
StackTraverse(s);
printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
return 0;
} 3，链栈
#include "stdio.h"
#include "stdlib.h"#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;
typedef int SElemType;
/* SElemType类型根据实际情况而定，这里假设为int *//* 链栈结构 */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}/*构造一个空栈S */
Status InitStack(LinkStack *S)
{
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
if(!S->top)
return ERROR;
S->top=NULL;
S->count=0;
return OK;
}/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{
LinkStackPtr p,q;
p=S->top;
while(p)
{
q=p;
p=p->next;
free(q);
}
S->count=0;
return OK;
}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(LinkStack S)
{
if (S.count==0)
return TRUE;
else
return FALSE;
}/* 返回S的元素个数，即栈的长度 */
int StackLength(LinkStack S)
{
return S.count;
}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(LinkStack S,SElemType *e)
{
if (S.top==NULL)
return ERROR;
else
*e=S.top->data;
return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data=https://www.it610.com/article/e;
s->next=S->top;
/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
S->top=s;
/* 将新的结点s赋值给栈顶指针，见图中② */
S->count++;
return OK;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top;
/* 将栈顶结点赋值给p，见图中③ */
S->top=S->top->next;
/* 使得栈顶指针下移一位，指向后一结点，见图中④ */
free(p);
/* 释放结点p */
S->count--;
return OK;
}Status StackTraverse(LinkStack S)
{
LinkStackPtr p;
p=S.top;
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}int main()
{
int j;
LinkStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;
j<=10;
j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
return 0;
}【数据结构|??数据结构之栈（图文版详解）??】
