Stack

栈刷题总结

1.有效的括号

知识点补充：

stack.pop()和stack.peek的区别：

相同点：大家都返回栈顶元素

不同点：satck.pop()返回栈顶元素后会将栈顶元素删除，而stack.peek()只返回不删除

//栈+哈希表
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n%2==1){
            return false;
        }
        Map<Character,Character> pairs = new HashMap<Character,Character>();
        pairs.put(']','[');
        pairs.put('}','{');
        pairs.put(')','(');

        Deque<Character> stack = new LinkedList<Character>();
        for(int i=0;i<n;i++){
          char ch = s.charAt(i);
            if(pairs.containsKey(ch)){
                if(stack.isEmpty()||stack.peek()!=pairs.get(ch)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

2.比较含退格的两个字符串

####2.1方法一：重构字符串(利用StringBuffer的可扩展性)

用栈处理字符串，如果是需要删除的元素，就将其出栈，如果是需要压入栈的元素，就使其入栈

iii Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str){
        StringBuffer ret = new StringBuffer();
        int length = str.length();

        for(int i=0;i<length;i++){
            char ch = str.charAt(i);
            if(ch!='#'){
                ret.append(ch);
            }else{
                if(ret.length()>0){
                    ret.deleteCharAt(ret.length()-1);
                }
            }
        }
        return ret.toString();
        
       //不是String类型的想转换为String类型直接引用toString()方法就行
    }
}

时间和空间度均为O(M+N)。

2.2双指针

//暂时不懂，后期可以再看一下官方题解

时间复杂度为O(M+N),空间复杂度为O(1)。

2.3栈

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str){
        Stack<Character> stack  = new Stack();
        for(int i=0;i<str.length();i++){
            Character C = str.charAt(i);
            if(C!='#'){
                stack.push(C);
            }else if(!stack.isEmpty()){        //要考虑到栈不为空的条件
                stack.pop();
            }
        }
        return stack.toString();
    }
}

3.化栈为队

class MyQueue {
    private Stack<Integer>stack1;
    private Stack<Integer>stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

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

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

4.用两个栈实现队列

#####实现队列最直观的方式是链表，但是用栈stack也可以

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }else if(!stack2.isEmpty()){
            return stack2.pop();
        } 
        return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

5.用栈实现队列

为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。

//方法一：使用两个栈来执行入队O(n)和出队O(1)操作
class MyQueue {
    private Stack<Integer>stack1;
    private Stack<Integer>stack2;
    private int front;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack1.isEmpty()){
            front = x;
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        stack2.push(x);
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
      int s =  stack1.pop();
        if(!stack1.isEmpty()){
            front = stack1.peek();    //j将新的栈顶元素赋值给front
        }
        return s;
    }
    
    /** Get the front element. */
    public int peek() {
       return stack1.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

//方法二：使用两个栈来执行入队O(1)和出队O(1)操作
class MyQueue {
    private Stack<Integer>stack1;
    private Stack<Integer>stack2;
    private int front;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack1.isEmpty()){
            front = x;   //代表每次stack1空了之后，再压入的队首元素会更新。
        }
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
      if(stack2.isEmpty()){
          while(!stack1.isEmpty()){
              stack2.push(stack1.pop());
          }
      }
      return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(!stack2.isEmpty()){
            return stack2.peek();
        }
        return front;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}
//使用front来保存队首元素，确保在peek()操作时，如果stack2是空的，可以直接返回之前保存的队首元素。
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

6.用队列实现栈

6.1使用两个队列

一个队列用于存储栈内元素，另一个队列作为辅助栈。

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();

    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();   //queue1此时就是按照栈的顺序来存储元素的，所以直接poll即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

6.2LinkedList作为堆栈和链表使用的总结

ava里的LinkedList可以同时作为堆栈和队列使用，因此在使用的时候总是会弄混他们的方法，此文就简单总结一下作为不同数据结构使用时的用法。

作为队列

方法

声明

任意两种方法：

• 一是直接声明LinkedList：
  LinkedList<T> q = new LinkedList<T>();
• 或者使用java.util.Queue接口，其底层关联到一个LinkedList实例。
  Queue<T> q = new LinkedList<T>();
  由于只暴露部分基于队列实现的接口，所以可以提供安全的队列实现。

入队

void offer(T v)

出队

• T poll(), 如果队列为空，则返回null
• T remove(), 如果队列为空，则抛出异常

看看队首元素不移除它。

• T peek(), 如果队列为空，则返回null
• T element(), 如果队列为空，则抛出异常

是否为空

• boolean isEmpty(), 空返回true，否则返回false

作为堆栈

方法

声明

任意两种方法：

• 一是直接声明LinkedList：
  LinkedList<T> stack = new LinkedList<T>();
• 请注意，LinkedList实现的堆栈名称是Deque:
  Deque<T> stack = new LinkedList<T>();
  由于只暴露部分基于堆栈实现的接口，所以可以提供安全的队列实现。

入栈

void addFirst(T v)
void push(T v)

出栈

• T pop()
• T poll()

peek()

看看队首元素不移除它。

• T peek(), 如果队列为空，则返回null
• T element(), 如果队列为空，则抛出异常

是否为空

• boolean isEmpty(), 空返回true，否则返回false

####6.3用一个队列实现

class MyStack {
    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for(int i=0;i<n;i++){
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

7.棒球比赛

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack();
        for(String op:ops){
            if(op.equals("+")){
                int top = stack.pop();
                int newtop = top+stack.peek();
                stack.push(top);
                stack.push(newtop);
            }else if(op.equals("C")){
                stack.pop();
            }else if(op.equals("D")){
                stack.push(2*stack.peek());
            }else{
                stack.push(Integer.valueOf(op));
            }
        }
        int ans=0;
        for(int n:stack){
            ans = ans+n;
        }
        return ans;
    }
}

8.用栈操作构建数组

9.删除最外层的括号