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

ゝ一世哀愁。 2023-09-28 15:30 36阅读 0赞

####  ####

*  前言
 *  1.用栈来实现队列
 *   *  1.1思路
     *  1.2图示
     *  1.3代码
 *  2.用队列来实现栈
 *   *  2.2思路
     *  2.2代码
 *  3.最小栈
 *   *  3.1思路
     *  3.2图示
     *  3.3代码
 *  4.删除字符串中所有相邻重复项
 *   *  4.1思路
     *  4.2代码

## 前言 ##

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

## 1.用栈来实现队列 ##

> ![在这里插入图片描述][e5ce97fabbda4aeba6224afc5375cb1c.png]  
> ![在这里插入图片描述][3b5f56fbafcd412d9eb8216a8d65ae58.png]  
> 我们要注意一个点，栈是先进后出，队列是先进先出，用一个栈是很难实现队列的,我们可以让一个栈用来入队列，另外一个栈来出队列

### 1.1思路 ###

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

### 1.2图示 ###

![在这里插入图片描述][50919b45cf084cc4817c6cda4f4ca689.png]  
![在这里插入图片描述][58f9549817f34ecf921b869ffa01f8dc.png]  
![在这里插入图片描述][102d1af9e7634ac6a26b97e12dd732a9.png]  
![在这里插入图片描述][b595419676d34b98b7890ca7c54631f5.png]

### 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();
     */

## 2.用队列来实现栈 ##

[用队列实现栈][Link 1]

*  仅仅使用两个队列实现栈的四种操作(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();
        }
    }

## 3.最小栈 ##

题目链接[最小栈][Link 2]  
设计一个支持 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图示 ###

下面的流程图来自博主独一无二的哈密瓜  
![在这里插入图片描述][57f551e0333f4288bb0c212544ef6383.png]  
![在这里插入图片描述][63a8a08fda414bc78acbf050e0c00b32.png]

### 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.删除字符串中所有相邻重复项 ##

[删除字符串中所有相邻重复项][Link 3]  
![在这里插入图片描述][ba893d9997b74a5fa0a303178cb27368.png]

### 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;
        }
    }

[_ _ _ Stack And Queue_- java -]: https://blog.csdn.net/DarkAndGrey/article/details/122511544
[e5ce97fabbda4aeba6224afc5375cb1c.png]: https://img-blog.csdnimg.cn/e5ce97fabbda4aeba6224afc5375cb1c.png
[3b5f56fbafcd412d9eb8216a8d65ae58.png]: https://img-blog.csdnimg.cn/3b5f56fbafcd412d9eb8216a8d65ae58.png
[50919b45cf084cc4817c6cda4f4ca689.png]: https://img-blog.csdnimg.cn/50919b45cf084cc4817c6cda4f4ca689.png
[58f9549817f34ecf921b869ffa01f8dc.png]: https://img-blog.csdnimg.cn/58f9549817f34ecf921b869ffa01f8dc.png
[102d1af9e7634ac6a26b97e12dd732a9.png]: https://img-blog.csdnimg.cn/102d1af9e7634ac6a26b97e12dd732a9.png
[b595419676d34b98b7890ca7c54631f5.png]: https://img-blog.csdnimg.cn/b595419676d34b98b7890ca7c54631f5.png
[Link 1]: https://leetcode.cn/problems/implement-stack-using-queues/
[Link 2]: https://leetcode.cn/problems/min-stack/
[57f551e0333f4288bb0c212544ef6383.png]: https://img-blog.csdnimg.cn/57f551e0333f4288bb0c212544ef6383.png
[63a8a08fda414bc78acbf050e0c00b32.png]: https://img-blog.csdnimg.cn/63a8a08fda414bc78acbf050e0c00b32.png
[Link 3]: https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
[ba893d9997b74a5fa0a303178cb27368.png]: https://img-blog.csdnimg.cn/ba893d9997b74a5fa0a303178cb27368.png