锲而舍之,朽木不折;锲而不舍,金石可镂。---荀子《劝学》
队列,是一种先进先出的结构,类似于我们日常生活中的各种排队
先进先出-队列
栈,是先进后出的结构,就像弹匣一下
先进后出-栈
如上图,入栈过程 1 -> 3 -> 5,出栈顺序就是 5 -> 3 -> 1。
数据结构(一)| 链表 一节中,我们已经知道,双向链表由数据域和节点指针组成,有指向前一个节点的指针(last)和指向后一个节点的指针(next),头结点的last指向空,尾结点的next指向空。
双向链表
我们可以用双向链表来实现队列和栈。
队列-从尾部插入,从头部取出
先定义双向链表:
public class Node<T> {
public T value;
public Node last;
public Node next;
public Node(T value) {
this.value = value;
}
}
根据队列的特性,先进先出,入队时元素加入到队尾(tail),出队时从队列头部(head)出,因此,入队push和出队poll方法的实现需要定义两个辅助Node head和tail即可。
向对列插入元素
一开始head和tail都指向空,
插入第一个元素a
插入第二个元素b
插入第三个元素c
以此类推,通过上述演示,我们可以得出,每当插入一个元素时,tail向后移动,即需要移动tail指针。
从队列取出元素
再来分析一下弹出元素如何做。由于先进先出,所以从头部弹出元素。
从头部弹出元素并返回
继续从头部弹出元素
从上述分析可以看出,从队列中取元素时,需要移动的是head节点。
代码实现:
public class MyQueue {
//借助链表实现队列
private Node head;
private Node tail;
//入队操作
public void push(T value) {
//封装一个节点,保存其值,然后考虑将该节点挂在哪个位置
Node<T> cur = new Node<>(value);
if (head == null) {
//一开始队列为空的时候,插入一个元素后,让head和tail都移动到当前节点
head = cur;
tail = cur;
} else {
//头结点不是空的情况,插入后,尾指针移动
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
//出队-获取队列头部元素
public T poll() {
if (head == null) {
System.out.println("队列空了");
return null;
}
Node cur = head;
//让head的下一个节点成为新的头结点
if (head == tail) {
//只有一个元素了
head = null;
tail = null;
} else {
//移动head
head = head.next;
head.last = null;
cur.next = null;
}
return cur.value;
}
}
TIP:上述用双向链表实现的是从尾部插入元素,从头部取出元素。双向链表的节点有两个指针,可以灵活的控制从队列的哪个方向插入和取出数据:也就是说可以用双向链表实现双端队列。
实现双端队列
双端队列,既可以从尾部插入头部取出(前面已实现),也可以从头部插尾部取出。
用链表实现队列(还有后面要实现的栈结构),玩的就是head和tail指针,控制好这两个指针的指向就很容易写出来,建议用图画一下加深一下理解。
头部插入尾部取出(先插入的在尾部,所以从尾部取出,符合先进先出)的过程:
队列-从头部插入元素
一图胜千言,图上每一个插入动作都体现出了head、tail指针的变化,我们来根据这个图实现双端队列的另一半:
public class DoubleEndsQueue<T> {
//上来先定义head和tail
private Node<T> head;
private Node<T> tail;
//从尾部插入头部取出的实现见MyQueue的push和poll方法,此处略
//从头部插入
public void addFromHead(T value) {
//宗旨:移动head
Node<T> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
//从尾部取出
public T popFromBottom() {
if (head == null) {
system.out.println("队列为空");
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
}
栈的结构和队列在结构上是相似的,就是出入栈和队列的出入在方向上有差别。
我们可以基于上面实现的双端队列(内部是用双向链表实现)来实现栈:只要符合先进后出的规则就行:addFromHead和popFromHead、addFromBottom和popFromBottom。
public class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
}
队列的先进先出 和 栈的先进后出 结构,基于双向链表指针的灵活性,很容易实现。
实现的要诀就是控制头 head、尾 tail 指针的指向,建议画图加深印象。