数据结构第3章栈和队列.ppt

文档介绍：栈 ( Stack )
队列 ( Queue )
栈和队列的应用
第三章 栈和队列
1
操作原则
后进先出
(LIFO)
§ 栈 ( Stack )
top
bottom
a1
an
an-1

进栈a 1    a n
出栈a n    a 1
只允许在一端插入和删除的线性表
S= （a 1 a 2 a 3       a n-1 a n ）
允许插入和删除的一端称为栈顶 (top)，
另一端称为栈底(bottom)
top
bottom
a1
an
an-1

x
2
ADT List
{ 数据对象:
D={ai|1i  n, n  0, ai属Elemtype类型
数据关系:
R1={< ai ,ai+1 >| ai ,ai+1 D, i=1,2, …,n-1}
基本运算:
InitStack(&S );
ClearStack(S);
StackEmpty(S);
StackLength(S):
Push(&S,e);
Pop(&S,&e)
GetTop(S,&e);
DispStack(S);
}
抽象数据类型栈的定义
3
typedef struct //顺序栈定义
{ ElemType data[maxsize]; //栈数组
int top; //栈顶指针
} SqStack;
顺 序 栈
top (栈空)
0 1 2 3 4 5 6 7 8 9 maxsize-1
data
c
a
b
4
top
空栈
top
a 进栈
a
top
a
b
c
d
e
f 进栈溢出
top
b 进栈
a
b
top
a
b
c
d
e
e 进栈
top
a
b
d
e
e 退栈
c
5
top
空栈
top
a
b
d
d 退栈
c
c 退栈
top
a
b
c
b 退栈
a
b
top
a
a 退栈
top
6
void InitStack (SqStack *&S) //置空栈
{ S=(SqStack *)malloc(sizeof(SqStack));
S->top = -1;
return;
}
bool StackEmpty (SqStack *S)
{
//判断栈是否空？空则返回1，否则返回0
if(S->top==-1) return false;
else return true;
}
7
bool push (SqStack *&S, ElemType e)
//若栈满返回0, 否则新元素 x 进栈并返回1
{ if ( S->top==maxsize-1) return false;
S->top++;
S->data[S->top] = e; //加入新元素
return true;
}
bool pop (SqStack *&S, ElemType &e)
//若栈空返回0, 否则栈顶元素读到x并返回1
{ if ( S->top==-1 ) return false;
e = S->data[S->top]; S->top--;
return true;
}
8
栈 1 top1 top2 栈2
0 MaxSize-1
data
双栈共享一个栈空间
进栈 退栈
栈1
top1++; data[top1]=x;
x=data[top1]; top1--;
栈2
top2--; data[top2]=x;
x=data[top2]; top2++;
栈满？
栈空？
数据类型
typedef struct
{ ElemType data[MaxSize];
int top1,top