文档介绍：数据结构课程的内容
1
栈(Stack)
第三章栈和队列
队列(Queue)
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
2
1. 定义
栈
与同线性表相同,仍为一对一关系。
用顺序栈或链栈存储均可,但以顺序栈更常见
只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。
关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同。
基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。
3. 存储结构
4. 运算规则
5. 实现方式
2. 逻辑结构
限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作)
3
问:堆栈是什么?它与一般线性表有什么不同?
栈
答:堆栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。
与一般线性表的区别:仅在于运算规则不同。
一般线性表堆栈
逻辑结构:一对一逻辑结构:一对一
存储结构:顺序表、链表存储结构:顺序栈、链栈
运算规则:随机存取运算规则:后进先出(LIFO)
“进”=压入=PUSH(x)
“出”=弹出=POP ( y )
4
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base
例如: 栈 s= (a1 , a2 , a3 , ……….,an-1 , an )
a1 称为栈底元素 an 称为栈顶元素
插入元素到栈顶(即表尾)的操作,称为入栈。
从栈顶(即表尾)删除最后一个元素的操作,称为出栈。
教材P44对栈有更详细定义:
强调:插入和删除都只能在表的一端(栈顶)进行!
5
栈的表示和实现
顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指向栈顶元素在顺序栈中的下一个位置,
base为栈底指针,指向栈底的位置。
base
空栈
a 进栈
b 进栈
a
a
b
top
base
top
base
top
6
顺序栈示意图
s
a1
a2
a3
data
a4
(栈底)
(栈顶)
99
.
.
.
3
2
1
0
top
7
顺序栈的类型表示:
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef char StackData;
typedef struct { //顺序栈定义
StackData *base; //栈底指针
StackData *top; //栈顶指针
int stacksize;//当前已分配的存储空间
} SeqStack;
8
判栈空
int StackEmpty (SeqStack *S) {
if( S->top == S->base ) return 1 //空则返回1
else return 0; //否则返回0
}
判栈满
int StackFull (SeqStack *S) {
if( S->top- S->base >= S-> StackSize ) return 1 //判栈满,满则返回1
else return 0; //否则返回0
}
顺序栈的基本运算:
9
初始化
void InitStack ( SeqStack *S) { //置空栈
S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW);
S->top = S->base ;
S->stacksize= STACK_INIT_SIZE ;
Return ok;
}
10