基础4 | 队列

栈:先进后出 想想青岛的栈桥

队列:先进先出 类似拉屎

如何理解“队列”?

队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。

先进者先出,这就是典型的“队列”。我们知道,栈只支持两个基本操作:入栈 push()和出栈 pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素

跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

// 用数组实现的队列
public class ArrayQueue {
// 数组:items,数组大小:n
private String[] items;
private int n = 0;
// head表示队头下标,tail表示队尾下标
private int head = 0;
private int tail = 0;

// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}

// 入队
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}

// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确,把–操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}

栈只需要一个栈顶指针就好 而队列需要两个指针 分别是head指针和tail指针 分别指向队首和队尾

你可以结合下面这幅图来理解。当 a、b、c、d 依次入队之后,队列中的 head 指针指向下标为 0 的位置,tail 指针指向下标为 4 的位置。

当我们调用两次出队操作之后,队列中 head 指针指向下标为 2 的位置,tail 指针仍然指向下标为 4 的位置。

// 入队操作,将item放入队尾
public boolean enqueue(String item) {
// tail == n表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0,表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}

items[tail] = item;
++tail;
return true;
}

发布者

王药酒

本站采用 知识共享署名4.0 国际许可协议进行许可 本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名