滨州网站定制,旧版优化大师,表情制作小程序,文具电子商务网站开发内容目录
一、队列基础知识
1.队列的概念
2.队列的实现
二、代码实现
1.链队列创建
2.链队列遍历
3.入队
4.出队
5.数据测试
6.完整的程序代码
总结 一、队列基础知识
1.队列的概念
今天我们继续学习另一个常见的数据结构——队列。和栈一样#xff0c;队列也是一种操…目录
一、队列基础知识
1.队列的概念
2.队列的实现
二、代码实现
1.链队列创建
2.链队列遍历
3.入队
4.出队
5.数据测试
6.完整的程序代码
总结 一、队列基础知识
1.队列的概念
今天我们继续学习另一个常见的数据结构——队列。和栈一样队列也是一种操作受限制的线性表其限定在表的前端进行删除操作在表的后端进行插入操作删除这一端叫做队头插入这一端叫做队尾。由于队列属于线性表的范畴所以队列当然拥有线性表存储数据的特性其中队列存储的数据元素称为队列元素。注意当队列中没有数据元素时为空队列。
在之前我们说过栈是一种先进后出后进先出的线性表而队列却完全不一样。因为队列只能在队头删除在队尾插入所以最先进入的元素会最早到达队头然后被删除因此队列是一种先进先出后进后出的线性表。这其实有点像我们平时在电影院排队买票第一个排队的人就最先到达队头买票最后一个排队的人只能最晚到达队头买票。
和顺序表、链表、栈这些线性表一样队列也有一些基本操作实现这里我们主要介绍的是入队和出队。
入队在队列中插入一个队列元素就叫做入队出队在队列中删除一个队列元素就叫做出队 2.队列的实现
在java中队列的实现可以通过以下两种方式完成。
顺序队列以数组为底层通过顺序存储结构实现队列。分配一段连续的存储空间用两个整型下标front和rear分别代表队头和队尾。 链队列以链表为底层通过链表存储结构来实现队列。链队列类似于一个单链表用头指针header和尾指针tail分别指向队头和队尾。 二、代码实现
这里我们采用链队列进行模拟。
1.链队列创建
由于链队列基于链表结构所以它的创建大体上和链表差不多结合之前学过的链表知识可以很容易得到如下代码
第一步我们同样创建一个内部类Node作为结点类并在其中定义成员变量data域和next域以及一个基本成员方法。
public class LinkedQueue {/*** An inner class.*/class Node {/*** The data.*/int data;/*** The reference to the next node.*/Node next;/********************* * The constructor.* * param paraValue The data.******************* */public Node(int paraValue) {data paraValue;next null;}// Of the constructor}// Of class Node
第二步为了方便后续进行出队入队操作我们提前准备一个头指针header和一个尾指针tail并通过new关键字为其分配内存空间。 /*** The header of the queue.*/Node header;/*** The tail of the queue.*/Node tail;/************************ Construct an empty sequential list.**********************/public LinkedQueue() {header new Node(-1);// header.next null;tail header;}// Of the first constructor
2.链队列遍历
链队列的遍历我们同样通过重写toString()方法来完成如下 /************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;if (header.next null) {return empty;} // Of ifNode tempNode header.next;while (tempNode ! null) {resultString tempNode.data , ;tempNode tempNode.next;} // Of whilereturn resultString;}// Of toString
这段代码在day13链表中有详细的分析这里就不再重复赘述了。
3.入队
我们知道链表在插入时一共需要三步分别是第一步创建新的结点第二步找到指定插入位置的前一个结点第三步修改该指定插入位置前后的指针指向。但是链队列不一样因为队列只能在队尾插入所以我们只需要在原尾指针之后增加一个新的结点即可具体模拟如下 /************************ Enqueue.* * param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {Node tempNode new Node(paraValue);tail.next tempNode;tail tempNode;}// Of enqueue
首先定义一个新的结点tempNode然后通过语句tail.next tempNode;将原尾指针与新结点链接起来相当于在原尾指针后面插入新结点最后不要忘了更新尾指针将新结点令为新的尾指针因为尾指针始终指向队尾。
4.出队
由于链表的存储方式是在物理空间中直接、任意创建一个新的结点所以它并没有明确的上限所以在上面链队列入队时我们并没有考虑队列是否已满的问题。但是在出队时就需要考虑队列是否为空。
在前面我们已经定义了头指针和尾指针当队列为空时显然头指针等于尾指针所以我们就把header tail作为判断队列是否为空的条件并且规定队列为空时返回 -1。 /************************ Dequeue.* * return The value at the header.**********************/public int dequeue() {if (header tail) {System.out.println(No element in the queue);return -1;} // Of ifint resultValue header.next.data;header.next header.next.next;// The queue becomes empty.if (header.next null) {tail header;} // Of ifreturn resultValue;}// Of dequeue
确定该队列不空后就可以进行出队操作了。早在day13链表中我们就已经知道头结点header的data域是无效的没办法执行删除操作同理这里的头指针header也是如此所以出队时我们需要跳过头指针从头指针后面第一个结点开始。显然header.next就是指的头指针后面第一个结点而header.next.data就是指头指针后面第一个结点的data域也就是第一个有效数据即需要删除的第一个数据所以我们将其赋给resultValue然后再通过header.next header.next.next;实现删除操作。
这里有一个地方需要特别注意当队列中只有一个有效结点时头指针header和尾指针tail的指向如图所示 这个时候再执行header.next header.next.next;毫无疑问就会将该有效结点和尾指针一同删掉所以我们需要重新定义尾指针。具体方法就是当header.next null即队列为空时重新定义尾指针tail header最后不要忘记返回所删掉的数据。
5.数据测试
接下来进行数据测试
创建LinkedQueue类的一个对象tempQueue并调用toString()方法进行遍历此时肯定为空进行入队操作利用for循环向空队列中插入5个队列元素并输出出队一次并输出再循环执行出队操作5次并输出最后再循环入队3次输出 /************************ The entrance of the program.* * param args Not used now.**********************/public static void main(String args[]) {LinkedQueue tempQueue new LinkedQueue();System.out.println(Initialized, the list is: tempQueue.toString());for (int i 0; i 5; i) {tempQueue.enqueue(i 1);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());tempQueue.dequeue();System.out.println(Dequeue, the queue is: tempQueue.toString());int tempValue;for (int i 0; i 5; i) {tempValue tempQueue.dequeue();System.out.println(Looped delete tempValue , the new queue is: tempQueue.toString());} // Of for ifor (int i 0; i 3; i) {tempQueue.enqueue(i 10);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());}// Of main
6.完整的程序代码
package datastructure;/*** Linked queue.* * author Xin Lin 3101540094qq.com.*/
public class LinkedQueue {/*** An inner class.*/class Node {/*** The data.*/int data;/*** The reference to the next node.*/Node next;/********************* * The constructor.* * param paraValue The data.******************* */public Node(int paraValue) {data paraValue;next null;}// Of the constructor}// Of class Node/*** The header of the queue.*/Node header;/*** The tail of the queue.*/Node tail;/************************ Construct an empty sequential list.**********************/public LinkedQueue() {header new Node(-1);// header.next null;tail header;}// Of the first constructor/************************ Enqueue.* * param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {Node tempNode new Node(paraValue);tail.next tempNode;tail tempNode;}// Of enqueue/************************ Dequeue.* * return The value at the header.**********************/public int dequeue() {if (header tail) {System.out.println(No element in the queue);return -1;} // Of ifint resultValue header.next.data;header.next header.next.next;// The queue becomes empty.if (header.next null) {tail header;} // Of ifreturn resultValue;}// Of dequeue/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;if (header.next null) {return empty;} // Of ifNode tempNode header.next;while (tempNode ! null) {resultString tempNode.data , ;tempNode tempNode.next;} // Of whilereturn resultString;}// Of toString/************************ The entrance of the program.* * param args Not used now.**********************/public static void main(String args[]) {LinkedQueue tempQueue new LinkedQueue();System.out.println(Initialized, the list is: tempQueue.toString());for (int i 0; i 5; i) {tempQueue.enqueue(i 1);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());tempQueue.dequeue();System.out.println(Dequeue, the queue is: tempQueue.toString());int tempValue;for (int i 0; i 5; i) {tempValue tempQueue.dequeue();System.out.println(Looped delete tempValue , the new queue is: tempQueue.toString());} // Of for ifor (int i 0; i 3; i) {tempQueue.enqueue(i 10);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());}// Of main
}// Of class LinkedQueue
运行结果 总结
队列是一个非常基本非常重要的数据结构因其先进先出的特性使得它在管理和调度顺序性任务时非常有效在很多实际问题中合理利用队列可以提升效率、保证数据处理的顺序性和稳定性同时队列还可以用来实现很多算法比如广度优先搜索算法、消息传递等等。
队列和我们之前学过的栈都是常用的两种数据结构也均为受限线性表只不过前者为先进先出适用于按顺序处理的场景后者为先进后出适合需要逆序处理的场景。
