数据结构与算法分析-栈.ppt

文档介绍：Stacks(栈)
栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶,另一端为栈底。若有栈
S = (s0,s1,……sn-1)
则s0为栈底结点,sn-1为栈顶结点。
栈的结点插入为进栈
栈的结点删除为出栈
栈具有后进先出(LIFO)的特性
S0
S1
….
Sn-1
进栈
出栈
栈顶
栈底
2003-8-25
1
Lecture notes
0
1
MAXN-1
top
0
1
MAXN-1
top
(a) 栈结构示意图
(b) 栈空
(c) 栈满
2003-8-25
2
Lecture notes
Array-Based Stacks(顺序栈)
可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个游标变量top(习惯称为栈顶指针,注意与指针变量的区别),top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。
top是下一次进栈时,进栈表元要存入的数组元素下标。当栈为空时,top=0;栈满时,top=MAXN(数组元素个数),如图中的(b)和(c)。
a2
a1
a1
a2
top
2003-8-25
3
Lecture notes
进栈:
首先把进栈表元存入以top为下标的数组元素中,然后top加1,使top变为下一次进栈表元在数组中的下标。
出栈:
首先执行top减1,然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时,不能再出栈;在栈满时,不能再入栈。
2003-8-25
4
Lecture notes
Array-based stack class implementation(顺序栈类的实现)
//Array-based stack class implementation
Template <class Elem> class AStack:public Stack<Elem>
{
private:
int size;//Maximum size of stack
int top;//Index for top element
//Array holding stack elements
Elem *listArray;
表示栈中的第一个空闲位置
2003-8-25
5
Lecture notes
public:
AStack(int sz=DefaultListSize)
{//Constructor
size = sz;
top = 0;
listArray = new Elem[sz];
}
//Destructor
~AStack() { delete [] listArray; }
void clear() { top = 0; }
2003-8-25
6
Lecture notes
bool push(const Elem& item)
{
if(top == size) return false;//Stack is full
else { listArray[top++] = item; }
 }
bool pop(Elem& it)//Pop top element
{
if (top == 0) return false;
else { it = listArray[--top]; return true; }
}
2003-8-25
7
Lecture notes
bool topvalue(Elem& it) const
{//Return top element
if (top = 0) return false;
else
{
it = listArray[top-1];
return true;
}
}
int length() const {return top;}
};
2003-8-25
8
Lecture notes
An array-based stack storing
variable-length strings.
每个位置存储一个字符或一个整数,该整数说明栈中位于其左边的字符串长度。
‘a’
‘b’
‘c’
3
‘l’
‘h’
‘l’
‘e’
‘o’
5
0 1 2 3 4 5 6 7 8 9 10
top=10
2003-8-25
9
Lecture notes
Linked Stacks(链式栈)
即用链表来实现栈。
链表的第一个表元是栈顶结点,链表的末尾表元是栈底结点。
链表的首表元指针就是栈顶指针top,top为NULL的空链表是空栈。
x
∧
top