栈的基本使用

2020-03-30

栈

后进先出(LIFO-last in first out):最后插入的元素最先出来

Leetcode 20、有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

由于题目的要求，判断字符串是否有效，这时候我们就可以利用栈的特性。

首先我们将左括号全部压入栈
然后只需要一一比对，就能得出正确答案

public class Solution {
    public boolean isValid(String s) {

       Stack<Character> stack=new Stack<>();

       for(int i=0;i<s.length();i++){
           char c=s.charAt(i);
           //如果是向左的，压入栈
           if(c=='('||c=='{'||c=='[')
           stack.push(c);
           else{
               //先判断栈是否为空，空的话不匹配
               if(stack.isEmpty()){
                   return false;
               }  
                //取出栈顶元素进行比较。
           char top=stack.pop();
          if(top=='('&&c!=')')
          return false;
          if(top=='{'&&c!='}')
          return false;
          if(top=='['&&c!=']')
          return false;
           }
       }
       return stack.isEmpty();
    }
}

Leetcode 155、最小栈

https://leetcode-cn.com/problems/min-stack/

题目的意思是设计一个支持push，pop，top操作栈，并且能够检索出栈中的最小元素

这时候我们可以利用两个栈，一个正常的栈，另外一个最小栈。我们取最小元素的时候直接从最小栈中去取即可。

class MinStack {
      private Stack<Integer> stack;
      private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
      //当该元素比最小栈中栈顶的元素小，压入栈
      //如果此时栈中元素为 1423 
        if(minStack.isEmpty()||x<minStack.peek()){
            minStack.push(x);
          //否则的话，将较小元素压入栈
          //那么此时最小栈中元素应该为1111
        }else{
            minStack.push(minStack.peek());
        }
    }
    public void pop() {
      stack.pop();
      minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

除了以上利用两个栈来实现一个最小栈，我们还可以用两个栈来实现一个队列

队列也是一种全新的数据结构
与栈相对应的，队列是先进先出（FIFO）

Leetcode232、用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

通过以上的说明，既然队列是先进先出的结构，我们只要利用两个栈。便可以轻而易举的实现

class MyQueue {

      private Stack<Integer> stack1;
      private Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();

    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        //元素统一push到第一个栈里面
        stack1.push(x);

    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        //最开始的时候stack2肯定为空,所以要将stack1的元素压入stack2
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
        

    }
    
    /** Get the front element. */
    public int peek() {

 if(!stack2.isEmpty()){
            return stack2.peek();
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.peek();
        
       

    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();

    }
}

单次pop操作的时间复杂度为O(1)。

即便在while循环中，最坏的复杂度为O(n)。但是pop操作n次,前面必然有n次push操作，所以平均时间复杂度还是O(1)。