栈的性质及相关概念 

栈的实现

栈相关OJ题

栈的性质及相关概念 

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端

**称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

根据理论环节,可以轻易的看出:栈的基本操作只有两个:
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶·

出栈：栈的删除操作叫做出栈。出数据也在

对应动图：

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

在这里就只用数组来实现栈

结构定义：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
#include<stdlib.h>
typedef int STDataType;
struct Stack
{
  Stack()
	  :a(nullptr),top(0),capacity(0)//初始化
  {}
	~Stack() {
		delete[]a;
		top = capacity = 0;
	}
	STDataType* a;
	int top;
	int capacity;
};

void StackPush(Stack* pst,STDataType x);//入栈

void StackPop(Stack* pst);//出栈

STDataType StackTop(Stack* pst);//获取栈顶的元素

bool StackEmpty(Stack* pst);//栈是否为空

int StackSize(Stack* pst);//栈中元素的个数

入栈代码：

void StackPush(Stack* pst, STDataType x)
{
	if (pst->capacity == pst->top)//满了需要增容
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//
		STDataType* tmp = new STDataType[newcapacity];
		memcpy(tmp, pst->a, sizeof(STDataType) * pst->top);//拷贝数据
		delete[]pst->a;//释放旧空间
		
		pst->capacity = newcapacity;//更新capacity
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;

}

入栈时首先检测容量是否已经满了如果满了则需要扩容，新空间开辟出来之后将原来空间上的数据拷贝到新空间上在这里我们可以使用memset进行拷贝。拷贝完成之后由于空间·是在堆区开辟的所以我们将其释放否则会有内存泄漏，扩容完成后将入栈的数据放入数组中即可并将top向后移。

出栈代码：

void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->top > 0);//防止栈空了还删
	pst->top--;
}

出栈我们只需要将top向前移即可。

返回栈顶的元素：

STDataType StackTop(Stack* pst)
{

	return pst->a[pst->top - 1];
}

判断栈是否为空

bool StackEmpty(Stack* pst)
{
	return pst->top == 0;
}

求栈中元素个数：

int StackSize(Stack* pst)
{
	return pst->top;
}

对应stack.h代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
#include<stdlib.h>
typedef int STDataType;
struct Stack
{
  Stack()
	  :a(nullptr),top(0),capacity(0)//初始化
  {}
	~Stack() {
		delete[]a;
		top = capacity = 0;
	}
	STDataType* a;
	int top;
	int capacity;
};

void StackPush(Stack* pst,STDataType x);//入栈

void StackPop(Stack* pst);//出栈

STDataType StackTop(Stack* pst);//获取栈顶的元素

bool StackEmpty(Stack* pst);//栈是否为空

int StackSize(Stack* pst);//栈中元素的个数

对应stack.cpp代码

#include"stack.h"
void StackPush(Stack* pst, STDataType x)
{
	if (pst->capacity == pst->top)//满了需要增容
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//
		STDataType* tmp = new STDataType[newcapacity];
		memcpy(tmp, pst->a, sizeof(STDataType) * pst->top);//拷贝数据
		delete[]pst->a;//释放旧空间
		
		pst->capacity = newcapacity;//更新capacity
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;

}

void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

STDataType StackTop(Stack* pst)
{

	return pst->a[pst->top - 1];
}

bool StackEmpty(Stack* pst)
{
	return pst->top == 0;
}

int StackSize(Stack* pst)
{
	return pst->top;
}

test.cpp

#include"stack.h"
int main()
{
	Stack st;
	StackPush(&st, 9);
	StackPush(&st, 9);
	StackPush(&st, 9);
	StackPush(&st, 9);
	StackPush(&st, 9);

	while (!StackEmpty(&st)){
		cout << StackTop(&st) << " ";
		StackPop(&st);
	   }

	return 0;

}

运行结果：

栈相关OJ题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出

栈的顺序是（）。
A 12345ABCDE

B EDCBA54321
C ABCDE12345

D 54321EDCBA
2.若进栈序列为1,2,3,4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2
B 2,3,4,1

C 3,1,4,2
D 3,4,2,1
首先第一个选择题答案很简单就直接按照栈后进先出的性质即可故答案为B。

第二个选择题了由于中途可以出栈所以我们验证法看是否符号栈先进后出的性质

首先A选项的出栈顺序为1 4 3 2那么可以是先将1入栈在将1出栈然后再将2 3 4全部入栈在将其全部出栈。

选项B是首先将1入栈再将2入栈再将2出栈然后将3入栈3再出栈4入栈再出栈最后再将1出栈

选项C不对如果按照这个出栈顺序首先再1入栈再将2入栈再将3入栈3出栈而此时出栈的为2而不是1

选项D先将1入栈再将2入栈再将3入栈3再出栈4入栈再出栈再将2出栈1出栈 

验证栈序列

对应letecode链接:
力扣

题目描述

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

解题思路：

1.新建另一个栈，index=0，，将pushed数组中的数，依次推入栈
2.入栈后，while判断popped[index]与新建的栈栈顶元素是否相等
3.若相等，则弹出栈顶，index++
4.最后判断栈是否为空

对应代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
                stack<int>stk;
                int index=0;
            for(auto x:pushed){
                stk.push(x);
                //对栈一直pop到栈顶元素不对应poped的当前元素（即代表不可以pop了）
                while(!stk.empty()&&index<popped.size()&&popped[index]==stk.top()){
                    stk.pop();
                    index++;
                }

            }
            return stk.empty();//如果是合法的栈序列最后栈一定为空
    }
};

栈排序

对应letecode链接：
力扣

题目描述：

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

示例1:

输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
 输出：
[null,null,null,1,null,2]
示例2:

输入： 
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：
[null,null,null,null,null,true]
说明:

栈中的元素数目在[0, 5000]范围内。

解题思路：

1.题目要求只能使用一个临时栈存放数据

2.入栈时，先将栈中小于val的数值暂存到临时栈中

3.将val入栈

4.再将临时栈中的数据push会栈中

对应代码：

class SortedStack {
public:
    SortedStack() {

    }
    
    void push(int val) {

          while(!stk.empty()&&stk.top()<val){//如果栈为空或者栈顶的元素比要入栈的元素要大则将栈顶的元素出栈保存再临时栈里面直到元素可以入栈
              tmp.push(stk.top());
              stk.pop();
          }
          stk.push(val);//将元素入栈
          while(!tmp.empty()){//将临时栈里面的元素重新放回栈中
              stk.push(tmp.top());
              tmp.pop();
          }
    }
    
    void pop() {
        if(isEmpty())
        return;
        
       stk.pop();
    }
    
    int peek() {
       if(isEmpty()){//如果为空直接返回-1；
           return -1;
       }
       int x=stk.top();
       return x;
    }
    
    bool isEmpty() {
    return stk.empty();
    }

private:
stack<int>stk;栈
stack<int>tmp;//辅助栈

};

栈实现队列

对应letecode链接：
力扣

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

解题思路：

输入栈：会把输入顺序颠倒如果把输入栈的元素弹出放到·输出栈中再从输出栈中弹出元素时则负负得正，实现了先进先出

1.可以把一个栈当做「输入栈」，把另一个栈当做「输出栈」。
2.当 push() 新元素的时候，放到「输入栈」的栈顶，记此顺序为「输入序」。
3.当 pop() 元素的时候，是从「输出栈」弹出元素。如果「输出栈」为空，则把「输入栈」的元素逐个 pop() 并且 push() 到「输出栈」中，这一步会把「输入栈」的栈底元素放到了「输出栈」的栈顶。此时负负得正，从「输出栈」的 pop() 元素的顺序与「输入序」相同。

对应图解：

对应代码：

class MyQueue {
public:
   stack<int>instack;//输入栈
   stack<int>outstack;//输出栈
  
    MyQueue() {
        
    }
    
    void push(int x) {
        instack.push(x);
    }
    
    int pop() {
        if(outstack.empty()){//如果输出栈中没有数据则去输入栈中取数据
            while(!instack.empty()){
                outstack.push(instack.top());
                instack.pop();
            }
        }
        int top=outstack.top();
        outstack.pop();
        return top;
    }
    
    int peek() {
        if(outstack.empty()){//如果输出栈中没有数据则去输入栈中取数据

             while(!instack.empty()){
                outstack.push(instack.top());
                instack.pop();
            }
        }
        
          return outstack.top();
    }
    
    bool empty() {
     return instack.empty()&&outputstack.empty();//两个栈同时为空则为空
    }
};

后缀表达式求值

对应letecode链接：
力扣

题目描述：

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

逆波兰表达式，也叫做后缀表达式。

我们平时见到的运算表达式是中缀表达式，即 "操作数① 运算符② 操作数③" 的顺序，运算符在两个操作数中间。
但是后缀表达式是 "操作数① 操作数③ 运算符②" 的顺序，运算符在两个操作数之后。

各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。

中缀表达式是其对应的语法树的中序遍历；
后缀表达式是其对应的语法树的后序遍历；
前缀表达式是其对应的语法树的前序遍历；
下图中左边是中缀表达式，中间是其对应的语法树，右边是语法树转成的后缀表达式。

为什么计算机要使用后缀表达式呢？是因为对于计算机而言，后缀表达式求值更简单。 

求值方法：

对逆波兰表达式求值的过程是：

如果遇到数字就进栈；
如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算 num1 运算 num2 .
逆波兰表达式是的代码实现很方便，用一个栈就能解决。

对应代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
          stack<int>st;
          for(auto &str:tokens){
              //操作符取数据运算
             if(str=="+"||str=="-"||str=="*"||str=="/"){
                    int right=st.top();//右操作数
                    st.pop();//出栈
                    int left=st.top();//左操作数
                    st.pop();//出栈
                    switch(str[0]){
                        case '*':
                        st.push(left*right);
                        break;
                        case '-':
                        st.push(left-right);
                        break;
                        case'/':
                        st.push(left/right);
                        break;
                        case '+':
                        st.push(left+right);
                        break;
                    }
             }
             
             else{
                 st.push(stoi(str));//转成整数
             }
          }
          return st.top();//返回结果
    }
};

如何由中缀表达式转后缀表达式呢？

遍历中缀表达式，空格跳过，遇到数字则读取（注意可能有多位数字，我这里只把负号看作操作符而不是数字前的符号），并加到后缀表达式中。
遇到左括号，压入操作符栈中。
遇到操作符，遵循一条规则——若栈顶的操作符优先级高于或等于当前符号优先级，则不断出栈并加到后缀表达式中，直到栈顶操作符的优先级小于当前符号优先级（'('的优先级最小）。接着将当前操作符入栈。
遇到右括号，不断出栈并加入到后缀表达式中，直到左括号也出栈。

对应代码：

vector<string> change(string &s){
        vector<string>ans;
        stack<char>flags;
        for(int i=0;i<s.size();i++){
            if(isspace(s[i]))continue;
            else if(isdigit(s[i])){
                int index=i;
                int len=0;
                 while(isdigit(s[i])){
                   i++;
                 }
                   ans.push_back(string(s.begin()+index,s.begin()+i));
                   i--;
            }
            else if(s[i]=='+'||s[i]=='-'){
                while(!flags.empty()){
                    if(flags.top()=='(')break;
                    ans.push_back(string(1,flags.top()));
                    flags.pop();
                }
                flags.push(s[i]);
            }
            else if(s[i]=='*'||s[i]=='/'){
                while(!flags.empty()){
                    if(flags.top()=='('||flags.top()=='+'||flags.top()=='-')break;
                    ans.push_back(string(1,flags.top()));
                    flags.pop();
                }
                flags.push(s[i]);
            }else if(s[i]=='('){//遇到左括号入栈
                flags.push(s[i]);
            }else if(s[i]==')'){
                while(!flags.empty()){
                    if(flags.top()=='('){
                        flags.pop();
                        break;
                    }
                    ans.push_back(string(1,flags.top()));
                    flags.pop();
                }
            }
        }
        while(!flags.empty()){
            ans.push_back(string(1,flags.top()));
            flags.pop();
        }
        return ans;
    }
};