04栈和队列

1、栈

1.1、概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈数据结构遵循的是先进后出原则。只有栈顶部的元素对外可见。

1.2、怎样实现栈数据结构

在Java中的栈是继承Vector来实现的，Vector与ArrayList类似，不过是线程安全的。

可以继承ArrayList或者LinkedList来实现栈，但是这样会多出很多不必要的方法，栈数据结构只对外提高如下接口

push：往栈顶部添加元素pop：弹出栈顶部的元素peep：查看栈顶部的元素size：查看栈中元素的数量isEmpty：查看栈是否为空clear：清空栈

可以让栈has a ArrayList来实现栈数据结构。

public class Stack<E> { private ArrayList<E> list = new ArrayList<>(); /** * 往栈里存放元素,也就是往数组的最后一个位置添加元素 * @param element */ public void push(E element){ list.add(element); } /** * 弹出栈顶的元素，也就是删除数组末尾的元素 * @return */ public E pop(){ return list.remove(list.size() - 1); } public int size(){ return list.size(); } public E peep(){ return list.get(list.size() - 1); } public boolean isEmpty(){ return list.isEmpty(); } public void clear(){ list.clear(); } }

3、队列

3.1、概念

队列是一种特殊的线性表。特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列遵循先进先出原则

3.2、对外方法

enQueue：入队deQueue：出队front：查看队列头部的size：查看队列中元素的数量isEmpty：查看队列是否为空clear：清空队列

3.3、用栈实现队列

思路：

需要准备两个栈，一个用于入队，一个用于出队。这里成为入队栈和出队栈。

不管任何元素入队时加入入队栈。

当出队时，将入队栈中的所有元素全部弹出，依次放入出队栈。然后弹出出队栈栈顶的元素，也就是入队栈栈底部的元素，也就是第一个入队的元素。

因为队列遵循的是先进先出原则，栈遵循的是先进后出原则，只需要将入队栈中的元素弹出到出队栈中，这个顺序就刚好与队列一样了。

这里要注意：当出队栈为空时才能让入队栈中的元素进入出队栈。

public class _232_用栈实现队列 { /** * 用于入队的栈 */ private Stack<Integer> inStack; /** * 用于出队的栈 */ private Stack<Integer> outStack; /** Initialize your data structure here. */ public _232_用栈实现队列() { inStack = new Stack<>(); outStack = new Stack<>(); } /** 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() { checkOutStack(); return outStack.pop(); } /** Get the front element. */ public int peek() { checkOutStack(); return outStack.peek(); } /** * 当pop或者peek时，需要判断出队的栈是否为空，如果为空，则需要将入队栈中的所有元素放入出队栈 */ private void checkOutStack(){ if (outStack.isEmpty()){ while(!inStack.isEmpty()){ outStack.push(inStack.pop()); } } } /** Returns whether the queue is empty. */ public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } }

4、双端队列

4.1、概念：

是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

4.2、对外方法

enQueueRear：从队尾入队enQueueFront：从队头入队deQueueRear：从队尾出队deQueueFront：从队头出队front：查看队列头部的size：查看队列中元素的数量isEmpty：查看队列是否为空clear：清空队列

4.3、用LinkedList实现双端队列

import java.util.LinkedList; /** * 双端队列 * @param <E> */ public class DeQueue<E> { LinkedList<E> list = new LinkedList<>(); public DeQueue() { } /** * 从队列的左边入队，也就是头部 */ public void enQueueFront(E element){ list.add(0,element); } /** * 从队列的右边入队，也就是尾部 */ public void enQueueRear(E element){ list.add(element); } /** * 从队头出队 * @return */ public E deQueueFront(){ return list.remove(0); } /** * 从队尾出队 * @return */ public E deQueueRear(){ return list.remove(list.size() - 1); } public int size(){ return list.size(); } public boolean empty(){ return list.isEmpty(); } public E left(){ return list.get(0); } public E right(){ return list.get(list.size() - 1); } public void clear(){ list.clear(); } }

5、循环队列

5.1、概念

循环队列是用数组实现，并且经过了一定优化之后的队列

优化了哪些：

在数组中，如果向首位置添加或删除元素，会让所有的元素都向后或者向前移动一位，效率低。为了解决这个问题，可以添加一个指针front指向数组的头元素，front永远指向数组第一个元素，当头元素被删除后，只需要让指针指向第二个元素即可。当数组容量不足时，如果front指针的前面位置还有元素，就将即将添加的元素添加到前面空余的位置即可，这样可以很好地利用内存空间，并且提高删除添加的效率。

如图所示：

​ 当删除a之后，让front指向b

​ 添加元素

​ 当后面没有容量时，下一个数据将添加到第一个位置。

5.2、对外方法

方法与队列一样，不过这里获取队头元素时是获取front指向的元素。

5.3、用动态数组实现循环队列

/** * 循环队列 */ public class CircleQueue<E> { private int size; private E[] elements; private int front; private static final int DEFAULT_CAPACITY = 10; public CircleQueue(){ this(DEFAULT_CAPACITY); } public CircleQueue(int initCapacity){ initCapacity = initCapacity <= 1 ? DEFAULT_CAPACITY : initCapacity; elements = (E[]) new Object[initCapacity]; } public void enQueue(E element){ ensureCapacity(size + 1); elements[index(size)] = element; size++; } private void ensureCapacity(int oldCapacity) { if (oldCapacity < elements.length) return; //当size = 数组的长度时，表示应该进行扩容,这里使用位运算符，扩容之后的容量为之前的1.5倍 int newCapacity = elements.length + (elements.length >> 1); E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++){ newElements[i] = elements[index(i)]; } elements = newElements; front = 0; } public E deQueue(){ E element = elements[front]; elements[front] = null; front = index(1); size--; return element; } public E front(){ return elements[front]; } public int size(){ return size; } public boolean empty(){ return size == 0; } /** * 通过传入的索引返回数组中的真实索引 * @param index * @return */ private int index(int index){ index += front; return index >= elements.length ? index-elements.length : index; } public void clear(){ for (int i = 0; i < size; i++){ elements[index(i)] = null; } front = 0; size = 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("size=").append(size).append(",front=").append(front).append(", ["); for (int i = 0; i < elements.length; i ++){ if (i != 0){ sb.append(", "); } sb.append(elements[i]); } sb.append("]"); return sb.toString(); } }

最核心的问题是索引问题：

入队时，往队尾添加元素，如果数组后面已经没有位置了，此时如果front前面有位置，则应该加入到front前面空缺的位置

如何得出该位置的索引呢？

这里就要通过式子来计算出该往什么位置添加索引。

private int index(int index){ index += front; return index >= elements.length ? index-elements.length : index; } 给该方法传入一个索引，比如传入size，就是往数组的末尾添加元素，该队列中有四个元素，size为4。实际上数组的长度为6，front为2。此时如果往队列尾部添加元素，应该用front + size对length取模，这样可以得出真实添加元素的位置。在这里对取模进行了优化（取模效率较低）。不过前提条件是取模的数不能大与被取模数的2倍。这是因为当小于2倍时，取模实际上就是减去这个数。