文章摘要
队列是一种先进先出（FIFO）的线性数据结构，可通过链表或数组实现。链表实现使用双向链表的头尾节点模拟队列操作；数组实现循环队列，利用front和rear指针及取模运算管理元素，避免空间浪费。
>
2.0 使用链表实现队列说明 ------------------------------------------------------------------------------------------------------------------------------------------------------ **使用链表实现队列，无疑就是用链表的数据结构的方式来实现队列的操作（实现队列的接口）。跟栈不同的是：栈只能对一端进行操作，而队列是对头尾进行操作。一般对于单链表来说，头节点当作队列中的队头（front），尾节点当作队列中的队尾（rear）。而入队列相当于尾插，在链表尾部插入节点，出队列相当于头删，在链表头部删除头节点。对于双向链表来说，就比较自由了，头节点既可以作为队头，也可以作为队尾。尾节点既可以作为队头，也可以作为队尾。** ### 2.1 链表实现队列 **用双向链表来实现队列，既然头尾都可以作为队列，选其中一种即可，对于队尾来说也是如此。这里就用头节点作为队列中的队头，而尾节点作为队列中的队尾。** **简单分析：** **- 实现入栈操作：在链表尾部插入节点即可。** **- 实现出栈操作：在链表头部删除节点即可。** **- 实现获取队列头部元素：获取链表头部节点的元素即可。** **- 实现总计有效元素个数：需要定义一个成员变量 size ，入栈时进行 size++ ，出栈时 size--** **- 实现判空处理：当 size == 0 ，则为空队列。** **- 实现判断满队列：当 size \>= 创建队列时默认大小，则为满队列。** ### 2.2 链表实现队列 - 入栈操作 **实现入栈操作：在链表尾部插入节点即可。分为两种情况：当队列为空时，则入栈的节点即是队头也是队尾；当队列不为空时，则入栈的节点一般来说就是新的队尾。每一次入栈完成后，都需要进行 size++ 。** **代码如下：** > > ```java > //入列 > @Override > public boolean offer(int e) { > if (isEmpty()) { > front = rear = new Node(null,e,null); > size++; > return true; > } > Node node = new Node(rear,e,null); > rear.next = node; > rear = node; > size++; > return true; > } > ``` > >
> ### 2.3 链表实现队列 - 出栈操作 **实现出栈操作：在链表头部删除节点即可。出栈一般分为三种情况：** **第一种情况，当队列为空时，不应该出栈了，直接返回 -1 或者抛异常。** **第二种情况，当只有一个节点时，出栈之后，就不会再有元素了，所以 front 与 rear 需要置为空。返回出栈节点的值即可。** **第三种情况，除了第一、二种情况之后，第三种情况就可以正常的进行头删节点操作处理了。需要注意的是，出栈完成后，进行 size-- 。最后，返回出栈节点的数值即可。** **代码如下：** > > ```java > //出列 > @Override > public int poll() { > if (isEmpty()){ > return -1; > } > //注意特例:只有一个节点的情况 > if (front.next == null) { > int temp = front.val; > front = null; > rear = null; > return temp; > } > Node temp = front; > front = front.next; > front.prev = null; > size--; > return temp.val; > } > ``` > >
> ### 2.4 链表实现队列 - 获取队头元素操作(不删除) **获取链表头部节点的元素即可。一般分为两种情况：当队列为空时，可以返回 -1 或者抛异常处理；当队列不为空时，直接返回头部节点的值即可。** **代码如下：** > > ```java > @Override > public int peek() { > if (isEmpty()) { > return -1; > } > return front.val; > } > ``` > >
> ### 2.5 链表实现队列 - 获取队列有效元素个数操作 **直接返回 size 即可。** > > ```java > @Override > public int size() { > return size; > } > ``` > >
> ### 2.6 链表实现队列 - 判空处理操作 **当 size == 0 时，返回 true 。否则返回 false 。也可以用 front == null 来判断是否为空队列。** **代码如下：** > > ```java > @Override > public boolean isEmpty() { > return front == null; > } > ``` > >
> ### 2.7 用链表实现队列的完整代码 > ```java > public class MyLinkedQueue implements QueueInterface { > > static class Node { > public Node prev; > public int val; > public Node next; > > public Node(Node prev, int val, Node next) { > this.prev = prev; > this.val = val; > this.next = next; > } > } > > private Node front; > private Node rear; > private int size; > > //入列 > @Override > public boolean offer(int e) { > if (isEmpty()) { > front = rear = new Node(null,e,null); > size++; > return true; > } > Node node = new Node(rear,e,null); > node.prev = rear; > rear.next = node; > rear = node; > size++; > return true; > } > > //出列 > @Override > public int poll() { > if (isEmpty()){ > return -1; > } > //注意特例:只有一个节点的情况 > if (front.next == null) { > int temp = front.val; > front = null; > rear = null; > return temp; > } > Node temp = front; > front = front.next; > front.prev = null; > size--; > return temp.val; > } > > @Override > public int peek() { > if (isEmpty()) { > return -1; > } > return front.val; > } > > @Override > public int size() { > return size; > } > > @Override > public boolean isEmpty() { > return front == null; > } > > } > ``` > >
> 3.0 使用数组实现循环队列说明 -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- **用数组实现队列，一般来说是循环队列，循环队列可以解决普通队列在出队操作后产生的空间浪费问题，同时可以利用数组的固定大小来实现队列的循环利用。** **循环队列的接口代码如下：** > > ```java > public interface QueueInterface{ > /** > * 入列 > */ > boolean offer(int e); > > /** > * 出列 > */ > int poll(); > > /** > * 获取队列头元素，不删除 > */ > int peek(); > > /** > * 检验队列是否为空 > */ > boolean isEmpty(); > > /** > * 判断是否为满队列 > */ > boolean isFull(); > > /** > * 得到队尾元素，不删除 > */ > int Rear(); > } > ``` > >
> **使用数组实现队列，无疑就是用数组的数据结构的方式来实现队列的操作（实现队列的接口）。循环队列的关键是使用两个指针来标记队列的头部和尾部，分别称为 front 和 rear 。当入队时，rear 指针向后移动；当出队时，front 指针向后移动。当 rear 指针到达数组的末尾时，可以通过取模运算将 rear 指针置为 0 ，实现循环的效果。**
### 3.1 数组实现循环队列的操作 **- 入队操作：将元素添加到 rear 指针所指向的位置，并更新 rear 指针。** **- 出队操作：从 front 指针所指向的位置移除元素，并更新 front 指针。** **- 判空操作：当 front 指针等于 rear 指针时，队列为空。** **- 判满操作：当 (rear+1) % 数组长度等于 front 指针时，队列为满。** ### 3.2 数组实现循环队列 - 入队列操作 **将元素添加到 rear 指针所指向的位置，并更新 rear 指针。更新 rear 就是往后走一步，但是为了实现循环，可不能简单的进行 +1 处理，需要 rear = (rear + 1) % arr.length，这样就可以数组中循环走了。在入队前，需要先判断是否为满队列了。** **代码如下：** > > ```java > // 入队列 > @Override > public boolean offer(int e) { > if (isFull()) { > return false; > } > arr[rear] = e; > rear = (rear+1) % arr.length; > return true; > } > ``` > >
> ### 3.3 数组实现循环队列 - 出队列操作 **从 front 指针所指向的位置移除元素，并更新 front 指针。同样的，更新可不能简单的 +1 处理，需要将 front = (front + 1) % arr.length ，每次出栈前需要记录一下出栈的元素，接着才往后走，最后返回记录的元素即可。出栈前，需要判断是否为空队列，如果为空队列，就需要抛异常或者返回 -1 处理。** **代码如下：** > > ```java > //出队列 > @Override > public int poll() { > if (isEmpty()) { > return -1; > } > int temp = arr[front]; > front = (front + 1) % arr.length; > return temp; > } > ``` > >
> ### 3.4 数组实现队列 - 得到队头元素操作(不删除) **先判断是否为空队列，若不是，则返回队头元素即可。** **代码如下：** > > ```java > //得到队头元素，不删除 > @Override > public int peek() { > if (isEmpty()) { > return -1; > } > return arr[front]; > } > ``` > >
> ### 3.5 数组实现队列 - 得到队尾元素操作(不删除) **先判断队列是否为空，如果为空队列，则返回 -1 或者抛异常。如果不为空，则需要返回 arr\[rear - 1\]，但是需要注意的是：有一种情况需要额外考虑进去，当 rear == 0 时，那么 rear - 1 == -1 ，所以不合理，数组中的索引不存在 -1 。因此这个情况要分开讨论，当 rear == 0 时，那么需要返回的值为 arr\[arr.length - 1\]；当 rear != 0 时，那么返回的值为 arr\[rear - 1\] 。** **代码如下：** > > ```java > //得到队尾元素，不删除 > @Override > public int Rear() { > if (isEmpty()) { > return -1; > } > int temp = (rear == 0) ? arr.length - 1 : rear - 1; > return arr[temp]; > } > ``` > >
> ### 3.6 数组实现队列 - 判空队列操作 **当且仅当 rear == front 时，则队列为空。** **代码如下：** > > ```java > @Override > public boolean isEmpty() { > return front == rear; > } > ``` > >
> ### 3.7 数组实现队列 - 判满队列操作 **有很多种方式可以来判断队列是否满，比如，定义 size 变量来总计元素个数，然后跟 arr.lengrh 进行对比，相等即满队列了，不相等即为还没有满队列；使用标记也可以实现判断是否为满队列。** **这里介绍牺牲空间来判断满队列，即当且仅当 (rear + 1) % arr.lengrh == front 时，该队列满了。由于这里牺牲了一个空间，所以需要在自定义初始化数组大小的时候额外 +1 。** **代码如下：** > > ```java > // 自定义数组大小 > public ArrayQueue(int capacity) { > arr = new int[capacity + 1]; > } > > // 默认数组大小为: 10 > public ArrayQueue() { > arr = new int[10]; > } > ``` > > ```java > @Override > //判断是否为满队列（有很多种判断方法，这里使用牺牲空间方法来判断） > public boolean isFull() { > return (rear + 1) % arr.length == front; > } > ``` > >
>
### 3.8 用数组实现队列完整代码 > ```java > public class ArrayQueue implements QueueInterface{ > > private int front; > private int rear; > private int[] arr; > > // 自定义数组大小 > public ArrayQueue(int capacity) { > arr = new int[capacity + 1]; > } > > // 默认数组大小为: 10 > public ArrayQueue() { > arr = new int[10]; > } > > // 入队列 > @Override > public boolean offer(int e) { > if (isFull()) { > return false; > } > arr[rear] = e; > rear = (rear+1) % arr.length; > return true; > } > > //出队列 > @Override > public int poll() { > if (isEmpty()) { > return -1; > } > int temp = arr[front]; > front = (front + 1) % arr.length; > return temp; > } > > //得到队头元素，不删除 > @Override > public int peek() { > if (isEmpty()) { > return -1; > } > return arr[front]; > } > > //得到队尾元素，不删除 > @Override > public int Rear() { > if (isEmpty()) { > return -1; > } > int temp = (rear == 0) ? arr.length - 1 : rear - 1; > return arr[temp]; > } > > @Override > public boolean isEmpty() { > return front == rear; > } > > @Override > //判断是否为满队列（有很多种判断方法，这里使用牺牲空间方法来判断） > public boolean isFull() { > return (rear + 1) % arr.length == front; > } > > } > ``` > >
>
喜欢这篇文章的人也看了
暂无评论，快来抢沙发吧～
评论