从数据结构角度看，栈也属于线性表（当然也满足上一章线性表的特性），是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

因此，栈又被称为后进先出的线性表（简称 LIFO 结构）。

补充：卡特兰数

n个不同元素进栈，则出栈元素不同排列的个数为 $\frac{1}{n+1}C_{2n}^{n}\textrm{}$

2、栈的基本操作

InitStack(&S) : 初始化一个空栈，分配内存空间。

DestroyStack(&S) ：销毁并释放栈S所占用的内存空间。

Push(&S , x) : 进栈，若栈S未满，则将x 加入使之成为新栈顶。

Pop(&S , &x) : 出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S , &x) : 读栈顶元素，若栈S非空，则用x返回栈顶元素。

StackEmpty(S)：判断一个栈S是否为空，若S为空，则返回true,否则返回false；

…………………

这些都会在下文，结合栈的存储结构来实现。

二、栈的顺序存储结构

1、顺序栈的定义

栈的定义：

这里先介绍静态分配的栈实现，动态分配在下面。


#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];  //静态数组存放栈中元素 
	int top;  //栈顶指针 
}SqStack;

栈的初始化：


void InitStack (SqStack &S)
{
	S.top = -1;
}

判断栈空：


bool StackEmpty (SqStack S)
{
	if (S.top == -1) return true; //栈空
	else return false; 
}

2、基本操作（静态vs动态）

进栈：


//进栈操作
bool Push (SqStack &S , ElemType x)
{
    if (S.top() == MaxSize - 1) return false; //栈满，报错（数组下标是从0开始的）
	S.data[++S.top] = x; //指针top先 + 1，新元素再入栈
	return true; 
}

出栈：


//出栈操作 
bool Pop (SqStack &S , ElemType &x)
{
    if (S.top() == -1) return false; //栈空，报错
    x = S.data[S.top--];  //栈顶元素先出栈，指针top再 -1 
	return true; 
}

读栈顶元素：


//读栈顶元素
bool GetTop (SqStack S , ElemType &x)
{
    if (S.top() == -1) return false; //栈空，报错
    x = S.data[S.top];  //栈顶元素出栈
	return true; 
}

⚠️:上述 top 初始化为 -1，指明的是当前栈顶元素位置。而有些时候，题目会将top初始化为0，指明的是下一个可以插入元素的位置，这时上述进栈和出栈操作就有点变化了：


//进栈：
S.data[S.top++] = x
 
//出栈：
x = S.data[--S.top]

动态分配：

栈的定义：


#define MAXSIZE 100  //存储空间初始分配量 
#define Increasesize 10 //为存储空间分配的增量 
typedef struct{
	ElemType *base; //栈底指针 
	ElemType *top; //栈顶指针 
	int stacksize; //当前已分配的存储空间 
} SqStack;

栈的初始化：


void InitStack(SqStack &S)
{
	S.base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    //因为base作为栈底指针，所以要为其分配地址
	S.top = S.base;
	S.stacksize = MAXSIZE;
 }

栈的判空就是：S.top == S.base

进栈操作：


void push(SqStack &S , ElemType e)
{
	if (S.top - S.base >= S.stacksize) //栈满，追加存储空间
	{
	    S.base = (ElemType *)realloc(S.base , (S.stacksize + Increasesize) * sizeof(ElemType));
		S.top = S.base + S.stacksize; //因为重新申请了一片空间，导致base地址位置改变
		S.stacksize += Increasesize;	
	} 
	*S.top++ = e; //先赋值，再 top + 1 
}

⚠️:这里我选择的是用realloc函数，语法简介：

指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。

注意：新的大小可大可小（如果新的大小大于原内存大小，则新分配部分不会被初始化，即数据会保留；如果新的大小小于原内存大小，可能会导致数据丢失，即部分不会保留。并且原来指针所指的存储空间是自动释放，不需要使用free ）

当然只采用malloc 和 free 这两个函数也是一样，这我在讲上一章顺序表的顺序存储结构的IncreaseSize (SeqList &L ，int len) 函数时就写了源码，可以去看看哦。

出栈操作：


bool pop(SqStack &S , ElemType &e)
{
	if (S.top == S.base) //栈空 
	{
		return false;
	}
	e = * --S.top; //先top - 1 ，再赋值 
	return true; 
}

3、共享栈

共享栈：两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间。
两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。

两个栈的栈顶指针都指向栈顶元素，top0 = -1时0号栈为空，top1 = MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0 + 1 = top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值，出栈时则刚好相反。

共享栈的定义：


#define MaxSize 10
typedef struct {
	ElemType data[MaxSize];
	int top0;
	int top1;
}ShStack;

栈的初始化：


void InitShStack (ShStack &S)
{
	S.top0 = -1;
	S.top1 = MaxSize;
}

进栈：


//StackType表示在0号顺序栈插入，还是在1号顺序栈插入 
bool Push (ShStack &S , ElemType x , int StackType) 
{
	if (S.top + 1 == S.top1) return false; //栈满
	if (StackType == 0) {
		S.data[++S.top0] = x;
	} 
	else {
		S.data[--S.top1] = x; 
	}
	return true;
}

出栈：


//StackType表示再那个0号顺序栈 插入，还是在1号顺序栈插入 
bool Pop (ShStack &S , ElemType &x , int StackType) 
{
	if (StackType == 0) {
		if (S.top0 == -1)
		{
			return false; //栈 0已空 
		}
		x = S.data[S.top0--]; //非空即出栈 
	}
	else {
		if (S.top1 == MaxSize)
		{
			return false;
		}
		x = S.data[S.top1++];
	}
	return true;
}

三、栈的链式存储结构

链式栈可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的问题，但是它也需要为每个栈元素分配额外的指针空间用来存放指针域。

上一章讲线性表时，已经着重介绍了单链表，在开始学习下文前，可以先去温习一下：

（点击即可穿越）

规定：链式栈的所以操作都是在单链表的表头进行的（因为给定链式栈以后，我们可以知道头结点的地址，在其后面插入新结点或删除首结点都很方便，且该操作的时间复杂度为O(1)）。

当然带头结点和不带头结点都是一样的，下文主要介绍带头结点：

1、基本操作

链栈的定义：


typedef struct Linknode {
	ElemType data;
	struct Linknode *next;//存储下一个元素的地址（朝栈底方向） 
}node , *LiStack;

链栈的初始化：


void InitLiStack (LiStack &S)
{
	S = (LiStack)malloc(sizeof(node));
	S -> next = NULL;
}

判断链栈是否为空（在不考虑内存溢出的情况下，一般不考虑栈满情况）：


bool LiStackEmpty(LiStack *S)
{
	return (S -> next == NULL);
}

进栈：


void Push (LiStack &S , ElemType x)
{
    //不需要判断是否栈满
	node *t; 
	t = (node *)malloc(sizeof(node));
	t -> data = x;
	//把 t节点添加到头节点的后面 
	t -> next = S -> next;
	S -> next = t;
}

出栈：


 
bool Pop (LiStack &S , ElemType &x)
{
	node *t;//指明要出栈的结点 
	if(S -> next != NULL)//栈不空
	{
		t = S -> next;
		x = t -> data;
		S -> next = t -> next;
		free(t); 
		return true;
	} 
	else
	{
		return false; //栈空
	}
}

销毁链栈：


void DestroyStack(LinkStack &S)
{
	ElemType m;
	while (S -> next != NULL)//不空
	{
		Pop(S); //上面写的Pop函数形参含有出栈的结点值并且返回值为 bool，但这里可以不用 
	} 
	free(S); //删除头结点
	S = NULL; 
}

看到这里，是不是发现和上一章的单链表几乎完全一样，所以你可以先考虑自己独自完成，这样既能检验自己上一章有没有学扎实，又可以熟悉这一章的栈。

当然如果栈的变化在可控范围内,建议使用顺序栈会更好一些，毕竟好写一点 hh。

四、栈的应用

1、用栈解决括号匹配

假设表达式中允许包含三种括号：圆括号、方括号和中括号，其嵌套顺序随意，但必须同类型，且左右匹配。比如（[ ] ()）或者 [ ( [ ] ( [ ] ) ) ] 这些是满足的，但是[ ( ] 或者 [ ( [ ] ) 这些都是不行的。

用栈实现括号匹配的规则：

遇到左括号就入栈
遇到右括号就将栈中的一个左括号出栈看是否匹配

首先来看一个能成功匹配的动图：

不满足括号匹配有这三种情况：

遇到右括号就将栈中的一个左括号出栈，发现不匹配
括号已经全部扫描完了，发现栈中还有未出栈的左括号
当扫描到一个右括号时，发现栈已空，即没有左括号

这里就给出第三种不匹配动图：

但最重要的还是代码实现，你可以先思而后行，先自己敲代码，再来看看正确代码。


bool bracketCheck(char str[] , int length)
{
    SqStack S;
	InitStack (S);
	for (int i = 0 ; i < length ; ++i)
	{
	    if (str[i] == '(' || str[i] == '[' || str[i] == '{' ) //扫描到左括号，入栈 
		{
			Push(S , str[i]);
		}
		else{
			if (StackEmpty(S)) return false;//扫描到右括号，但是当前栈空
			char topelem;  //栈顶元素出栈 
			Pop(S , topelem);
			if (str[i] == ')' && topelem != '(') return false;
			if (str[i] == ']' && topelem != '[') return false;
			if (str[i] == '}' && topelem != '{') return false;
		}	
	}	
	return StackEmpty(S);//最后检索完全部括号后，还要检测此时栈是否为空 
}

上面的InitStack函数、StackEmpty函数、Push函数、Pop函数都一一介绍了哦。

这题既然我们已经知道了length ，所以用栈的顺序存储（建议静态存储就行了）。

2、栈排序

如果给你一个装有元素的栈Stack1，并且里面的元素是乱序的，现在要求你只能格外再定义一个辅助栈Stack2，然后对Stack1进行排序，你如何实现这一过程呢？

做法思路：

Stack2为空栈，直接将Stack1.top()压入Stack2。
Stack2非空，若Stack1.top() <= Stack2.top()，Stack1.top()出栈并压入Stack2。
Stack2非空，若Stack1.top() > Stack2.top()，Stack2.top()陆续出栈，并且压入Stack1，直至Stack1.top()【这个值是一开始的top值，不是陆续压入Stack1的top值】 <= Stack2.top()，Stack1.top()出栈并压入Stack2。

为了方便大家理解，我也是辛苦地画了图（）

假设一开始Stack1的初始数据是：4、2、3、7

【1】

【2】

【3】

【4】

【5】

最后要想得到Stack的降序，只需要将Stack2依次出栈压入Stack1,就

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/898547

【数据结构复习之路】栈和队列（本站最全最详细讲解）& 严蔚敏版_站和队列

☆ 栈 ：

一、栈的基本概念

1、栈的定义

2、栈的基本操作

二、栈的顺序存储结构

1、顺序栈的定义

栈的初始化：

判断栈空：

2、基本操作（静态vs动态）

进栈：

出栈 ：

读栈顶元素 ：

动态分配：

3、共享栈

栈的初始化：

进栈：

出栈：

三、栈的链式存储结构

1、基本操作

链栈的初始化：

进栈：

出栈：

销毁链栈：

四、栈的应用

1、用栈解决括号匹配

2、栈排序

☆ 栈：

出栈：

读栈顶元素：