线性表之队列

1、简介

队列是一种线性表，只能在头尾两端进行操作。

• 队尾：只能从尾部添加元素，叫做入队。
• 队首：只能头部删除元素，叫做出队。

• 先进先出的原则，FIFO。

  
  image.png

2、队列的接口设计

//元素的数量
public int size() {}

//是否为空
public boolean isEmpty() {}

//清空
public void clear() {}

//队尾入队
public void enQueue(E element) {}

//队头出队
public E deQueue() {}

//获取队首元素
public E front() {}

由于队列是操作头尾的元素，所以我们可以使用双向链表来实现队列。

public class Queue<E> {
    private LinkedList<E> list = new LinkedList<>();

    // 元素的数量
    public int size() {
        return list.size();
    }

    // 是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 清空
    public void clear() {
        list.clear();
    }

    // 队尾入队
    public void enQueue(E element) {
        list.add(element);
    }

    // 队头出队
    public E deQueue() {
        return list.remove(0);
    }

    // 获取队首元素
    public E front() {
        return list.get(0);
    }
    
    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        while (!isEmpty()) {
            sb.append(deQueue()).append(",");
        }
        return sb.toString();
    }
}

3、练习：用栈来实现队列

准备两个栈：inStack和outStack

• 入队时，push到inStack中
• 出队时，
  • 判断outStack是否为空，不为空则直接出栈
  • 如果outStack为空，则将inStack所有元素逐一弹出，push到outStack中，outStack弹出栈顶元素
    具体实现如下：

public class _232_用栈实现队列 {
    private Stack<Integer> inStack = new Stack<Integer>();
    private Stack<Integer> outStack = new Stack<Integer>();

    /** Initialize your data structure here. */
    public _232_用栈实现队列() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        inStack.push(x);
    }

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

    /** Get the front element. */
    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

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

4、双端队列

双端队列能在头尾两端进行添加、删除的队列。

4.1、接口设计

//元素的数量
public int size() {}

//是否为空
public boolean isEmpty() {}

//清空
public void clear() {}

//从队尾入队
public void enQueueRear(E element) {}

//从队头出队
public E deQueueFront() {}

//从队头入队
public void enQueueFront(E element) {}

//从队尾出队
public E deQueueRear() {}

//获取队头元素
public E front() {}

//获取队尾元素
public E rear() {}

双端队列需要进行队头、队尾元素的添加和删除，所以内部使用双向链表来实现。
代码如下：

public class DeQueue<E> {
    private LinkedList<E> list = new LinkedList<>();

    // 元素的数量
    public int size() {
        return list.size();
    }

    // 是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 清空
    public void clear() {
        list.clear();
    }

    // 从队尾入队
    public void enQueueRear(E element) {
        list.add(element);
    }

    // 从队头出队
    public E deQueueFront() {
        return list.remove(0);
    }

    // 从队头入队
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    // 从队尾出队
    public E deQueueRear() {
        return list.remove(list.size()-1);
    }

    // 获取队头元素
    public E front() {
        return list.get(0);
    }

    // 获取队尾元素
    public E rear() {
        return list.get(list.size()-1);
    }
    
    @Override
    public String toString() {
        return list.toString();
    }
}

5、循环队列

我们在实现队列时，底层使用的是双向链表来实现的，其实也可以使用动态数组来实现，并且各项接口也可以优化到O(1)级别，使用动态数组实现，并且优化之后的队列，就叫循环队列。，我们知道队列使用动态数组实现时，在出队时会删除数组的头部元素，那么后面所有的元素都会向前移动，其复杂度为O(n)，这里可以使用front来记录数组的头元素的index，来进行优化到O(1)级别。前面一篇文章中我们讲到了动态数组的优化ArrayList的优化。

@SuppressWarnings("unchecked")
public class CircleQueue<E> {
    private int size;
    private E[] elements = (E[]) new Object[5];
    private int front;

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空
    public void clear() {
        for (E element : elements)
            element = null;
        size = 0;
        front = 0;
    }

    // 队尾入队
    public void enQueue(E element) {
        ensureCapacity(size + 1);
        elements[index(size)] = element;
        size++;
    }

    // 队头出队
    public E deQueue() {
        E oldElement = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return oldElement;
    }

    // 获取队首元素
    public E front() {
        return elements[front];
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity >= oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            System.out.println("oldCapacity = " + oldCapacity + "  扩容为：" + newCapacity);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < oldCapacity; i++) {
                newElements[i] = elements[index(i)];
            }
            elements = newElements;
            front = 0;
        }

    }

    private int index(int index) {
        return (index + front) % elements.length;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size + " front= " + front).append(" [");
        for (E e : elements) {
            sb.append(" " + e).append(",");
        }
        sb.append("]");
        return sb.toString();
    }
}

6、循环双端队列

内部使用动态数组实现的，可对头部、尾部进行删除、添加操作的队列称为循环双端队列。
这里依然增加一个front来记录数组中的头元素的index来进行优化，代码如下：

public class CircleDeque<E> {
    private int size;
    private E[] elements = (E[]) new Object[10];
    private int front;

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空
    public void clear() {
        for (E e : elements) {
            e = null;
        }
        size = 0;
        front = 0;
    }

    // 从队尾入队
    public void enQueueRear(E element) {
        ensureCapacity(size + 1);
        elements[index(size)] = element;
        size++;
    }

    // 从队头出队
    public E deQueueFront() {
        E oldElement = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return oldElement;
    }

    // 从队头入队
    public void enQueueFront(E element) {
        ensureCapacity(size + 1);
        front = index(-1);
        elements[front] = element;
        size++;
    }

    // 从队尾出队
    public E deQueueRear() {
        E oldElement = elements[index(size - 1)];
        elements[index(size - 1)] = null;
        size--;
        return oldElement;
    }

    // 获取队头元素
    public E front() {
        return elements[front];
    }

    // 获取队尾元素
    public E rear() {
        return elements[index(size - 1)];
    }

    private int index(int index) {
    index += front;
        if (index < 0) 
        return index + elements.length;
        return index % elements.length;
}

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity >= oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < oldCapacity; i++) {
                newElements[i] = elements[index(i)];
            }
            elements = newElements;
            front = 0;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size + " front= " + front).append(" [");
        for (E e : elements) {
            sb.append(" " + e).append(",");
        }
        sb.append("]");
        return sb.toString();
    }
}

上线我们多次调用了方法index(int index)对index进行转换，方法内部使用了取模的运算：

private int index(int index) {
    index += front;
        if (index < 0) 
        return index + elements.length;
        return index % elements.length;
}

而经分析可知index + front不可能大于elements.length的2倍，所以可以对(index + front) % elements.length进行转换：

private int index(int index) {
    index += front;
    if (index < 0) {
        return index + elements.length;
    }
    return index - (index >= elements.length ? elements.length : 0);
}

7、使用队列实现栈

栈是栈尾入栈，栈顶出栈，所以栈是后进先出的，
队列是队尾入队，队首出队，所以队列是先进先出的，
要想使用队列来实现栈，就需要在队列入栈时首先获取入栈前的元素个数n，然后将元素入队到队列，然后将前n个元素依次出队并将出队的元素入队到队列中，此时队列的前端元素即为新入栈的元素，而且队列的前端和后端分别对应栈的栈顶和栈底。
代码如下：

public class _225_用队列实现栈 {
    private Queue<Integer> queue;

    /** Initialize your data structure here. */
    public _225_用队列实现栈() {
        queue = new LinkedList<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        int oldSize = queue.size();
        queue.offer(x);
        for (int i = 0; i < oldSize; i++)
            queue.offer(queue.poll());
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }

    /** Get the top element. */
    public int top() {
        return queue.peek();
    }

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

由于每次入栈的元素都确保为队列的前端元素，所以在出栈操作和获取栈顶元素的操作就可以直接调用队列的出队和获取对头操作即可。