Leetcode刷题100天—225.用队列实现栈(栈)—day04

傷城~ 2022-09-05 12:56 176阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![image-20210816224740405][]

请你仅使用两个队列实现一个后入先出（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** 都保证栈不为空

**进阶**：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

> 来源：力扣（LeetCode）
> 
> 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
> 
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

package 队列;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /* * https://leetcode-cn.com/problems/implement-stack-using-queues/ * 原理解析：比如有元素[2,9,3] * in out * -------- * 2 null * null 2 * -------- * 9 2 * 29 null * null 29 * -------- * 3 29 * 293 null * -------- * 出队:392,完成出栈操作 */
    public class _225_用队列实现栈 { 
    	Queue<Integer> inqueue;
    	Queue<Integer> outqueue;
    	/** Initialize your data structure here. 设置队列*/
        public _225_用队列实现栈() { 
        	inqueue=new LinkedList<Integer>() ;
        	outqueue=new LinkedList<Integer>();
        }
        
        /** Push element x onto stack. 入队*/
        public void push(int x) { 
    // 将输入的一个个x值入队
        	inqueue.offer(x);
    // if(outqueue)
    // 循环判断outqueue是否为空
        	while(!outqueue.isEmpty()) { 
        		inqueue.offer(outqueue.poll());
        	}
    // 设置指针temp,然后将inqueue和outqueue的值相互替换
        	Queue<Integer> temp=inqueue;
    // 这里道理相当于重新将inqueue的值设置为空，因为outqueue会将值poll出栈
        	inqueue=outqueue;
    // 将入队的值存入outqueue
        	outqueue=temp;
        }
        
        /**出队 Removes the element on top of the stack and returns that element. */
        public int pop() { 
        	return outqueue.poll();
        }
        
        /** Get the top element. */
        public int top() { 
        	return outqueue.peek();
        }
        
        /** Returns whether the stack is empty. */
        public boolean empty() { 
        	return outqueue.isEmpty();
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210816224740405]: /images/20220829/10a3afba09874eb8921d407b1d214a57.png