数据型网站 建设方案,建材类网站建设方案,腾讯云 配置wordpress,wordpress建站 评测#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 队列的说明 1.1 队列的几种常用操作 2.0 使用链表实现队列说明 2.1 链表实现队列 2.2 链表实现队列 - 入栈操作 2.3 链表实现队列 - 出栈操作 2.4 链表实现队列 … 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 队列的说明 1.1 队列的几种常用操作 2.0 使用链表实现队列说明 2.1 链表实现队列 2.2 链表实现队列 - 入栈操作 2.3 链表实现队列 - 出栈操作 2.4 链表实现队列 - 获取队头元素操作(不删除) 2.5 链表实现队列 - 获取队列有效元素个数操作 2.6 链表实现队列 - 判空处理操作 2.7 用链表实现队列的完整代码 3.0 使用数组实现循环队列说明 3.1 数组实现循环队列的操作 3.2 数组实现循环队列 - 入队列操作 3.3 数组实现循环队列 - 出队列操作 3.4 数组实现队列 - 得到队头元素操作(不删除) 3.5 数组实现队列 - 得到队尾元素操作(不删除) 3.6 数组实现队列 - 判空队列操作 3.7 数组实现队列 - 判满队列操作 3.8 用数组实现队列完整代码 1.0 队列的说明 队列是一种线性数据结构具有先进先出First In First OutFIFO的特性。它类似于排队的概念新元素被添加到队列的尾部而从队列中移除元素时则从队列的头部开始。队列通常用于需要按照特定顺序处理元素的场景比如任务调度、消息传递等。 1.1 队列的几种常用操作 - 队首元素front队列的头部元素。 - 队尾元素rear队列的尾部元素。 - 入队offer将新元素添加到队列的尾部。 - 出队poll从队列的头部移除元素。 - 获取队头元素peek从队列的头部获取元素不移除。 - 判空isEmpty判断队列是否为空。 - 判满isFull判断队列是否已满对于有限大小的队列。 - 元素个数size获取队列有效的元素个数。
接口代码如下 public interface QueueInterface{/*** 入列*/boolean offer(int e);/*** 出列*/int poll();/*** 获取队列头元素*/int peek();/*** 获取队列中有效元素个数*/int size();/*** 检验队列是否为空*/boolean isEmpty();
} 2.0 使用链表实现队列说明 使用链表实现队列无疑就是用链表的数据结构的方式来实现队列的操作实现队列的接口。跟栈不同的是栈只能对一端进行操作而队列是对头尾进行操作。一般对于单链表来说头节点当作队列中的队头front尾节点当作队列中的队尾rear。而入队列相当于尾插在链表尾部插入节点出队列相当于头删在链表头部删除头节点。对于双向链表来说就比较自由了头节点既可以作为队头也可以作为队尾。尾节点既可以作为队头也可以作为队尾。 2.1 链表实现队列 用双向链表来实现队列既然头尾都可以作为队列选其中一种即可对于队尾来说也是如此。这里就用头节点作为队列中的队头而尾节点作为队列中的队尾。
简单分析 - 实现入栈操作在链表尾部插入节点即可。 - 实现出栈操作在链表头部删除节点即可。 - 实现获取队列头部元素获取链表头部节点的元素即可。 - 实现总计有效元素个数需要定义一个成员变量 size 入栈时进行 size 出栈时 size-- - 实现判空处理当 size 0 则为空队列。 - 实现判断满队列当 size 创建队列时默认大小则为满队列。 2.2 链表实现队列 - 入栈操作 实现入栈操作在链表尾部插入节点即可。分为两种情况当队列为空时则入栈的节点即是队头也是队尾当队列不为空时则入栈的节点一般来说就是新的队尾。每一次入栈完成后都需要进行 size 。
代码如下 //入列Overridepublic 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-- 。最后返回出栈节点的数值即可。
代码如下 //出列Overridepublic 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 或者抛异常处理当队列不为空时直接返回头部节点的值即可。
代码如下 Overridepublic int peek() {if (isEmpty()) {return -1;}return front.val;} 2.5 链表实现队列 - 获取队列有效元素个数操作 直接返回 size 即可。 Overridepublic int size() {return size;} 2.6 链表实现队列 - 判空处理操作 当 size 0 时返回 true 。否则返回 false 。也可以用 front null 来判断是否为空队列。
代码如下 Overridepublic boolean isEmpty() {return front null;} 2.7 用链表实现队列的完整代码 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;//入列Overridepublic 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;}//出列Overridepublic 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;}Overridepublic int peek() {if (isEmpty()) {return -1;}return front.val;}Overridepublic int size() {return size;}Overridepublic boolean isEmpty() {return front null;}} 3.0 使用数组实现循环队列说明 用数组实现队列一般来说是循环队列循环队列可以解决普通队列在出队操作后产生的空间浪费问题同时可以利用数组的固定大小来实现队列的循环利用。
循环队列的接口代码如下 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 指针时队列为空。 - 判满操作当 (rear1) % 数组长度等于 front 指针时队列为满。 3.2 数组实现循环队列 - 入队列操作 将元素添加到 rear 指针所指向的位置并更新 rear 指针。更新 rear 就是往后走一步但是为了实现循环可不能简单的进行 1 处理需要 rear (rear 1) % arr.length这样就可以数组中循环走了。在入队前需要先判断是否为满队列了。
代码如下 // 入队列Overridepublic boolean offer(int e) {if (isFull()) {return false;}arr[rear] e;rear (rear1) % arr.length;return true;} 3.3 数组实现循环队列 - 出队列操作 从 front 指针所指向的位置移除元素并更新 front 指针。同样的更新可不能简单的 1 处理需要将 front (front 1) % arr.length 每次出栈前需要记录一下出栈的元素接着才往后走最后返回记录的元素即可。出栈前需要判断是否为空队列如果为空队列就需要抛异常或者返回 -1 处理。
代码如下 //出队列Overridepublic int poll() {if (isEmpty()) {return -1;}int temp arr[front];front (front 1) % arr.length;return temp;} 3.4 数组实现队列 - 得到队头元素操作(不删除) 先判断是否为空队列若不是则返回队头元素即可。
代码如下 //得到队头元素不删除Overridepublic 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] 。
代码如下 //得到队尾元素不删除Overridepublic int Rear() {if (isEmpty()) {return -1;}int temp (rear 0) ? arr.length - 1 : rear - 1;return arr[temp];} 3.6 数组实现队列 - 判空队列操作 当且仅当 rear front 时则队列为空。
代码如下 Overridepublic boolean isEmpty() {return front rear;} 3.7 数组实现队列 - 判满队列操作 有很多种方式可以来判断队列是否满比如定义 size 变量来总计元素个数然后跟 arr.lengrh 进行对比相等即满队列了不相等即为还没有满队列使用标记也可以实现判断是否为满队列。 这里介绍牺牲空间来判断满队列即当且仅当 (rear 1) % arr.lengrh front 时该队列满了。由于这里牺牲了一个空间所以需要在自定义初始化数组大小的时候额外 1 。
代码如下 // 自定义数组大小public ArrayQueue(int capacity) {arr new int[capacity 1];}// 默认数组大小为: 10public ArrayQueue() {arr new int[10];} Override//判断是否为满队列有很多种判断方法这里使用牺牲空间方法来判断public boolean isFull() {return (rear 1) % arr.length front;} 3.8 用数组实现队列完整代码 public class ArrayQueue implements QueueInterface{private int front;private int rear;private int[] arr;// 自定义数组大小public ArrayQueue(int capacity) {arr new int[capacity 1];}// 默认数组大小为: 10public ArrayQueue() {arr new int[10];}// 入队列Overridepublic boolean offer(int e) {if (isFull()) {return false;}arr[rear] e;rear (rear1) % arr.length;return true;}//出队列Overridepublic int poll() {if (isEmpty()) {return -1;}int temp arr[front];front (front 1) % arr.length;return temp;}//得到队头元素不删除Overridepublic int peek() {if (isEmpty()) {return -1;}return arr[front];}//得到队尾元素不删除Overridepublic int Rear() {if (isEmpty()) {return -1;}int temp (rear 0) ? arr.length - 1 : rear - 1;return arr[temp];}Overridepublic boolean isEmpty() {return front rear;}Override//判断是否为满队列有很多种判断方法这里使用牺牲空间方法来判断public boolean isFull() {return (rear 1) % arr.length front;}}
