6_队列.md

队列

1、用栈实现队列

用栈实现队列

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    private int front; //记录队首元素

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack1.isEmpty()){
            front = x;
        }
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(empty()){
            return -1;
        }
        if(stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            return front;
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return (stack1.isEmpty()) && (stack2.isEmpty());
    }
}

2、用队列实现栈

用队列实现栈

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

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue1.offer(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(empty()){
            return -1;
        }
        while (queue1.size()>1){
            queue2.offer(queue1.poll());
        }
        //交换着两个队列
        int num = queue1.poll();
        Queue<Integer> tmp = queue1;
        queue1 = queue2;
        queue2 = tmp;
        return num;
    }

    /** Get the top element. */
    public int top() {
        while (queue1.size()>1){
            queue2.offer(queue1.poll());
        }
        return queue1.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return (queue1.isEmpty()) && (queue2.isEmpty());
    }
}

3、字符流中第一个不重复的字符

字符流中第一个不重复的字符

//统计字符出现的次数
private int[] freq = new int[256];
//队列中只存储出现一次的字符，并且出队顺序就是入队顺序
private Queue<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch) {
    freq[ch]++;
    queue.offer(ch);

    //队列中只存储出现一次的字符
    while (!queue.isEmpty() && freq[queue.peek()]>1){
        queue.poll();
    }
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    return queue.isEmpty()? '#':queue.peek();
}