7.队列(Queue)与栈(Stack)

概念

Queue:队列是一种先进先出的数据结构，类似排队。
Stack: 栈是一种先进后出或者说后进先出的数据结构，类似垃圾桶。

        Deque<Integer> stack = new LinkedList<>();
        //主要函数
        stack.size();
        stack.isEmpty();
        stack.push(6);//入栈
        stack.peek();//查看首元素，元素不出队列
        stack.pop();//出栈

        Queue<Integer> queue = new LinkedList<>();
        //主要函数
        queue.size();
        queue.isEmpty();
        queue.offer(6);//入队列
        queue.peek();//查看首元素，元素不出队列
        queue.poll();//出队列

题目1

使用两个Stack实现一个Queue数据结构。

/**
 * 使用两个stack 实现一个queue
 * Created by tomcat on 2017/12/2.
 */
public class QueueByTwoStacks {

    private Deque<Integer> in = new LinkedList<>();
    private Deque<Integer> out = new LinkedList<>();

    public Integer poll() {
        shuffle();
        return out.isEmpty() ? null : out.pop();
    }

    public Integer peek() {
        shuffle();
        return out.isEmpty() ? null : out.peek();
    }

    public void offer(int element) {
        in.push(element);
    }

    public int size() {
        return in.size() + out.size();
    }

    public boolean isEmpty() {
        return in.isEmpty() && out.isEmpty();
    }

    private void shuffle() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                Integer pop = in.pop();
                out.push(pop);
            }
        }
    }
}

题目2

实现一个Stack数据结构，并实现一个min()函数可以获取Stack中最小的元素，要求时间复杂度是O(1).

/**
 * 实现一个Stack数据结构，并实现一个min()函数可以获取Stack中最小的元素，要求时间复杂度是O(1).
 * Created by tomcat on 2017/12/2.
 */
public class StackWithMin {

    @Test
    public void test() throws Exception {
        StackWithMin stack = new StackWithMin();
        stack.push(5);
        stack.top();
        stack.min();
        stack.pop();
        stack.min();
        stack.top();
    }

    private Deque<Integer> in = new LinkedList<>();
    private Deque<Integer> min = new LinkedList<>();

    public int pop() {
        if(in.isEmpty()){
            return -1;
        }
        Integer pop = in.pop();
        if(pop == min.peek()){
            min.pop();
        }
        return pop;
    }

    public int top() {
        return in.isEmpty() ? -1 : in.peek();
    }

    public void push(int element) {
        in.push(element);
        if(min.isEmpty()){
            min.push(element);
        }else if(element <= min.peek()){
            min.push(element);
        }
    }

    public int min(){
        if(min.isEmpty())return -1;
        return min.peek();
    }

    public int size() {
        return in.size();
    }

    public boolean isEmpty() {
        return in.isEmpty();
    }

}