栈

栈题集

• 栈是一种特殊的数据结构，具有先进后出的特点。可以把栈想象成一个桶，当从桶中取出物品时，先放入的物品会后取出，并且只有将上面的物品取出后，处于桶下面的物品才能取出。

• 在java中也提供了这种数据结构，位于java.util包下，名称为Stack。以下是有关Stack的一些常用操作

• //初始化
  Stack<Integer>stack = new Stack<>();
  //向栈中存放数据
  stack.push(1);
  //取出栈顶元素
  int x = stack.pop();
  //查看栈顶元素
  int top = stack.peek();
  //移除栈中对应的元素
  stack.remove(1);
  //查看栈是否为空
  stack.isEmpty();
  //返回栈的大小
  stack.size();
  //翻转栈
  Collections.reverse(stack);
  <hr>
  
  
  [LeetCode155](https://leetcode.cn/problems/min-stack)
  
  ​	本题要求实现一个最小栈，与普通栈相比，多了一个返回栈中最小值的功能(要求时间复杂度为常数级别)。我一开始的思路是打算用优先队列来做的，但不知道为什么过不了。以上问题已解决，主要是在定义优先队列的排序规则时使用了减法导致数据溢出，代码如下：
  
  ```java
  class MinStack {
      private Stack<Data> stack;
      private int index;
      private PriorityQueue<Data>heap;
      public MinStack() {
          stack = new Stack<>();
          heap = new PriorityQueue<>(new Comparator<Data>(){
              public int compare(Data a,Data b){
                  return a.getData() - b.getData();
              }
          });
          index = 0;
      }
      
      public void push(int val) {
          Data data = new Data(val,index++);
          stack.push(data);
          heap.add(data);
      }
      
      public void pop() {
          Data data = stack.pop();
          heap.remove(data);
      }
      
      public int top() {
          return stack.peek().getData();
      }
      
      public int getMin() {
          return heap.peek().getData();
      }
  }
  //设计这个类来避免优先队列remove时将所有的数字都移除，比如heap中有1，2，2，这时执行heap.remove(2),就会将所有2移除，而我们只是想要移除其中一个2.
  class Data{
      private int data;
      private int ord;
  
      public Data(){};
      public Data(int data,int ord){
          this.data = data;
          this.ord = ord;
      }
  
      public int getData(){
          return data;
      }
  }
  

以下是看了题解后的写法，题解的做法是使用辅助栈。因为由于栈具有先进后出的特点，只要上面的数不被弹出，那么下面的数就一定还在栈中，因此可以使用一个辅助栈来记录每个状态下，栈的最小值，相当于维护一个前缀最小值。

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer>tempStack;
    public MinStack() {
        stack = new Stack<>();
        tempStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(tempStack.isEmpty()){
            tempStack.push(val);
        }else{
            int top = tempStack.peek();
            if(top > val)tempStack.push(val);
            else tempStack.push(top);
        }
    }
    
    public void pop() {
        stack.pop();
        tempStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return tempStack.peek();
    }
}