第四章：——栈、队、堆

第四章：——栈、队、堆

（1）预备知识：

栈：先进后出。

队列：先进先出。

栈：

S.top():取出栈顶（仅仅是获得栈顶的数值）

S.empty():判断栈是否为空

S.push(x):将x添加至栈

S.pop():弹出栈顶（把栈顶的数值弹出删除）

S.size():栈的存储元素个数

队列：

Q.empty():判断队列是否为空

Q.front():返回队列头部元素

Q.back():返回队列尾部元素

Q.pop():弹出队列头部元素

Q.push(x):将x添加至队列

Q.size():返回队列的存储元素的个数

栈如何声明：std::stack S;//栈的关键字是stack

队列如何声明：std::queue Q;//队列的关键字是queue

（2）例1：使用队列实现栈：

设计一个栈，支持基本的操作，这个栈的内部存储数据的结构为队列，队列的方法只能包括push、peek(front)、pop、size、empty等标准队列的方法：意思是用队列实现栈

方法论述：

push(x):将元素x压入栈中

pop()：弹出（移除）栈顶元素

top():返回栈顶元素

empty():判断栈是否是空

class MyStack
{
    public:
    MyStack()
    {}
    void push(int x)
    {}
    int pop()
    {}
    int top()
    {}
    bool empty
    {}
};

这边的重点思路就是通过利用：一个临时队列来实现顺序的调整：

#include
class MyStack
{
  public:
    MyStack(){}
    void push(int x)
    {
        std::queuetemp_queue;
        temp_queue.push(x);
        while(!_data.empty())
        {
            temp_queue.push(_data.front());
            _data.pop();
        }
        while(!temp_queue.empty())
        {
            _data.push(temp_queue.front());
            temp_queue.pop();
        }
    }
    int pop()
    {
        int x=_data.front();//取栈顶元素，即为队列头部元素
        _data.pop();
        return x;//返回取出的队列头部元素x，即为栈顶元素
    }
    int top()
    {
        return _data.front();//返回栈顶即直接返回队列头部元素
    }
    bool empty()
    {
        return _data.empty();
    }
    private:
    std::queue_data;//_data数据队列存储元素的顺序就是栈存储元素的顺序
};

（3）例2：使用栈实现队列：设计一个队列，支持基本的队列操作，这个队列的内部存储数据的结构为栈，栈的方法只能包括push、top、pop、size、empty等标准的栈方法。

方法论述：

push(x):将元素x压入队列中

pop()：弹出（移除）队列头部元素

peek():返回队列头部元素

empty():判断队列是否是空

class MyQueue
{
    public:
    MyQueue()
    {}
    void push(int x)
    {}
    int pop()
    {}
    int top()
    {}
    bool empty
    {}
};

思路重点：添加一个临时栈：

#include 
class MyQueue
{
  public:
    MyQueue(){}
    void push(int x)
    {
        std::stacktemp_stack;
        while(!_data.empty)
        {
            temp_stack.push(_data.top());
            _data.pop();
        }
        temp_stack.push(x);
        while(!temp_stack.empty())
        {
            _data.push(temp_stack.top());
            temp_stack.pop();
        }
    }
    int pop()
    {
        int x=_data.top;
        _data.pop();
        return x;
    }
    int peek()
    {
        return _data.top();
    }
    bool empty()
    {
        return _data.empty();
    }
    private:
    std::stack_data;
};

(4)例3：设计一个栈，支持如下操作，这些操作的算法复杂度需要是常数级，O(1):

方法概述：

push(x):将元素x压入栈中

pop():弹出（移除）栈顶元素

top():返回栈顶元素

getMin():返回栈内最小元素

class MinStack
{
  public:
    MinStack(){}
    void push(int x)
    {}
    void pop(){}
    int top(){}
    int getMin(){}//返回栈内最小元素
};

思考关键：用另一个栈，存储各个状态的最小值：

#include 
#include 

class MinStack
{
  public:
    void push(int x)
    {
        _data.push(x);
        if(_min.empty()) _min.push(x);
        else{
            if(x>_min.top())
                x=_min.top();
            _min.push(x);
        }
    }
    void pop()
    {
        _data.pop();
        _min.pop()//数据栈喝最小栈同时弹出
    }
    int top()
    {
        return _data.top();
    }
    int getMin()
    {
        return _min.top();
    }
    private:
    std::stack -data;
    std::stack _min;
};

（5）例4：合法的出栈序列：已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法？

设置一个栈依按照题中给出的出栈顺序，依次进入，发现最后栈不能为空，则说明不合理，为空则说明合理

#include 
#include 

bool check_is_valid_order(std::queue&order)
{
    std::stackS;
    int n=order.size();
    for(int i=0;i 
(6)例5：简单的计算器：设计一个计算器，输入一个字符串存储的数学表达式，可以计算包括“（”、“）”、“+”、“-”四种符号的1数学表达式，输入的数学表达式字符串保证是合法的。输入的数学表达式中可能存在空格字符。
 
//字符串转换数字
#include 
#include 

int main()
{
    int number=0;
    std::string s="12345";
    for(int i=0;i 
//计算
void compute(std::stack&number stack,std::stack&operation stack)
{
    if(number_stack.size<2) return;
    int num1=number_stack.top();
    number_stack_pop();
    int num2=number_stack.top();
    number_stack_pop();
    if(operation_stack.top()=='+')
        number_stack.push(num1+num2);
    else if(operation_stack.top()=='-')
        number_stack.push(num1-num2);
    operation_stack.pop();
}
 
#include 
#include 

class Solution
{
    public:
    int calculate(std::string s)
    {
        static const int STATE_BEGIN=0;
        static const int NUMBER_STATE=1;
        static const int OPERATION_STATE=2;
        std::stacknumber_stack;
        std::stackoperation_stack;
        int number=0;
        int STATE=STATE_BEGIN;
        int compuate_flag=0;
        for(int i=0;i='0'&&s[i]<='9')
                        STATE=NUMBER_STATE;
                    else
                        STATE=OPERATION_STATE;
                    i--;
                    break;
                case NUMBER_STATE:
                    if(s[i]>='0'&&s[i]<='9')
                        number=number*10+s[i]-'0';
                    else
                    {
                        number_stack.push(number);
                        if(compuate_flag==1)
                            compute(number_stack,opteration_stack);
                        number=0;
                        i--;
                       STATE=OPERATION_STATE;
                        break;
                    }
                 case OPERATION_STATE:
                        if(s[i]=='+'||s[i]=='-')
                        {
                            operation_stack.push(s[i]);
                            compuate_flag=1;
                        }
                        else if(s[i]=='(')
                        {
                            STATE=NUMBER_STATE;
                            compuate_flag=0;
                        }
                        else if(s[i]>='0'&&s[i]<='9')
                        {
                            STATE=NUMBER_STATE;
                            i--;
                        }
                        else if(s[i]==')')
                            compute(number_stack,opteration_stack);
                    if(number!=0)
                    {
                        number_stack.push(number);
                		compute(number_stack,opteration_stack);
                    }
                    if(number==0&&number_stack.empty())
                    {
                        return 0;
                    }
                    return number_stack.top();
            }
        }
    }
};
 
(7)堆的预备：
 
（8）例6：数组中第K大的数：已知一个未排序的数组，求这个数组中第K大的数字。
 
直接对数组排序是O(NlogN)的时间复杂度。
 所以就可以考虑用最大堆和最小堆来解决问题。
 
#include
#include
class Solution:
{
    public:
    int findKthLargest(std::vector&nums,int k)//最小堆
    {
        std::priority queue,std::greater> Q;
        for(int i=0;i 
（9）例9：寻找中位数：设计一个数据结构，该数据结构动态维护一组数据，且支持如下操作：
 
（1）添加元素：void addNum(int num)，将整型num添加至数据结构中。
 
（2）返回数组的中位数：double findMedian(),返回其维护的数据的中位数。
 
中位数的定义为：
 
（1）若数据个数为奇数，中位数是该数组排序后中间的数。[1,2,3]->2
 
（2）若数据个数为偶数，中位数是该组数排序后中间的两个数字的平均值。[1,2,3,4]->2.5
 
void addNum(int num)
{
    if(bid_queue.empty())
    {
        bid_queue.push(num);
        return ;
    }
    if(big_queue.size()==small_size())
    {
        if(numsmall_queue.size())
    {
            if(numsmall_queue.top())
          {
              big_queue.push(small_queue.top());
              small_queue.pop();
              small_queue.push(num);
          }
          else{
              big_queue.push(num);
          }
      }
    }
}
 
double findMedian()
{
    if(big_queue.size()==small_queue.size())
    {
        return (big_queue.top()+small_queue.top())/2;
    }
    else if(big_queue.size()>small_queue.size())
    {
        return big_queue.top();
    }
    else if(big_queue.size() 
          small_queue.pop();
          small_queue.push(num);
      }
      else{
          big_queue.push(num);
      }
  }
}
 
}
 
```c++
double findMedian()
{
    if(big_queue.size()==small_queue.size())
    {
        return (big_queue.top()+small_queue.top())/2;
    }
    else if(big_queue.size()>small_queue.size())
    {
        return big_queue.top();
    }
    else if(big_queue.size()