堆栈

王小明_HIT

发布于 2020-04-21 07:55:54

1.1K00

代码可运行

文章被收录于专栏：程序员奇点程序员奇点

运行总次数：0

代码可运行

堆栈（英语：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();
        queue.push();
        System.out.println(queue.peek()); // 返回 1
        System.out.println(queue.pop()); // 返回 1
        System.out.println(queue.empty()); // 返回 false
    }

}