当前位置:   article > 正文

栈——概念、基本操作及其应用_栈的组合

栈的组合

前言

问:栈与队列也属于线性表的范畴,为什么要单独拿出来说呢?
因为一般的线性表插入和删除位置是没有限制的,而栈与队列对插入和删除的位置有限制,从而在相关操作上有一定的特殊性

受限数据结构——插入和删除受限制的线性表
(1)栈
(2)队列
(3)双队列

栈作为一种线性结构,在数据结构中有非常重要的地位,以后会常用。熟知栈的基本操作及适用情况是非常重要的。

一、栈的相关概念及特性

1.定义和术语

栈:限定在表尾作插入、删除操作的线性表
(1)进栈:插入一个元素到栈中,或称:入栈、推入、压入、push
(2)出栈:从栈删除一个元素,或称:退栈、上托、弹出、pop
(3)栈底:表头,即表中不允许插入、删除元素的一端
(4)栈顶:表尾,即允许插入、删除元素的一端
(5)空栈:不含元素的栈
(6)栈的别名:“后进先出”表、“LIFO”表、反转存储器、地窖、堆栈
注:栈的元素的进出原则:后进先出

2.栈的基本操作

(1)Initstack(s):置s为空栈
(2)Push(s,e):元素e进栈s
若s已满,则发生溢出;若不能解决溢出,重新分配空间失败,则插入失败。
(3)Pop(s,e):删除栈s的顶元素,并送入e
若s为空栈,发生“下溢”;为空栈时,表示某项任务已完成
(4)Gettop(s,e):栈s的顶元素拷贝到e
若为空栈,则结束拷贝
(5)Empty(s):判断s是否为空栈
若s为空栈,则Empty(s)为true;否则返回false

3.理解栈操作(模拟铁路调度站)

讨论:假设依次输入3个元素ABC到栈中,可得哪几种不同输出
(1)输出ABC
每输入一个元素后就立马出栈
在这里插入图片描述

(2)输出CBA
ABC全部进栈后,依次出栈
在这里插入图片描述

(3)输出BCA
AB进栈,C不进栈。B出栈,C进栈后CA出栈
在这里插入图片描述

ps:排列组合可知,有六种输出可能,除以上三种外,还有ACB,BAC,CAB。其中CAB不可能为输出结果,A不能成为C的直接后继
通过分析可知,一般的,输入序列(…,ai,…,aj,…,ak,…)到栈中,不能得到(…,ak,…,ai,…,aj,…)

延伸讨论:输入ABCD到栈中,能得到哪几种输出?不能得到哪几种输出?
从上面对三个元素的讨论可知,有5种输出组合。我们把A元素输入后马上输出,剩下的BCD就有5种输出。同理,把B输入后马上输出,剩下的ACD就有5种输出组合。
若AB进栈后,C进来马上输出,剩下D,有3种输出组合。若ABC进栈后,D进栈立刻出栈,只有DCBA一种组合。
共5+5+3+1=14种组合

思考一下:当输入元素不断扩大,有几种输出呢?

二、顺序栈的基本操作

之前我们说到,每个线性表有两种存储方式,一种是顺序存储,一种是链式存储。
栈是一种特殊的线性表,也有两种存储方式

1.顺序栈

1.定义:用顺序空间表示的栈
设计实习方案时需考虑的因素:
(1)如何分配存储空间
动态分配或静态分配
栈空间范围,如:s[0…maxleng-1]
(2)如何设置进栈和出栈的标志top
如top指向栈顶元素或指向栈顶元素下一空单元等,作为进栈出栈的依据
(3)分析满栈的条件,用于进栈操作
(4)分析空栈的条件,用于出栈操作

下面针对top指向栈顶元素或指向栈顶元素下一空单元,分别进行基本操作的讲解,分为方案1和方案2

2.方案1

方案内容:栈空间范围:s[0…maxleng-1]
顶指针指向顶元素所在位置

序号
maxleng-1
/// 自由 区
top->n-1 ——an 栈顶
… …
1 —— a2
0 —— a1 栈底

(1)非空栈
top>=0
顶元素=s[top]
(2)进出栈说明:进栈操作:先对top加一,指向下一空位置,将新数据送入top指向的位置,完成进栈操作。结束时top指向新栈顶元素所在位置
出栈操作:先根据top指向,取出栈顶数据元素,再对top减一。完成出栈操作。结束时top指向新栈顶元素所在位置
(3)满栈条件
top == maxleng-1 若插入元素,将发生溢出
(4)空栈条件
top == -1 若删除元素,将发生下溢

3.方案2
方案内容:栈空间范围:s[0…maxleng-1]
顶指针指向顶元素下一空位置

序号
maxleng-1
/// 自由 区
top->n
n-1 —— an 栈顶
… …
1 —— a2
0 —— a1 栈底

(1)非空栈
top>=0
顶元素=s[top-1]
(2)进出栈说明:进栈操作:先将新数据送入top指向的位置,再对top加一,指向下一空位置,完成进栈操作。结束时top指向新栈顶元素所在位置的下一空位置
出栈操作:先对top减一,再根据top指向,取出栈顶数据元素,完成出栈操作。结束时top指向新栈顶元素所在位置的下一空位置
(3)满栈条件
top == maxleng 若插入元素,将发生溢出
(4)空栈条件
top == 0 若删除元素,将发生下溢

4.顺序栈的描述
栈元素与顶指针合并定义为一个记录
约定:栈元素空间[0…maxleng-1]
top指向栈元素下一空位置
ps:top是栈顶标志,根据约定由top找栈顶元素

存储空间分配方案:静态分配与动态分配
(1)静态分配

typedef struct
{
	ElemType elem[maxleng];//栈元素空间
	int top;//顶指针 
}sqstack;//sqstack为结构类型
sqstack s;//s为结构类型变量
//其中:s.top:顶指针	s.elem[s.top-1]:顶元素 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

(2)动态分配

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{
	ELemType *base;//指向栈元素空间,栈元素空间首地址
	int top;//顶指针
	int stacksize;//栈元素空间大小,相当于maxleng 
}SqStack;//结构类型 
SqStack s;//s为结构类型变量 
//其中:s.top:顶指针	s.base[s.top-1]:顶元素 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

`

2.顺序栈算法

1.初始化

//栈的初始化算法(动态分配)
void InitStack (SqStack &S)
{
	S.base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));//分配存储空间
	S.top = 0;//定义栈顶指针
	S.stacksize = STACK_INIT_SIZE;//定义栈大小 
} 
//可放在主函数中调用 
void main(void)
{
	SqStack S1,S2;
	InitStack(S1);//调用函数初始化S1	
	//也可以自己写
	S2.base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));//分配存储空间
	S2.top = 0;//定义栈顶指针
	S2.stacksize = STACK_INIT_SIZE;//定义栈大小  
	
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

2.进栈

int push(SqStack &S,ElemType x)
{
	if (S.top >= S.stacksize)//发生溢出,扩充
	{
		newbase = (ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if (!newbase)//扩充失败
		{
			printf ("Overflow");
			return ERROR;
		}
		free (S.base);//释放原有空间,将栈挪到新空间
		S.base = newbase;//赋值基地在 
		S.stacksize += STACKINCREMENT;//增加空间 
	} 
	S.base[s.top] = x;//装入元素x
	S.top++;//修改顶指针
	return OK; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

3.出栈

//出栈算法
int pop (SqStack &S,ElemType &x)
{
	if (S.top == 0)
		return ERROR;//空栈
	else
	{
		S.top--;//修改顶指针
		x = S.base[S.top]//取走栈顶元素
		return OK;//成功退栈 
	} 
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

4.例子

//栈S操作例子
int main()
{
	SqStack S;
	ElemType e;
	InitStack (S);
	push(S,10);
	if (push(S,10)==ERROR)//最好能判断其返回值,做出相应处理
		printf ("进栈失败!");
		//...
	if (pop(S,e)==OK)
	{
		//退栈成功 
	}else
	{
		//退栈失败,提示错误信息 
	} 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

三、链式栈的基本操作

1.链式栈概念:用链式存储结构实现的栈
2.链式栈表示:用不带表头结点的单链表表示

1.结点和指针的定义

//结点和指针的定义
struct node
{
	ElemType data;//data为抽象元素类型
	struct node *next;//next为指针类型 
}*top = NULL;//初始化,置top为空栈 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2.非空链式栈的一般形式

假定元素进栈次序为i:a1、a2、…、an(top指向a1)
用普通无结点的单链表,在进出栈时需扫描找到最后一个结点
缺点:进出栈时间开销大

解决方案:将指针次序颠倒,top指向an。此时进栈时将新结点作为首结点,出栈时删除首结点,即之前说的后进先出链表
优点:进出栈时间为常数

3.链式栈的进栈:压入元素e到top为顶指针的链式栈

//进栈算法(push_link)
struct node *push_link (struct node *top,ElemType e)
{
	struct node *p;
	int leng = sizeof(struct node);//确定新结点空间的大小
	p = (struct node*)malloc(leng);//生成新结点
	p->data = e;//装入元素e
	p->next = top;//插入新结点
	top = p;//top指向新结点
	return top;//返回指针top 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

4.退栈算法 (pop_link)

struct node *pop(struct node*top,ElemType *e)
{
	struct node *p;
	if (top == NULL)
		return NULL;//空栈,返回NULL
	p = top;//p指向原栈的顶结点
	(*e) = p->data;//取出原栈的顶元素送(*e)
	top = top->next;//删除原栈的顶结点
	free(p);//释放原栈顶结点的空间
	return top;//返回新的栈顶指针top 
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

四、栈的应用

这里给大家讲几个适用栈的具体例子,主要讲解思路,代码并未给出。

1.数制转换

例1:给定十进制数N=1348,转换为八进制数R=2504

1.依次求余数,并送入栈中,直到商为0
	(1)r1 = 1348%8 = 4	求余数 
	   n1 = 1348/8 = 168求商
	(2)r1 = 168%8 = 0	求余数 
	   n2 = 168/8 = 21	求商
	(3)r3 = 21%8 = 5	求余数 
	   n3 = 21/8 = 2	求商
	(4)r4 = 2%8 = 2		求余数 
	   n4 = 2/8 = 0 	求商 
2.依次退栈,得R=2504 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

2.判定表达式中的括号匹配

1.括号匹配的表达式
例:{…(…()…)…}
[…{…()…()…}…]
2.括号不匹配的表达式
例:{…[}…]
[…(…()…)…)

该检查算法的思想如下:
(1)每碰到一个左括号,把左括号进栈
(2)每碰到一个右括号a,就将栈顶元素出栈,记为b,检查b是否跟a匹配的左括号。如果是,则继续;否则返回,提示存在括号不匹配
在这里插入图片描述

3.表达式求值

约定:#为开始或结束符
例:求表达式的值:#4+2*3-12/(7-5)#
算法思想:
设:s1——操作数栈,存放暂不运算的数和中间结果
s2——运算符栈,存放暂不运算的运算符

1.置s1、s2为空栈;开始符#进s2
2.从表达式读取“单词”w——操作数/运算符
3.当 w!=‘#’或s2的栈顶运算符!=‘#’时,重复
	3.1若w为操作数,则w进s1,读取下一“单词”w
	3.2若w为运算符,则:
			若s2的栈顶运算符优先级<w,则
				w进s2,读取下一“单词”w
			若s2的栈顶运算符优先级=w,且w=“)”,则
				去括号,pop(s2),读取下一“单词”w
			s2的栈顶运算符优先级>w,则
				pop(s1,a);	pop(s1,b);	pop(s2,op);
				c=b op a; push(s1,c);//op=s2的栈顶运算符
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

总结

大家可以想想怎么用栈做更加复杂的操作,除了上面的例子,有哪些算法精准的利用了栈的特性,达到优化算法的效果。
下一节会讲讲队列,也是一种线性表。
如有错误,欢迎指正。
ps:代码非原创。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/869024
推荐阅读
相关标签
  

闽ICP备14008679号