Leetcode刷题100天—232. 用栈实现队列（队列）—day02

小鱼儿 2022-08-29 10:09 149阅读 0赞

前言：

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

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（`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`（双端队列）来模拟一个栈，只要是标准的栈操作即可。

**进阶**：

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

示例：

输入：
    ["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 操作）

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

### 代码 ###

package 队列;
    
    import java.util.Stack;
    
    /* * 运智 * 1 * https://leetcode-cn.com/problems/implement-queue-using-stacks/ * 请你仅使用两个栈实现先入先出队列。 */
    public class _232_用栈实现队列 { 
    // 设置栈，由于他是int类型的元素，所以这里用Integer
    	private  Stack<Integer> inStack;
    	private  Stack<Integer> outStack;
    	/** Initialize your data structure here. 设置两个栈*/
        public _232_用栈实现队列() { 
    // new两个栈
        	inStack=new Stack<>();
        	outStack = new Stack<>();
        }
        
        /** Push element x to the back of queue. 入队*/
        public void push(int x) { 
        	inStack.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element.出队 */
        public int pop() { 
    // 通过判断两个栈是否为空来做出入栈出栈操作
        	if (outStack.isEmpty()) { 
    			while(!inStack.isEmpty()) { 
    				outStack.push(inStack.pop());
    			}
    		}
        	return outStack.pop();
        }
        
        /** Get the front element.获取队头元素 */
        public int peek() { 
        	if (outStack.isEmpty()) { 
    			while(!inStack.isEmpty()) { 
    				outStack.push(inStack.pop());
    			}
    		}
    // jdk官方获取栈顶元素用peek
        	return outStack.peek();
        }
        
        /** Returns whether the queue is empty.是否为空 */
        public boolean empty() { 
        	return inStack.isEmpty() && outStack.isEmpty();
        }
        
    }

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