用栈实现队列(LeetCode 232)

简介: 用栈实现队列(LeetCode 232)

用栈实现队列(LeetCode 232)

Description

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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(双端队列)来模拟一个栈,只要是标准的栈操作即可。

Sample Input 1

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Sample Output 1

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

Sample Tips 1

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

Tips

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

算法思想:

使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。

执行语句:

queue.push(1);

queue.push(2);

queue.pop(); 注意此时的输出栈的操作

queue.push(3);

queue.push(4);

queue.pop();

queue.pop();注意此时的输出栈的操作

queue.pop();

queue.empty();

在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。

判断队列为空:如果进栈和出栈都为空的话,说明模拟的队列为空了。**

在代码实现的时候,会发现pop() 和 peek()两个函数功能类似,代码实现上也是类似的,可以思考一下如何把代码抽象一下。

C++代码如下:

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /** Initialize your data structure here. */
    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stackIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {    
        dumpstackIn();
        return stackOut.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut为空,那么将stackIn中的元素全部放到stackOut中
    private void dumpstackIn(){
        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }
}

Java代码代码如下:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针,从头结点和相遇结点,各走一步,直到相遇,相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
目录
相关文章
LeetCode 热题100——单调栈
LeetCode 热题100——单调栈
19 0
|
2月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
34 6
|
4月前
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点
|
4月前
【Leetcode 1944】队列中可以看到的人数 —— 单调栈
解题思路:维持一个单调递增栈来辅助计算每个人能够看到的人数。从右往左遍历数组,对于每个人,我们将其身高与栈顶元素的身高进行比较。如果当前人的身高比栈顶元素的身高高,则栈顶元素无法被当前人看到,将其出栈,并累计计数
LeetCode | 232. 用栈实现队列
LeetCode | 232. 用栈实现队列
|
5天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
6 0
|
27天前
|
C语言
Leetcode每日一题——“用栈实现队列”
Leetcode每日一题——“用栈实现队列”
|
27天前
|
C语言
Leetcode每日一题——“用队列实现栈”
Leetcode每日一题——“用队列实现栈”
|
2月前
|
存储
leetcode1944. 队列中可以看到的人数
leetcode1944. 队列中可以看到的人数
16 0
|
2月前
|
算法 安全 Java
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
22 0