文档介绍：第3章栈和队列
本章主要介绍以下内容:
栈的概念、存储结构及其基本操作
队列的概念、存储结构及其基本操作
栈与队列的应用举例
退出
栈
栈的应用举例
队列
队列的应用举例
栈
栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:
进行插入和删除的一端是浮动端,通常被称为栈顶,并用一个“栈顶指针”指示;而另一端是固定端,通常被称为栈底。我们经常将栈用下图3-1的形式描述:
a1, a2, a3, ..., an 插入和删除端
图 3-1
结论:后进先出(Last In First Out),简称为LIFO线性表。
举例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。
举例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
下面我们先给出栈结构的基本操作:
(1)初始化栈 Init_Stack(S)
(2)入栈 Push_Stack(S,x)
(3)出栈 Pop_Stack(S)
(4)获取栈顶元素内容 Top_Stack(S)
(5)判断栈是否为空 Empty_Stack (S)
栈的顺序存储
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素,并用起始端作为栈底。
类型定义如下所示:
#define MAXSIZE 100
typedef struct
{datatype data[MAXSIZE];
int top;
}SeqStack
定义一个指向顺序栈的指针:
SeqStack *s;
基本操作算法:
⑴置空栈:首先建立栈空间,然后初始化栈顶指针。
SeqStack *Init_SeqStack()
{ SeqStack *s;
s=malloc(sizeof(SeqStack));
s->top= -1; return s;
}
⑵判空栈
int Empty_SeqStack(SeqStack *s)
{ if (s->top= = -1) return 1;
else return 0;
}
图 3-2
⑶入栈
int Push_SeqStack (SeqStack *s, datatype x)
{if (s->top= =MAXSIZE-1) return 0; /*栈满不能入栈*/
else { s->top++;
s->data[s->top]=x;
return 1;
}
}
⑷出栈
int Pop_SeqStack(SeqStack *s, datatype *x)
{ if (Empty_SeqStack ( s ) ) return 0; /*栈空不能出栈*/
else { *x=s->data[s->top];
s->top--; return 1; } /*栈顶元素存入*x,返回*/
}
⑸取栈顶元素
datatype Top_SeqStack(SeqStack *s)
{ if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/
else return (s->data[s->top] );
}
以下几点说明:
1. 对于顺序栈,入栈时,首先判断栈是否满了,栈满的条件为:s->top= =MAXSIZE-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。
2. 出栈和读栈顶元素操作,先判断栈是否为空,为空时不能操作,否则产生错误。通常栈空时常作为一种控制转移的条件。