堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象数据类型,只允许在有序的线性数据集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。
LeetCode232题
两个栈组成一个队列
思想:两个栈,一个input ,一个 output , 进入队列都从 input 输入,出队列都从output 出。但是要注意的是 pop, 或者 peek 时,注意如果output 是空的需要将input 中的内容都放到 output 中。如果 output 不为空,就将 input 倒入,会破坏队列的结构。
import java.util.Stack; /** * 类说明 使用栈实现队列的下列操作: * * push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- * 返回队列是否为空。 * * 示例: * * MyQueue queue = new MyQueue(); * * queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 * queue.empty(); // 返回 false * * 来源:力扣(LeetCode) * 链接:https://leetcode-cn.com/problems/implement-queue-using-stacks * 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 * * <pre> * Modify Information: * Author Date Description * ============ =========== ============================ * wangm 2020年4月18日 Create this file * </pre> * */ class MyQueue { Stack<Integer> input; Stack<Integer> output; /** Initialize your data structure here. */ public MyQueue() { input = new Stack<Integer>(); output = new Stack<Integer>(); } public void transfer() { if (output.isEmpty()) { while (!input.isEmpty()) { int x = input.pop(); output.push(x); } } } /** Push element x to the back of queue. */ public void push(int x) { input.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { transfer(); return output.pop(); } /** Get the front element. */ public int peek() { transfer(); return output.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { if (input.isEmpty() && output.isEmpty()) { return true; } else { return false; } } } /** * * 类说明 思想: 两个栈,一个input ,一个 output , 进入队列都从 input 输入,出队列都从output 出。但是要注意的是 pop, * 或者 peek 时,注意如果output 是空的需要将input 中的内容都放到 output 中。 如果 output 不为空,就将 input * 倒入,会破坏队列的结构。 * * <pre> * Modify Information: * Author Date Description * ============ =========== ============================ * wangm 2020年4月18日 Create this file * </pre> * */ public class LeetCode232 { /** * @param args */ public static void main(String[] args) { MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); System.out.println(queue.peek()); // 返回 1 System.out.println(queue.pop()); // 返回 1 System.out.println(queue.empty()); // 返回 false } }