Stack & Queue

什么是栈(Stack)、队列(Queue)？

在很多的应用中，我们需要维护多个对象的集合。这种操作一般来说都比较简单，例如向集合中添加、删除、更新某个元素，检查是否为空以及遍历整个集合。
栈（Stack），或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表，按照通常的规则，每次新来一封邮件，往往都将其放至于最上方；同理，每次处理（查看）一封邮件，都是查看最新的邮件。
队列（Queue），遵守公平原则，你可以将队列想象成为现实中买票排队，永远保证等待时间最长的人最先出队。

栈(Stack)

栈（Stack），或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表，按照通常的规则，每次新来一封邮件，往往都将其放至于最上方；同理，每次处理（查看）一封邮件，都是查看最新的邮件。

栈遵守后进先出（LIFO; Last In, First Out）原则。无论是从栈中添加亦或是删除操作，都只允许从栈顶进行操作。

如上图，栈内元素的顺序是：0->1->2->3->4。
一般我们对于栈的基本操作无非以下几种：

• 入栈（push）
• 出栈（pop）
• 获取栈大小（size）
• 是否为空（isEmpty）

我们上面说过，无论是从栈中添加亦或是删除操作，都只允许在栈顶操作。
我们分别来看下分步图解入栈（添加）和出栈（删除）操作。

入栈(Push)

1. 目前栈内元素的顺序是0->1->2->3
2. 入栈元素4，位置为栈顶
3. 入栈后栈内元素为0->1->2->3->4

出栈(Pop)

1. 目前栈内元素的顺序是0->1->2->3->4
2. 出栈栈顶元素，出栈的元素为4
3. 出栈后栈内元素为0->1->2->3

接下来我们看下代码层面的数组实现，你可以在我的Github找到此代码。

package net.sunzhenyu.miscellaneous.dsa.stack;

import java.util.Iterator;

public class Stack<T> implements IStack<T> {

  private static int      DEFAULT_INITIAL_CAPACITY = 10;
  private        Object[] elements;
  private        int      size;

  public Stack() {
    this.elements = new Object[DEFAULT_INITIAL_CAPACITY];
  }

  public Stack(int initialCapacity) {
    if (initialCapacity > 0) {
      this.elements = new Object[initialCapacity];
    } else {
      this.elements = new Object[DEFAULT_INITIAL_CAPACITY];
    }
  }

  private void ensureCapacity() {
    if (this.elements.length >= size) {
      expand(this.elements.length << 1);
    }
  }

  @SuppressWarnings("all")
  private void expand(int newSize) {
    Object[] newArr = new Object[newSize];
    for (int i = 0; i < size; i++) {
      newArr[i] = this.elements[i];
    }
    this.elements = newArr;
  }

  @Override
  public void push(T element) {
    ensureCapacity();
    this.elements[size++] = element;
  }

  @Override
  @SuppressWarnings("unchecked")
  public T pop() {
    Object oldElement = this.elements[--size];
    elements[size] = null;
    if (size > 0 && size == this.elements.length >> 4) {
      expand(this.elements.length >> 1);
    }
    return (T) oldElement;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public Iterator<T> iterator() {
    return new It();
  }

  class It implements Iterator<T> {

    private int key = size;

    @Override
    public boolean hasNext() {
      return key > 0;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T next() {
      return (T) elements[--key];
    }
  }
}

PS:还有一种是使用Node来实现栈，代码在这里

队列(Queue)

队列（Queue），遵守公平原则，你可以将队列想象成为现实中买票排队，永远保证等待时间最长的人最先出队。

队列是一种线性的数据结构，遵守先进先出（FIFI; First In First Out）原则；队列只允许在队首 进行出队操作，且只允许在队尾进行入队操作。

一般来说，队列的操作只有如下几种：

• 入队（enqueue）
• 出队（dequeue）
• 获取队列大小（size）
• 队列是否为空（isEmpty）

我们接下来来看下入队和出队操作的分步图解：

入队(EnQueue)

1. 目前队列内元素为0->1->2->3
2. 入队元素4到队尾
3. 入队后的队列内元素为0->1->2->3->4

出队(DeQueue)

1. 目前队列内元素为0->1->2->3->4
2. 从队首出队一个元素，元素为0
3. 出队后的队列内元素为1->2->3->4

接下来我们来看下代码层面的数组实现，你也可以在我的Github找到此代码。

package net.sunzhenyu.miscellaneous.dsa.queue;

import java.util.Iterator;

public class ArrayQueue<T> implements IQueue<T> {

  private       Object[] elements;
  private       int      size;
  private       int      head;
  private final Integer  DEFAULT_CAPACITY = 10;

  public ArrayQueue(int initialCapacity) {
    if (initialCapacity <= 0) {
      elements = new Object[DEFAULT_CAPACITY];
    } else {
      elements = new Object[initialCapacity];
    }
  }

  @Override
  public void enqueue(T element) {
    ensureCapacity(this.elements.length << 1);
    elements[size++] = element;
  }

  @Override
  @SuppressWarnings("unchecked")
  public T dequeue() {
    if (size == (elements.length >> 4)) {
      expandAndShrink(this.elements.length >> 1);
    }
    T result = (T) elements[head];
    elements[head] = null;
    if (++head == elements.length) {
      head = 0;
    }
    return result;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  private void ensureCapacity(int newCapacity) {
    if (newCapacity <= 0) {
      throw new IllegalArgumentException("The new capacity cannot smaller and equal than zero");
    }
    if (size >= elements.length) {
      expandAndShrink(newCapacity);
    }
  }

  @SuppressWarnings("all")
  private void expandAndShrink(int newCapacity) {
    Object[] newCapacityArray = new Object[newCapacity];
    for (int i = 0; i < size; i++) {
      newCapacityArray[i] = elements[i];
    }
    this.elements = newCapacityArray;
  }

  @Override
  public Iterator<T> iterator() {
    return new ArrayQueueIterator<>();
  }

  class ArrayQueueIterator<E> implements Iterator<E> {

    private int index = head;

    @Override
    public boolean hasNext() {
      return index < size;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E next() {
      return (E) elements[index++];
    }
  }
}