数据结构栈与队列.ppt

文档介绍：数据结构---第三章栈和队列
1
第三章栈和队列
栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其插入、删除元素时的运算规则受到更多的限制。
栈
栈与递归的实现
队列
本章学****要点<br****题与上机作业
数据结构---第三章栈和队列
2
线性表
插入删除
Insert(L, i, x) Delete(L, i)
(1≤ i≤ n+1) (1≤ i ≤n)
Insert(L, n+1, x) Delete(L, n)
Insert(L, n+1, x) Delete(L, 1)
栈
队列
数据结构---第三章栈和队列
3
栈
栈的定义
栈是一种特殊的线性表,限定插入和删除操作只能在表尾进行。具有后进先出(LIFO—Last In First Out )的特点。
a1
a2
an
栈顶(表尾)
栈底
bottom
top
入栈push
出栈pop
进栈
出栈
栈顶
栈底
an
…
a2
a1
数据结构---第三章栈和队列
4
定义在栈结构上的基本运算
(1) 生成空栈 InitStack(&amp;S)
(2) 销毁已存在的栈 DestroyStack(&amp;S)
(3) 清空已存在的栈 ClearStack(&amp;S)
(4) 判栈空与否 StackEmpty(S)
(5) 求当前栈元素个数(栈长) StackLength(S)
(6) 取栈顶元素 GetTop(S,&amp;e)
(7) 数据元素入栈 Push(&amp;S, e)
(8) 数据元素出栈 Pop(&amp;S, &amp;e)
(9) 遍历栈元素 StackTraverse( S, visit())
数据结构---第三章栈和队列
5
抽象数据类型栈的定义
ADT Stack {
数据对象:D={ai | ai  ElemSet, i=1,2, …, n, n0 }
数据关系:R1={ &lt;ai-1, ai&gt;, ai D, i=2, …, n }
约定an端为栈顶, a1端为栈底
基本操作:
InitStack(&amp;S)
操作结果:构造一个空栈S。
DestroyStack(&amp;S)
初始条件:栈S已存在。
操作结果:销毁栈S。
……
}ADT List
数据结构---第三章栈和队列
6
栈的顺序存储结构以及操作的实现
一个栈独占一组地址连续的存储单元
[类型定义] 空间基址+栈顶指示+栈容量
Typedef struct {
SElemType * base;
SElemType * top;
int stacksize;
}SqStack;
S
i-1 ai

.
.
.
1 a2
0 a1
stacksize-1

SqStack S;



空栈
栈不存在: base==NULL
栈空: top==base
可不用最后一个结点以保证指针正确
数据结构---第三章栈和队列
7
[基本运算实现示例]
# define STACK_INIT_SIZE 100;
Status InitStack(SqStack &amp;S)
{ = (SElemType *)
malloc(STACK_INIT_SIZE*sizeof(SElemType));
if ( ! ) return OVERFLOW;
= ; = STACK_INIT_SIZE;
return OK;
}//InitStack P47
Status StackEmpty(SqStack S)
{ if (==) return TRUE ;
else return FALSE;
}//StackEmpty
(1)
(4)
数据结构---第三章栈和队列
8
(5)
int StackLength(SqStack S)
{ return -;
}//StackLength
(6)
Status GetTop(SqStack S, SElemType &amp;e)
{ if (==) return ERROR;
e= *(-1);
return OK;
}//GetTop P47
(-)/sizeof(SElemType)
top
base
数据结构---第三章栈和队列
9
(7)
#define STACK_INCREMENT 50 ;
Status Push(SqSta