225. 用队列实现栈

待我称王封你为后i 2023-10-13 22:28 118阅读 0赞

### 225. 用队列实现栈 ###

*  题干背景
 *  重要思路
 *  具体代码

# 题干背景 #

[力扣入口 - 225. 用队列实现栈][- 225.]

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈  
pop() – 移除栈顶元素  
top() – 获取栈顶元素  
empty() – 返回栈是否为空  
注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。  
你所使用的语言也许不支持队列。 你可以**使用 list** 或者 deque（双端队列）来**模拟一个队列** , 只要是标准的队列操作即可。  
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

# 重要思路 #

1.  一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） **重新添加到队列尾部**，此时再去弹出元素就是栈的顺序了。
2.  使用`Queue<Integer> queue = new LinkedList<>()`来实现队列。
3.  linkedlist链表当作栈的时候，使用push来添加值；linkedlist链表当作队列的时候，使用add添加元素添加元素。
4.  poll是队列数据结构中类似pop的操作，poll是从队首获取元素，同时将整个元素从原队列删除。

# 具体代码 #

package org.example;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class MyStack {
        
        Queue<Integer> queue;
    
        public MyStack(){
        
            queue = new LinkedList<>();
        }
    
        public void push(int x){
        
            queue.add(x);
        }
    
        public int pop(){
        
            rePosition();
            return queue.poll();
        }
    
        public int top(){
        
            rePosition();
            int result = queue.poll();
            queue.add(result);
            return result;
        }
    
        public boolean empty(){
        
            return queue.isEmpty();
        }
    
        public void rePosition(){
        
            int size = queue.size();
            size--;
            while(size-->0){
        
                queue.add(queue.poll());
            }
        }
    }

**参考资料**：[225. 用队列实现栈][225.]

[- 225.]: https://leetcode.cn/problems/implement-stack-using-queues/
[225.]: https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html