LeetCode刷题：栈和队列的相关题目

<font size="4">大家如果对于队列的性质等不太了解的话，我推荐一篇博客，写得很细节，大家可以去看看栈 和 队列 【 Stack And Queue】- java - 细节决定一切</font>

<font size="4" color="red">我们要注意一个点，栈是先进后出，队列是先进先出，用一个栈是很难实现队列的,我们可以让一个栈用来入队列，另外一个栈来出队列</font>

1.1思路

<font size="4" color="wwfegrgrgr4rg4444wetgrwfblue">入队:先把所有元素放到栈A中(栈B用来出队)
出队:先把栈A中的所有元素出栈进入到栈B中，然后栈B的栈顶元素就是要出队的元素
取队首元素：和出队操作类似，先把A元素进入到B，取栈B的栈顶元素
判断是否为空：看A和B是否同时为空</font>

1.2图示

1.3代码

class MyQueue { 
    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() { 
        stackIn=new Stack();
        stackOut=new Stack();
    }
    //入队
    public void push(int x) { 
        if(stackOut.isEmpty()){ 
            stackIn.push(x);
        }else{ 
            while(!stackOut.isEmpty()){ 
                stackIn.push(stackOut.pop());
            }
            stackIn.push(x);
        }
    }
    
    public int pop() { 
        while(!stackIn.isEmpty()){ 
            stackOut.push( stackIn.pop());
        }
        return stackOut.pop();
    }
    
    public int peek() { 
          while(!stackIn.isEmpty()){ 
            stackOut.push( stackIn.pop());
        }
        return stackOut.peek();
    }
    
    public boolean empty() { 
        return stackIn.isEmpty() && stackOut.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(); */

用队列实现栈

• 仅仅使用两个队列实现栈的四种操作(push,pop,tip,empty)
• 我们只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

2.2思路

一个队列为主队列，一个为辅助队列，当入栈操作时，我们先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。

2.2代码

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

    public MyStack() { 
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    public void push(int x) { 
        queue2.offer(x);
        while (!queue1.isEmpty()) { 
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() { 
        return queue1.poll();
    }
    
    public int top() { 
        return queue1.peek();
    }
    
    public boolean empty() { 
        return queue1.isEmpty();
    }
}

题目链接 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

3.1思路

• 因为要求在常数时间内检索到最小元素，所以用一个栈是无法达到的，因为需要O(n)
• 我们可以用一个辅助栈B来存放栈的最小元素，那么直接取出辅助栈的栈顶元素就是栈的最小元素
• 入栈的话，A直接入栈，B如果为空，则直接入栈，B如果不是空，则比较B的栈顶和A的大小关系，如果待入栈元素比B栈顶元素小，则入B
• 取栈顶：直接取A栈顶
• 取最小元素：直接取B栈顶元素

3.2图示

下面的流程图来自博主独一无二的哈密瓜

3.3代码

class MinStack { 
    //使用两个栈
    private Stack<Integer> stack;
     private Stack<Integer> minStack;
    public MinStack() { 
        stack=new Stack();
        minStack=new Stack();
    }
    
    public void push(int val) { 
        stack.push(val);
        if(minStack.isEmpty()){ 
            minStack.push(val);
        }else{ 
            if(val<=minStack.peek()){ 
                minStack.push(val);
            }
        }
    }
    
    public void pop() { 
        if(!stack.isEmpty()){ 
            int val=stack.pop();
            if(val==minStack.peek()){ 
                minStack.pop();
            }
        }
    }
    
    public int top() { 
        return stack.peek();
    }
    
    public int getMin() { 
        return minStack.peek();
    }
}

/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

删除字符串中所有相邻重复项

4.1思路

• 我们可以使用栈来完成
• 当栈为空，则把字符直接加入栈中
• 如果栈非空

- 若栈顶元素和待加入元素相等，则栈顶元素出栈 - 若栈顶元素和待加入元素不相等，则该元素入栈

• 最后把栈中所有元素出栈，然后反转就是结果，为了简单一点，我们可以使用ArrayDeque双端队列

4.2代码

class Solution { 
    public String removeDuplicates(String S) { 
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) { 
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) { 
                deque.push(ch);
            } else { 
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) { 
            str = deque.pop() + str;
        }
        return str;
    }
}