文档介绍：数据结构与算法第3章栈与队列
操作受限的线性表
栈(Stack)
运算只在表的一端进行
队列(Queue)
运算只在表的两端进行
栈
后进先出(LastInFirstOut)
一种限制访问端口的线性表
栈存储和删除元素的顺序与元素到达的顺序相反
也称为“下推表”
栈的主要元素
栈顶(top)元素:栈的唯一可访问元素
元素插入栈称为“入栈”或“压栈”(push)
删除元素称为“出栈”或“弹出”(pop)
栈底:另一端
栈的示意图
每次取出(并被删除)的总是刚压进的元素,而最先压入的元素则被放在栈的底部
当栈中没有元素时称为“空栈”
k0
k1
...
kn-1
栈顶
栈底
出栈
进栈
栈的主要操作
入栈( push )
出栈(pop)
取栈顶元素( top )
判断栈是否为空( isEmpty )
栈的抽象数据类型
template <class T> // 栈的元素类型为 T
class Stack {
public: // 栈的运算集
void clear(); // 变为空栈
bool push(const T item); // item入栈,成功则返回真,否则返回假
bool pop(T & item); // 返回栈顶内容并弹出,成功返回真,否则返回假
bool top(T& item); // 返回栈顶内容但不弹出,成功返回真,否则返回假
bool isEmpty(; // 若栈已空返回真
bool isFull(); // 若栈已满返回真
};
栈的实现方式
顺序栈(Array-based Stack)
使用向量实现,本质上是顺序表的简化版
栈的大小
关键是确定哪一端作为栈顶
链式栈(Linked Stack)
用单链表方式存储,其中指针的方向是从栈顶向下链接
顺序栈
template <class T> class arrStack : public Stack <T> {
private: // 栈的顺序存储
int mSize; // 栈中最多可存放的元素个数
int top; // 栈顶位置,应小于mSize
T *st; // 存放栈元素的数组
public: // 栈的运算的顺序实现
arrStack(int size) { // 创建一个给定长度的顺序栈实例
mSize = size; top = -1;
st = new T[mSize];
}
arrStack() { // 创建一个顺序栈的实例
top = -1;
}
~arrStack() { // 析构函数
delete [] st;
}
void clear() { // 清空栈内容
top = -1;
}
}
顺序栈
按压入先后次序,最后压入的元素编号为4,然后依次为3,2,1
1
2
3
top
栈底
4
顺序栈示意
0
1
2
3
4
5
= -1
= 0
A
0
B
1
C
2
D
3
E
4
F
5
= 5
A
0
1
2
3
4
5
A
0
B
1
C
2
D
3
4
5
= 3