《上海交通大学数据结构3-栈.ppt

第三章 栈 栈的逻辑结构 栈的物理结构 栈类的实现 STL中的栈 栈的应用 栈 后进先出(LIFO, Last In First Out)或先进后出(FILO, First In Last Out)结构，最先(晚)到达栈的结点将最晚(先)被删除。 相关概念 相关概念 栈底(bottom) ：结构的首部(结点最早到达的部分) 栈顶（top）：结构的尾部(结点最晚到达的部分) 出栈（Pop）：结点从栈顶删除 进栈（Push）：结点在栈顶位置插入 空栈 ：栈中结点个数为零时 栈的运算 创建一个栈create()：创建一个空的栈； 进栈push(x)：将x插入栈中，使之成为栈顶元素； 出栈pop()：删除栈顶元素并返回栈顶元素值； 读栈顶元素top()：返回栈顶元素值但不删除栈顶元素； 判栈空isEmpty()：若栈为空，返回true，否则返回false。 栈的抽象类 template class elemType class stack { public: virtual bool isEmpty() const = 0; virtual void push(const elemType x) = 0; virtual elemType pop() = 0; virtual elemType top() const = 0; virtual ~stack() {} }; 第三章 栈 栈的逻辑结构 栈的物理结构 栈类的实现 STL中的栈 栈的应用 栈的物理结构 栈的顺序结构及实现 栈的链接链式及实现 栈的顺序结构存储 用连续的空间存储栈中的结点，即数组 进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。 顺序栈类 template class elemType class seqStack: public stackelemType { private: elemType *elem; int top; int maxSize; void doubleSpace(); public: seqStack(int initSize = 10) ； ~seqStack()； bool isEmpty() const； elemType top() const； elemType pop()； void push(const elemType x) ； }; 顺序栈类的实现 template class elemType class seqStackelemType:: seqStack(int initSize = 10) { elem = new elemType[initSize]; maxSize = initSize ; top= -1; } template class elemType class seqStackelemType:: ~seqStack() { delete [] elem; } template class elemType bool class seqStackelemType::isEmpty() const { return top == -1; } template class elemType elemType class seqStackelemType::top() const { return elem[top]; } template class elemType elemType class seqStackelemType:: pop() { return elem[top--]; } template class elemType void class seqStackelemType:: push(const elemType x) { if (top == maxSize - 1) doubleSpace(); elem[++top] = x; } doubleSpace template class elemType void seqStackelemType::doubleSpace() { elemType *tmp = elem; elem = new elemType[2 * maxSize]; for (int i = 0; i maxSize; ++i) elem[i] = tmp[i]; maxSize *= 2; delete [] tmp; }