下载文档原格式
1第3章栈和队列3.1 栈3.2 队列2栈和队列是两种特殊的线性表，其特殊性在于插入和删除运算的限制上。
这两种线性结构在程序设计中经常使用。
33.1 栈3.1.1 栈的抽象数据类型3.1.2 顺序栈3.1.3 链式栈3.1.4 栈的应用举例3.1.5 栈与递归43.1 栈(stack)栈是一种限定仅在一端进行插入和删除操作的线性表。
插入：入栈（压栈） 删除：出栈（退栈） 插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）。
特征：后进先出(LIFO表，Last-In First-Out)。
k 0k 1k 2k 3栈底栈顶出栈入栈53.1.1 栈的抽象数据类型template <class ELEM> class Stack {public:void clear(); // 清空bool push(const T item); // 入栈bool pop(T& item); // 出栈bool top(T& item); // 返回栈顶内容bool is Empty(); //判栈是否空bool isFull(); // 判栈是否满};6栈的实现顺序栈采用顺序存储结构表示的栈链式栈采用链式存储结构表示的栈7template <class T>class arrStack : public Stack<T> {private:int mSize; // 栈容量int top; // 栈顶指针，初始为-1T *st; // 存放栈内容的连续空间public:arrStack(int size) { mSize=size; top=-1; st=new T[mSize];}arrStack() {mSize = 0; top = -1; st = null;}~arrStack() { delete[] st; }void clear() { top = -1;}bool push(const T item);bool pop(T& item);bool top(T& item);};3.1.2 顺序栈8template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){cout<<"栈满"<endl;return false;}else {st[++top]=item;return true;}}k 0k 1k 2k 3top top栈空9自动解决栈溢出的入栈操作template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){ // 扩展存储空间T * new2St = new T[mSize*2];for (i=0;i<top ;i++) newst[i]=st[i];delete [] st;st=newSt;mSize *=2;}st[++top]=item;return true;}10template <class T>bool arrStack<T>::pop(T& item) {if (top==-1){cout<<“栈为空，不能执行出栈操作"<endl;return false;}else {item = st[top--];return true;}}11template <class T>bool arrStack<T>::top(T& item) {if (top==-1){cout<<“栈为空，不能读取栈顶元素"<endl;return false;}else {item = st[top ];return true;}}123.1.3 链式栈\top13template <class T>class lnkStack : public Stack<T>{private:Link<T>*top; // 头指针int size; // 结点个数public:lnkStack(int defSize) { top=NULL; size=0; }~lnkStack() { clear(); }void clear();bool push(const T item);bool pop(T& item);bool top(T& item);}；14template <class T>void lnkStack::clear(){while (top!=NULL) {Link<T>* temp = top;top = top->next;delete temp;}size=0;}template <class T>bool lnkStack::push(const T item){Link<T>* tmp=new Link<T >(item, top );top=tmp;size++;return true;}template <class T>bool lnkStack::pop(T& item) {Link<T>* item;if (size==0){cout<<"栈空"<<endl;return false;}item=top->data;tmp=top->next;delete top;top=tmp;size--;return true;}153.1.4 栈的应用举例数制转换 迷宫问题表达式括号匹配检验 表达式求值 背包问题161.数制转换（1348）10=（2504）8==========================N N/8 N%81348 168 416821 021 2 52 0 2while (N) {N%8入栈；N/8=>N;}while (栈非空）{出栈；输出；}17//将非负十进制整数转换成八进制输出void conversion( ){Stack s;cin>>N;while (N){s.push( N%8); N=N/8;}while (!s.isEmpty()){s.pop(e); cout<<e;}}182.迷宫问题1234567891011121314151617181213141516171819201419*1234o o o o oo o o o o o oo o o o o o入口出口20*1234入口出口0 1 2 3 4 5 6 7 8 9 10 1112345687109OO21算法基本思路“穷举求解”，即从入口出发，沿某一方向向前试探，若能走通，则继续往前走；否则原路退回，换一个方向再继续试探，直到走到出口或确定无路可走为止。
