chapter 3栈与队列.ppt

3 栈与队列
主要内容
栈
栈的应用
队列
队列的应用
2
栈与队列
栈与队列
栈和队列是在程序设计中被广泛使用的两种线性数据结构。
与线性表相比,它们的插入和删除操作受更多的约束和限定,故又称为限定性的线性表结构。
3
栈与队列
栈
栈:限定仅只能在末端进行插入和删除的线性表。
栈顶:允许插入和删除的一端。
栈底:不允许插入和删除的一端。
时间有序表:先进后出(FILO) /后进先出(LIFO)
an-1
an-2
…
a1
a0
bottom
top
退栈
(弹出)
进栈
(压入)
4
栈与队列
栈的基本操作
● clear()——清空栈。
● isEmpty()——判断栈是否为空。
● push(el)——将元素el放到栈的顶部。
● pop()——取出栈顶部的元素。
● topEl()——获取栈顶部的元素,但不删除该元素。
5
栈与队列
top=0
1
2
3
4
5
0
栈空
栈顶指针top,指向实际栈顶
后的空位置,初值为0
top
1
2
3
4
5
0
进栈
A
top
出栈
栈满
B
C
D
E
F
设数组大小为M
top=0,栈空,此时出栈,则下溢(underflow)
top=M,栈满,此时入栈,则上溢(overflow)
top
top
top
top
top
1
2
3
4
5
0
A
B
C
D
E
F
top
top
top
top
top
top
栈空
6
栈与队列
栈的表示和实现
顺序方式
链式方式
7
栈与队列
顺序表示的栈的实现
top
空栈: top == -1
MaxTop = = 4
top
A
top
A
B
A
B
C
top
top
A
B
C
D
3
1
2
0
8
栈与队列
栈的初始化操作
0 1 2 MaxTop-1
top
template<class T>
Stack<T>::Stack(int MaxStackSize){
MaxTop=MaxStackSize-1;
stack=new T[MaxStackSize];
top=-1;
}
9
栈与队列
进栈操作
0 1 2 maxSize-1
top
b
a
0 1 2 maxSize-1
top
b
a
c
template<class T>
Stack<T>& Stack<T>::Add(const T& x){
if(IsFull())
{cout<<"no memory;"<<endl;return *this;}
top=top+1;
stack[top]=x;
return *this;
}
10
栈与队列