Queue & Stack

Queue, Stack

Leetcode介绍专题： https://leetcode.com/explore/learn/card/queue-stack/

<font size=2.5> 栈

push() 入栈, pop() 出栈。

队列

push to back() 入队列, peek/pop from front() 出队列。

####Example: 1.用两个先进先出的队列实现一个后进先出的栈: 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

<td bgcolor=#F5F5F> Implement the MyStack class: - void push(int x) Pushes element x to the top of the stack. - int pop() Removes the element on the top of the stack and returns it. - int top() Returns the element on the top of the stack. - boolean empty() Returns true if the stack is empty, false otherwise. 实现 MyStack 类： - void push(int x) 将元素 x 压入栈顶。 - int pop() 移除并返回栈顶元素。 - int top() 返回栈顶元素。 - boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 Notes: - Use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations. 注意： - 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列, 只要是标准的队列操作即可。 </td>

Java实现：

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        // queue入队
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        // queue出队
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

2.用两个后进先出的栈实现一个先进先出的队列: Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

<td bgcolor=#F5F5F> Implement the MyQueue class: - void push(int x) Pushes element x to the back of the queue. - int pop() Removes the element from the front of the queue and returns it. - int peek() Returns the element at the front of the queue. - boolean empty() Returns true if the queue is empty, false otherwise. 实现 MyQueue 类： - void push(int x) 将元素 x 推到队列的末尾 - int pop() 从队列的开头移除并返回元素 - int peek() 返回队列开头的元素 - boolean empty() 如果队列为空，返回 true ；否则，返回 false Notes: - You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations. 说明： - 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 </td>

java实现

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

3.最小栈： Implement the MinStack class:

<td bgcolor=#F5F5F> 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 - push(x) —— 将元素 x 推入栈中。 - pop() —— 删除栈顶的元素。 - top() —— 获取栈顶元素。 - getMin() —— 检索栈中的最小元素。 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. - MinStack() initializes the stack object. - void push(int val) pushes the element val onto the stack. - void pop() removes the element on the top of the stack. - int top() gets the top element of the stack. - int getMin() retrieves the minimum element in the stack. </td>

java实现

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        int x = dataStack.pop();
        if (x == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

参考： https://zhuanlan.zhihu.com/p/57321004 http://www.codebaoku.com/it-java/it-java-230716.html 栈和队列的实现 https://www.jianshu.com/p/8855fbd9d570

results matching ""

    No results matching ""