首页 > 代码库 > LeetCode 225 Implement Stack using Queues

LeetCode 225 Implement Stack using Queues

2024-08-12 00:21:57   210人阅读

Implement the following operations of a stack using queues.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • empty() -- Return whether the stack is empty.

Notes:

    • You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
    • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
    • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

 

思路：

基本上还是通过两个队列去实现，在实现栈的出栈操作的时候，将主队列中的元素出队至备用队列中，将队尾元素留下并弹出，再将备用队列中的元素出队至主队列中即可。而返回栈顶元素的方法大同小异，区别仅在于是否需要将队尾元素删除。

 

解法：

 1 import java.util.Queue; 2  3 public class MyStack 4 { 5     private Queue<Integer> mainQueue; 6     private Queue<Integer> tempQueue; 7  8     public MyStack() 9     {10         mainQueue = new LinkedList<>();11         tempQueue = new LinkedList<>();12     }13 14     public void push(int x)15     { mainQueue.offer(x); }16 17     public void pop()18     {19         while(mainQueue.size() > 1)20             tempQueue.offer(mainQueue.poll());21         mainQueue.poll();22         while(!tempQueue.isEmpty())23             mainQueue.offer(tempQueue.poll());24     }25 26     public int top()27     {28         while(mainQueue.size() > 1)29             tempQueue.offer(mainQueue.poll());30         int topValue =http://www.mamicode.com/ mainQueue.poll();31         tempQueue.offer(mainQueue.poll());32         while(!tempQueue.isEmpty())33             mainQueue.offer(tempQueue.poll());34         return topValue;35     }36 37     public boolean empty()38     { return mainQueue.isEmpty(); }39 }

 

LeetCode 225 Implement Stack using Queues


联系
我们