顺序表：栈

刺骨的言语ヽ痛彻心扉 2022-11-25 10:16 56阅读 0赞

## 栈 ##

### 栈的抽象数据类型及其实现 ###

栈是一种特殊的线性表。在逻辑结构与存储结构上，栈与一般的线性表没有区别，但对允许的操作却加以限制，栈的插入和删除操作只允许在表尾一端进行。  
栈可以顺序存储，也可以连接存储。顺序存储的栈称为顺序栈，连接存储的栈称为链栈。  
**栈的插入和删除操作只能在表的尾端进行，每次删除的均为最后进栈的元素，故栈也称为后进先出表（LIFO）。**  
栈中插入，删除的一段称为栈顶，另一端称为栈底。  
栈底固定不动，栈顶随着插入和删除操作不断变化。  
不含栈元素的栈称为空栈。  
为了对栈中运算处理的方便，设置了一个栈顶指针top，伊总是指向最后一个进栈的栈元素。  
**栈顶指针实际上是数组的下标，伊的正常取值范围应是0~MaxSize-1。当top=-1时，表示栈为空，不能再进行删除操作；当top等于MaxSize-1时，表示栈已满，再进行插入操作会溢出。**

##### 构造函数Stack(int s) #####

//类操作的实现
    template<class T>
    Stack<T>::Stack(int s)
    { 
        //构造函数：创建栈空间，生成一个空栈
        MaxSize=s;
        elements=new T[MaxSize];  //创建栈空间
        top=-1;       //生成一个空栈 
    }

##### 进栈Push(const T& item) #####

template<class T>
    Stack<T>::Push(const T& item)
    { 
        //进栈：若栈不满，则item进栈，返回0，否则返回-1 
        if(!IsFull())      
        { 
      	elements[++top]=item;
      	return 0;
        }
        else
        { 
      	return -1;
        }
    }

##### 出栈Pop(void) #####

template<class T>
    Stack<T>::Pop(void)
    { 
        //出栈：若栈非空，则栈顶元素出栈，返回其值，否则返回NULL 
        if(!IsEmpty())      
        { 
      	return elements[top--];
        }
        else
        { 
      	return NULL;
        }
    }

##### 读栈顶元素 #####

template<class T>
    Stack<T>::GetTop(void)
    { 
        //读栈顶：若栈非空，则返回栈顶元素的值，否则返回NULL 
        if(!IsEmpty())      
        { 
      	return elements[top];
        }
        else
        { 
      	return NULL;
        }
    }

### 栈的应用 ###

##### 表达式的记值 #####

**此处只考虑常量表达式的情况，假设：表达式中的操作数只允许为个位的整形常数（若为多位数，可用"."分隔两操作数）；除整形常量外，只含有二元运算符（+，-，\*，、）和括号（（，））；记值顺序遵循四则运算法则，表达式无语法错误。**  
译程序扫描表达式(表达式在源程序中是以字符串的形式表示的)，析取一个“单词” ——操作数或运算符,是操作数则进操作数栈，是运算符则进运算符栈，但运算符在进栈时要按运算法则作如下处理:

1.  (1)当运算符栈为空时，析取的运算符无条件进栈。
2.  当运算符栈顶为“`*`”或“`/`”时，若析取的运算符为“`(`”，则进栈;否则，先执行出栈操作，并执行(6)的操作，然后该运算符再进栈。
3.  当运算符栈顶为“`+`”或“`-`”时,若析取的运算符为“`(`”、“`*`”或“`/`”，则进栈;否则，先执行出栈操作，并执行(6)的操作，然后该运算符再进栈。
4.  当运算符栈顶为“`(`”时，析取的运算符除“`)`”之外都可进栈。
5.  若析取的运算符为“`)`”，则先要连续执行出栈操作，直到出栈的运算符为“`(`”时为止,实际上，“`)`”并不进栈。
6.  除了“`(`”之外，每当一个运算符出栈时，要将操作数栈的栈顶和次栈顶出栈，进行该运算符所规定的运算,运算结果立即又进操作数栈。“`(`"出栈时,操作数栈不做任何操作。
7.  当表达式扫描结束后,若运算符栈还有运算符，则将运算符一一出栈,并执行(6)的操作。当运算符栈为空时，操作数栈的栈顶内容就是整个表达式的值。  
    例如，表达式2\* (3+4)- 8/2的计值过程如图所示。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]

在实际的表达式计值中往往采用另一种处理方法，即先把中缀式转换成后缀式，然后对后缀式进行计值处理。把**操作数所执行运算的运算符放在操作数之后**的表示方式称为**后缀式**。例如，中缀表达式2\* (3+4)-8/2对应的后缀式为234+ \*82/-.  
一个表达式的中缀式和对应的后缀式是等价的，即表达式的计算顺序和结果完全相同。但在后缀式中没有了括号,运算符紧跟在两个操作数后面，所有的计算按运算符出现的顺序，严格从左向右进行，而不必考虑运算符的优先规则。后缀式的计值只需一个操作数栈。  
编译程序在扫描后缀表达式时，若析取一个操作数，则立即进栈;若析取一个运算符，则将操作数栈的栈顶和次栈顶连续出栈,使出栈的两个操作数执行运算符规定的运算,并将运算结果进栈。后缀表达式扫描结束时，操作数栈的栈顶内容即为表达式的值。例如后缀表达式234+\*82/-的计值过程如图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70 1]  
后缀表达式的计值只需一个栈，而且不必考虑运算符的优先规则，显然比中缀表达式的计值要简单得多,但这种简单性的优势是以中缀式到后缀式的转换为代价的。为了把中缀式转换成等价的后缀式，需要扫描中缀式，并使用一个运算符栈来存放“`(`”和暂时还不能确  
定计算次序的运算符。在扫描中缀式的过程中，逐步生成后缀式。扫描到操作数时直接进人后缀式;扫描到运算符时先进栈，并按运算规则决定运算符进人后缀式的次序。操作数在后缀表达式中出现的次序与中缀表达式是相同的，运算符出现的次序就是实际应计算的顺序,运算规则隐含地体现在这个顺序中。例如中缀表达式`2*(3+4)-8/2`转换成等价的后缀表达式`234+ * 82/-`的过程如图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70 2]

##### 后缀表达式记值 #####

int EvaluatePostfix(void)
    { 
     //后缀表达式的记值
     //假设运算符只有+，-，*，/，操作数都是个位数，后缀表达式无语法错误
     Stack<int>Spnd(80);
     const int size=80;   //限定表达式最长为79个字符
     char buf[size];    //存储表达式的输入缓冲区
     cout<<"Input Postfix"<<endl;
     cin>>buf;     //输入后缀表达式
     int i=0,k;
     while(buf[i]!='\0')
     { 
      switch(buf[i])
      { 
       case '+':
        k=Spnd.Pop()+Spnd.Pop();
        Spnd.Push(k);
        break;
       case '-':
        k=Spnd.Pop();
        k=Spnd.Pop()-k;
        Spnd.Push(k);
        break;
       case '+':
        k=Spnd.Pop()*Spnd.Pop();
        Spnd.Push(k);
        break;
       case '+':
        k=Spnd.Pop();
        k=Spnd.Pop()/k;
        Spnd.Push(k);
        break; 
       default:
        //操作数进栈时，字符转换为数值
        Spnd.Push(intbuf[i]-48); 
      }
      i++;
     }
     cout<<"The value is "<<Spnd.Pop()<<endl;
     return 0; 
    }

##### 栈与递归 #####

##### 求前n个正整数的和的递归算法 #####

int sum(int n)
    { 
        //设n是正整数
        if(n==1)
        { 
            return 1;
        }
        else
        { 
            return n+sum(n-1);
        }
    }

##### 求前n个正整数的积的递归算法 #####

int factorial(int n)
    { 
        //设n是非负整数
        if(n==0)
        { 
            return 1;
        }
        else
        { 
            return n*factorial(n-1);
        }
    }

##### 汉诺塔问题的递归算法 #####

void hanoi(int n,char a,char b,char c)
    { 
        //将n个盘子从a柱移到c柱
        //只有1个盘子，直接移动
        if(n==1)
        { 
      	cout<<"move"<<a<<"to"<<c<<endl;
        }
        else
        { 
      	//将n-1个盘子从a柱移到b柱
      	hanoi(n-1,a,c,b);
      	//最后1个盘子从a柱移到c柱
      	cout<<"move"<<a<<"to"<<c<<endl;
      	//将n-1个盘子从b柱移到c柱
      	hanoi(n-1,b,a,c);
        } 
    }
    int main()
    { 
        int n;//盘子个数
        char A='1',B='2',C='3';//柱名
        cout<<"Enter the numbers of disks:";
        cin>>n;
        cout<<"The solution for n="<<n<<endl;
        hanoi(n,A,B,C);  
    }

**小结：**

1.  递归过程在计算机中实现时必须依赖堆栈
2.  使用递归前，需权衡设计和估计运行的复杂度，当强调算法设计且在运行时有合理的空间复杂度和时间复杂度时，应使用递归。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]: /images/20221124/2168492ab871450e909f6d7d64f5a64f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70 1]: /images/20221124/ab532ecfbbe540ca828f142ca54ad2f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70 2]: /images/20221124/2167a79446f84565825abe6067eeb7c5.png