第2章 栈和队列.pptVIP

一、栈 1.什么是栈 栈是限定在一端进行插入与删除的线性表。 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。 栈是按照“先进后出”的原则组织数据的。 通常用指针top 来指示栈顶的位置，用指针bottom 指向栈底。 往栈中插入一个元素称为入栈运算， 从栈中删除一个元素称为退栈运算。 建立一个空栈： using namespace std; template typename T void init_Stack(T *s, int m, int top) { s=new T[m];//动态申请容量为m的存储空间 top=0;//栈顶指针置0 return; } 入栈操作： ① 首先判断栈顶指针是否已经指向存储空间的最后一个位置，如果是，则说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误，算法结束。 ②然后将栈顶指针进一（top加一）。 ③最后将新元素x插入到栈顶指针指向的位置。 using namespace std; template typename T void push(T *s, int m, int top, T x) { if (top==m) {cout “Stack-overflow”endl;return;} top= top+1; s[top-1]=x; return; } 退栈运算： ①首先判断栈顶指针是否为0，如果是，则说明栈空，不可能进行退栈操作。这种情况称为“下溢”错误，算法结束。 ②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。 ③最后将栈顶指针退一（top减一） using namespace std; template typename T T pop(T *s,int m, int top) { T y; if (top==0) { cout“stack-underflow”;return;} y=s[top-1]; top=top-1; return (y); } 读栈顶元素 ① 首先判断栈顶指针是否为0，如果是，则说明栈空，读不到栈顶元素，算法结束。 ②然后将栈顶元素赋给指定的变量y。 using namespace std; template typename T T top(T *s,int m,int top) { T y; if (top==0) {cout“stack empty”endl;return;} y=s[top-1]; return(y); } 例2.10 建立容量为10的空栈，依次将50，60，70，80，90，100入栈，然后输出栈顶指针与栈中的元素，再输出栈顶元素，输出连续3次退栈的元素，最后再次输出栈顶指针与栈中的元素。 4.表达式的计算 计算机系统在具体处理表达式前，首先设置以下两个栈： 一是运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符栈中先压入一个表达式结束符“；”。 二是操作数栈，用于在表达式处理过程中存放操作数。 然后从左到右依次读出表达式中的各个符号（运算符或操作数），每读出一个符号按以下原则进行处理： （1）若读出的是操作数，则将该操作数压入操作数栈，并依次读下一个符号。 （2）若读出的是运算符，则作进一步判断： ①若读出运算符的优先级大于运算符栈栈顶运算符的优 先级,或者是“（”，则将读出的运算符压入运算符栈，并依次读下一个符号。 ②若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。 ③若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈。 ④若读出的为右括弧“）”，且运算符栈栈顶运算符为左括弧，则说明这对括号内的运算全部处理完，从运算符栈栈顶退出左括弧，然后依次读下一个符号。 2. 队列及其应用 什么是队列？ 队列是只允许在一端进行插入，而在另一端进行删除的线性表。 允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。 队列——“先进先出” 循环队列及其运算 循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 在循环队列中，用队尾指针rear指向队列中的队尾元素