文档介绍：数据结构辅导栈和队列 1
一、栈
栈(Stack)又称堆栈,它是一种运算受限的线性表,其限制是仅答应在表的一端进行插入和删除运算。人们把此端称为栈顶,栈顶的第一个元素被称为栈顶元素,相对地,把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈,它是把该元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称为出栈或退栈,它是把栈顶元素删除掉,使其下面的相邻元素成为新的栈顶元素。
在日常生活中,有许多类似栈的例子,如刷洗盘子时,依次把每个洗净的盘子放到洗好的盘子上,相当于进栈;取用盘子时,从一摞盘子上一个接一个地向下拿,相当于出栈。又如向枪支弹夹里装子弹时,子弹被一个接一个地压入,则为进栈;射击时子弹总是从顶部一个接一个地被射出,此为子弹出栈。
由于栈的插入和删除运算仅在栈顶一端进行,后进栈的元素必定先出栈,所以又把栈称为后进先出表(Last In First Out,简称LIFO)。
例如,假定一个栈S为(a,b,c),其中字符c的一端为栈顶,字符c为栈顶元素。若向S压入一个元素d,则S变为(a,b,c,d),此时字符d为栈顶元素;若接着从栈S中依次删除两个元素,则首先删除的是元素d,接着删除的使元素c,栈S变为(a,b),栈顶元素为b。
视频教程''target='_blank'title='div视频教程'div
栈既然是一种线性表,所以线性表的顺序存储和链接存储结构同样适用于栈。
(1)栈的顺序存储结构
栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现,利用数组来顺序存储栈中的所有元素,利用整型变量来存储栈顶元素的下标位置。假定栈数组用stack[StackMaxSize]表示,指示栈顶位置的整型变量用top表示,则元素类型为ElemType的栈的顺序存储类型可定义为:
ElemType stack[StackMaxSize];
int top;
其中,StackMaxSize为一个整型全局常量,需事先通过const语句定义,由它确定顺序栈(即顺序存储的栈)的最大深度,又称为长度,即栈最多能够存储的元素个数;由于top用来指示栈顶元素的位置,所以把它称为栈顶指针。
栈的顺序存储结构同样可以定义在一个记录类型中,假定该记录类型用Stack表示,则定义为:
struct Stack{
ElemType stack[StackMaxSize];
int top;
};
在顺序存储的栈中,top的值为-1表示栈空,每次向栈中压入一个元素时,首先使top增1,用以指示新的栈顶位置,然后再把元素赋值到这个位置上,每次从栈中弹出一个元素时,首先取出栈顶元素,然后使top减1,指示前一个元素成为新的栈顶元素。由此可知,对顺序栈的插入和删除运算相当于是在顺序表(即顺序存储的线性表)的表尾进行的,其时间复杂度为O(1)。
设一个栈S为(a,b,c,d,e),对应的顺序存储结构如图4-1(a)所示。若向S中插入一个元素f,则对应如图4-1(b)所示。若接着执行两次出栈操作后,则栈S对应如图4-1(c)所示。若依次使栈S中的所有元素出栈,则s变为空,如图4-1(d)所示。在图4-1中栈是垂直画出的,并且使下标编号向上递增,这样可以形象地表示出栈顶在上,栈底在下。
图4-1栈的顺序存储结构及操作过程
在一个顺序栈中,若top已经指向了StackMaxSize-1的位置,则表示栈满,若top的值已经等于-1,则表示栈空。向一个满栈插入元素和从一个空栈删除元素都是不答应的,应该停止程序运行或进行非凡处理。
(2)栈的链接存储结构
栈的链接存储结构与线性表的链接存储结构相同,是通过由结点构成的单链表实现的,此时表头指针被称为栈顶指针,由栈顶指针指向的表头结点被称为栈顶结点,整个单链表被称为链栈,即链接存储的栈。当向一个链栈插入元素时,是把该元素插入到栈顶,即使该元素结点的指针域指向原来的栈顶结点,而栈顶指针则修改为指向该元素结点,使该结点成为新的栈顶结点。当从一个链栈中删除元素时,是把栈顶元素结点删除掉,即取出栈顶元素后,使栈顶指针指向原栈顶结点的后继结点。由此可知,对链栈的插入和删除操作是在单链表的表头进行的,其时间复杂度为O(1)。
设一个栈为(a,b,c),当采用链接存储时,对应的存储结构示意图如图4-2(a)所示,其中HS表示栈顶指针,其值为存储元素c结点的地址。当向这个栈插入一个元素d后,对应如图4-2(b)所示。当从这个栈依次删除两个元素后,对应如图4-2(c)所示。当链栈中的所有元素全部出栈后,栈顶指针HS的值为空,即常量NULL所表示的数值0。
图4-2栈的链接存储结构及操作过程
栈的抽象数据