【LC】用栈实现队列,用队列实现栈,设计循环队列

我不是女神ヾ 2023-09-26 11:11 18阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  1. 用栈实现队列(lc232)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  2. 用队列实现栈(lc225)
 *   *  题目描述:
     *  解题思路：
     *  提交结果：
 *  3. 设计循环队列(lc622)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：

## 1. 用栈实现队列(lc232) ##

### 题目描述: ###

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

*  void push(int x) 将元素 x 推到队列的末尾
 *  int pop() 从队列的开头移除并返回元素
 *  int peek() 返回队列开头的元素
 *  boolean empty() 如果队列为空，返回 true ；否则，返回 false

**说明**：

*  你 **只能** 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

**示例 1**：

输入：

\[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”\]

\[\[\], \[1\], \[2\], \[\], \[\], \[\]\]

输出：

\[null, null, null, 1, 1, false\]

解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: \[1\]

myQueue.push(2); // queue is: \[1, 2\] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is \[2\]

myQueue.empty(); // return false

**提示**：

1 <= x <= 9

最多调用 100 次 push、pop、peek 和 empty

假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

**进阶**

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/implement-queue-using-stacks][https_leetcode.cn_problems_implement-queue-using-stacks]

### 解题思路： ###

题目要求使用栈来实现队列，栈是先进后出表，队列是先进先出表，我们考虑两个栈来实现队列，分别称这两个栈为栈1，栈2。

栈1用来入队，就是说入队的所有元素都往栈1里面放，出队在栈2执行，如果栈2是空的，则将栈1里面所有的元素出栈，放入栈2，这样从栈1入，栈2出的元素满足了先进先出的原则，这样也就用两个栈实现了队列;

当两个栈均为空时，表示队列为空。

### 代码实现： ###

class MyQueue {
        
    
        private Stack<Integer> s1;
        private Stack<Integer> s2;
        public MyQueue() {
        
            s1 = new Stack<>();
            s2 = new Stack<>();
        }
        
        public void push(int x) {
        
            s1.push(x);
        }
        
        public int pop() {
        
            if(empty()) {
        
                return -1;
            }
            if(s2.isEmpty()) {
        
                while(!s1.isEmpty()) {
        
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }
        
        public int peek() {
        
            if(empty()) {
        
                return -1;
            }
            if(s2.isEmpty()) {
        
                while(!s1.isEmpty()) {
        
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }
        
        public boolean empty() {
        
            return s1.isEmpty() && s2.isEmpty();
        }
    }

### 提交结果： ###

![img][]

## 2. 用队列实现栈(lc225) ##

### 题目描述: ###

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

*  void push(int x) 将元素 x 压入栈顶。
 *  int pop() 移除并返回栈顶元素。
 *  int top() 返回栈顶元素。
 *  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

*  你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
 *  你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

**示例**：

输入：

\[“MyStack”, “push”, “push”, “top”, “pop”, “empty”\]

\[\[\], \[1\], \[2\], \[\], \[\], \[\]\]

输出：

\[null, null, null, 2, 2, false\]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

**提示**：

*  1 <= x <= 9
 *  最多调用100 次 push、pop、top 和 empty
 *  每次调用 pop 和 top 都保证栈不为空

**进阶**: 你能否仅用一个队列来实现栈。

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/implement-stack-using-queues][https_leetcode.cn_problems_implement-queue-using-stacks]

### 解题思路： ###

*  **思路1**

可以使用两个队列来实现本题, 分别称这两个队列为队1, 队2, 进队和出队永远往非空队列操作，如果进队时两个队列均为空，则任选一个队列入队;

入栈时，哪一个队列不为空，就在哪一个队列入队;

出栈时，先找到不为空的队列，然后获取该队列的大小size，将前size-1个元素转移到另一个队列，剩下最后一个元素出队返回，这样就实现了栈后进先出的特点, 同时保证了一个队列为空，另一个队列不为空;

获取栈顶元素，与出栈思路一样, 稍微有一点区别就是最后一个元素也需要放入到另一个栈中.

*  **思路2**

使用一个队列，队列是先进先出，栈是先进后出，在入栈前，我们先保存入队前的元素个数size，然后再进行新元素入队，最后将所有的旧元素重新入队（就是对所有的旧元素先出队再入队），这样做可以将旧元素（先进队列的元素）全部排在新元素（后进队的元素），这样在这个队列中，新元素总是能够排在队头，实现了栈的后进先出的特点。

//方法二: 使用一个栈
    class MyStack {
        
        Queue<Integer> qu;
        public MyStack() {
        
            qu = new LinkedList<>();
        }
    
        public void push(int x) {
        
            int size = this.qu.size();
            this.qu.offer(x);
            while(size != 0) {
        
                this.qu.offer(this.qu.poll());
                size--;
            }
        }
    
        public int pop() {
        
            if(this.empty()) {
        
                return -1;
            }
            return this.qu.poll();
        }
    
        public int top() {
        
            if(this.empty()) {
        
                return -1;
            }
            return this.qu.peek();
        }
    
        public boolean empty() {
        
            return this.qu.isEmpty();
        }
    }
    
    //方法一: 使用两个栈
    /*
    class MyStack {
        private Queue<Integer> qu1;
        private Queue<Integer> qu2;
        public MyStack() {
            qu1 = new LinkedList<>();
            qu2 = new LinkedList<>();
        }
    
        public void push(int x) {
            if(!qu1.isEmpty()) {
                qu1.offer(x);
            }else if(!qu2.isEmpty()) {
                qu2.offer(x);
            }else {
                qu1.offer(x);
            }
        }
    
        public int pop() {
            if(empty()) {
                return -1;
            }
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                for(int i = 0; i < size-1; i++) {
                    qu2.offer(qu1.poll());
                }
                return qu1.poll();
            }else {
                int size = qu2.size();
                for(int i = 0; i < size-1; i++) {
                    qu1.offer(qu2.poll());
                }
                return qu2.poll();
            }
        }
    
        public int top() {
            if(empty()) {
                return -1;
            }
    
            int ret = -1;
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                for(int i = 0; i < size; i++) {
                    ret = qu1.poll();
                    qu2.offer(ret);
                }
            }else {
                int size = qu2.size();
                for(int i = 0; i < size; i++) {
                    ret = qu2.poll();
                    qu1.offer(ret);
                }
            }
            return ret;
        }
    
        public boolean empty() {
            return qu1.isEmpty() && qu2.isEmpty();
        }
    
        public static void main(String[] args) {
            MyStack myStack = new MyStack();
            myStack.push(1);
            myStack.push(2);
            System.out.println(myStack.top());
        }
    }*/

### 提交结果： ###

![img][img 1]

## 3. 设计循环队列(lc622) ##

### 题目描述: ###

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

*  MyCircularQueue(k): 构造器，设置队列长度为 k 。
 *  Front: 从队首获取元素。如果队列为空，返回 -1 。
 *  Rear: 获取队尾元素。如果队列为空，返回 -1 。
 *  enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 *  deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 *  isEmpty(): 检查循环队列是否为空。
 *  isFull(): 检查循环队列是否已满。

**示例**：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3

circularQueue.enQueue(1); // 返回 true

circularQueue.enQueue(2); // 返回 true

circularQueue.enQueue(3); // 返回 true

circularQueue.enQueue(4); // 返回 false，队列已满

circularQueue.Rear(); // 返回 3

circularQueue.isFull(); // 返回 true

circularQueue.deQueue(); // 返回 true

circularQueue.enQueue(4); // 返回 true

circularQueue.Rear(); // 返回 4

**提示**：

*  所有的值都在 0 至 1000 的范围内；
 *  操作数将在 1 至 1000 的范围内；
 *  请不要使用内置的队列库。

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/design-circular-queue][https_leetcode.cn_problems_design-circular-queue]

### 解题思路： ###

循环队列需要用顺序表，以循环的形式实现，难点在于判定队列是否满，是否为空;

主要有三种判断方式, 分别是:

1.  通过添加 size 属性记录
2.  保留一个位置
3.  使用标记

具体思想可以看我另一篇博客循环队列的部分: [链接][Link 1]

这里采用第一种方法来实现, **记录队列元素个数count，当count的值与顺序表的长度相等时，代表队列已满 ; count值为0表示队列为空**。

*  第一步，按照题目要求，根据传入的参数k创建顺序表大小。
 *  第二步，记录队列元素个数count，当count的值与顺序表的大小相等时，代表队列已满。size值为0表示队列为空。
 *  第三步，确定下标怎么变化，记顺序表长度为len，设置front指向队首元素, rear指向尾(下一次入队时的位置), 下标是由0n-1,n-10进行变化，所以进行下标前移时rear = (rear+1)%len，front = (front+1)% len。

要注意的是获取队尾元素需要拿到队尾元素的下标, 一般情况下是rear - 1, 但如果队尾元素在数组的最后一个位置, 此时rear-1是-1就会出现问题, 此时应该用len-1来表示队尾元素下标.

![img][img 2]

### 代码实现： ###

class MyCircularQueue {
        
    
        private int[] elem;
        private int front;//队头
        private int rear;//队尾
        private int count;//计数器
    
        public MyCircularQueue(int k) {
        
            elem = new int[k];
        }
    
        public boolean enQueue(int value) {
        
           if(isFull()) {
        
               return false;
           }
           elem[rear] = value;
           rear = (rear+1) % elem.length;
           count++;
           return true;
        }
    
        public boolean isFull() {
        
            if(count == elem.length) {
        
                return true;
            }
            return false;
        }
    
        public boolean deQueue() {
        
            if(isEmpty()) {
        
                return false;
            }
            front = (front+1)% elem.length;
            count--;
            return true;
        }
        
        public boolean isEmpty() {
        
            if(count == 0) {
        
                return true;
            }
            return false;
        }
    
        public int Front() {
        
            if(isEmpty()) {
        
                return -1;
            }
            return elem[front];
        }
    
        public int Rear() {
        
            if(isEmpty()) {
        
                return -1;
            }
            int index = rear == 0 ? elem.length-1 : rear - 1;
            return elem[index];
        }
    }

### 提交结果： ###

![img][img 3]

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11990219.html?spm=1001.2014.3001.5482
[https_leetcode.cn_problems_implement-queue-using-stacks]: https://leetcode.cn/problems/implement-queue-using-stacks
[img]: https://img-blog.csdnimg.cn/img_convert/f80fce4f2d81292fed33a999f1d17ca5.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/0e382076c6ff840217fe828f27ed398b.png
[https_leetcode.cn_problems_design-circular-queue]: https://leetcode.cn/problems/design-circular-queue
[Link 1]: http://t.csdn.cn/K8o8K
[img 2]: https://img-blog.csdnimg.cn/img_convert/4d1ed50118016e310a495a2ac890999b.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/397d2d3288f2aa41cd1a4892729502d9.png