队列

Queue 的数组与 LinkedList 实现

作者 QIFAN 日期 2017-01-20
队列

基本概念

Queue 是一种遵循 FIFO (先入先出)规则的一种数据结构。于 Stack 对应。

Queue API

public interface QueueInterface<T> {
public boolean isEmpty();
public boolean isFull();
public void push(T item);
public T pop();
public T peek();
}

Array Implementation

使用一个数组作为容器。

使用三个指针 front , end ,size ,分别代表队伍头,队伍尾,当前队伍人数。

public class ArrayQueue<T> {
private T[] queue;
private int front;
private int end;
private int size;
...
}

Constructor:

public ArrayQueue(int capacity) {
queue = (T[]) new Object[capacity];
front = 0;
end = 0;
size = 0;
}

记住不能 queue = new T[capacity] ! Java 中没有 generic type 的数组。

boolean isEmpty()

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

boolean isFull()

public boolean isFull() {
return size == queue.length;
}

void push(T item)

public void push(T item) {
if (!isFull()) {
queue[end] = item;
end = (end + 1) % queue.length;
size++;
}
}

T pop()

public T pop() {
if (!isEmpty()) {
T res = queue[front];
queue[front] = null;
front = (front + 1) % queue.length;
size--;
return res;
}
return null;
}

T peek()

public T peek() {
if (!isEmpty()) {
return queue[front];
}
return null;
}

LinkedList Implementation

这个很简单。有两个指针 front , end ,分别指向链表的头和尾。

public class LinkedListQueue<T> {
Node<T> front;
Node<T> end;
public LinkedListQueue() {
front = null;
end = front;
}
public boolean isEmpty() {
return front == null;
}
public void push(T item) {
if (isEmpty()) {
front = new Node(item, null);
end = front;
} else {
end.next = new Node(item, null);
}
}
public T pop() {
if (isEmpty()) {
return null;
}
T res = front.data;
if (front.next == null) {
front = null;
end == null;
} else {
front = front.next;
}
return res;
}
public T peek() {
if (isEmpty()) {
return null;
}
return front.data;
}
static class Node<T> {
private T data;
private Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}

完整代码

ArrayQueue.java
LinkedListQueue.java

相关文章

算法总结 |

更新历史

  • 2017.01.20 第一版