Day 9
阿柠·
帮助1人
Java 线性数据结构（四）
学习来源： 日撸 Java 三百行（11-20天，线性数据结构）
一、链队列
链队列比较容易写.
Node 类以前是 LinkdedList 的内嵌类, 这里重写了一遍. 访问控制的事情以后再说.
为方便操作, 空队列也需要一个节点. 这和以前的链表同理. 头节点的引用 (指针) 称为 header.
入队仅操作尾部, 出队仅操作头部.
题目一：入队
输入：给定数paraValue
示例：
1
输出：队列
示例：
Enqueue, the queue is: 1,
题目二：出队
输出：队列
示例：
No element in the queue
或
Looped delete 1, the new queue is: 2,3, 4, 5,
代码如下：
package datastructure.queue;
/**
*
* @author Ling Lin E-mail:linling0.0@foxmail.com
*
* @version 创建时间：2022年4月15日 下午5:41:51
*
*/
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 construct
/*
* 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 if
int resultValue = header.next.data;
header.next = header.next.next;
// The queue becomes empty.
if (header.next == null) {
tail = header;
} // Of if
return resultValue;
}// Of dequeue
/**
* Overrides the method claimed in Object, the superclass of any class.
*
*/
@Override
public String toString() {
String resultString = "";
if (header.next == null) {
return "empty";
} // Of if
Node tempNode = header.next;
while (tempNode != null) {
resultString = tempNode.data ", ";
tempNode = tempNode.next;
} // Of while
return resultString;
}// Of toString
/*
* The entrance of the program.
*
* @para args Not used now.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
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 i
System.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 i
for (int i = 0; i < 3; i ) {
tempQueue.enqueue(i 10);
} // Of for i
System.out.println("Enqueue, the queue is: " tempQueue.toString());
}// Of main
}// Of class LinkedQueue
运行结果：
二、循环队列
整除的作用.
想像操场跑道里放一队人, 循环的感觉就出来了.
为了区分空队列与满队列, 需要留一个空间. 相当于不允许首尾相连. 还是画个图吧, 否则容易进坑.
用链式结构, 空间的分配与回收由系统做, 用循环队列, 则是自己把控. 想像自己写的是操作系统, 从这个代码可以感受下内存的管理.
题目一：入队
输入：给定数paraValue
示例：
1
输出：队列
示例：
Enqueue, the queue is: 1, 2, 3, 4, 5,
或
Queue full.
题目二：出队
输出：队列
示例：
Dequeue 1, the queue is: 2, 3, 4, 5,
或
Queue full.
代码如下：
package datastructure.queue;
/**
*
* @author Ling Lin E-mail:linling0.0@foxmail.com
*
* @version 创建时间：2022年4月15日 下午6:39:39
*
*/
public class CircleIntQueue {
// The total space. One space can never be used.
public static final int TOTAL_SPACE = 10;
// The data.
int[] data;
// The index for calculating the head. The actual head is head % TOTAL_SPACE
int head;
// The index for calculating the tail.
int tail;
/**
* The constructor
*
*/
public CircleIntQueue() {
data = new int[TOTAL_SPACE];
head = 0;
tail = 0;
}// Of the first constructor
/**
* Enqueue.
*
* @param paraValue
* The value of the new node.
*/
public void enqueue(int paraValue) {
if ((tail 1) % TOTAL_SPACE == head) {
System.out.println("Queue full.");
return;
} // Of if
data[tail % TOTAL_SPACE] = paraValue;
tail ;
}// Of enqueue
public int dequeue() {
if (head == tail) {
System.out.println("No element int the queue");
return -1;
} // Of if
int resultValue = data[head % TOTAL_SPACE];
head ;
return resultValue;
}// Of dequeue
/**
*
* Overrides the method claimed in Object, the superclass of any class.
*
* @param args
*/
@Override
public String toString() {
String resultString = "";
if (head == tail) {
return "empty";
} // Of if
for (int i = head; i < tail; i ) {
resultString = data[i % TOTAL_SPACE] ", ";
} // Of for i
return resultString;
}// Of toString
/**
* The entrance of the program.
*
* @param args
* Not used now.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CircleIntQueue tempQueue = new CircleIntQueue();
System.out.println("Initialized, the list is: " tempQueue.toString());
for (int i = 0; i < 5; i ) {
tempQueue.enqueue(i 1);
} // Of for i
System.out.println("Enqueue, the queue is: " tempQueue.toString());
int tempValue = tempQueue.dequeue();
System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
for (int i = 0; i < 6; i ) {
tempQueue.enqueue(i 10);
System.out.println("Enqueue, the queue is: " tempQueue.toString());
} // Of for i
for (int i = 0; i < 3; i ) {
tempValue = tempQueue.dequeue();
System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
} // Of for i
for (int i = 0; i < 6; i ) {
tempQueue.enqueue(i 100);
System.out.println("Enqueue, the queue is: " tempQueue.toString());
} // Of for i
}// Of main
}// Of CircleIntQueue
运行结果：
由于后面还要用到字符队列, 就把上面这个程序中的 int 改成 char, 并作相应调整, 获得如下程序.
//package datastructure.queue;
//
///**
// *
// * @author Ling Lin E-mail:linling0.0@foxmail.com
// *
// * @version 创建时间：2022年4月15日 下午6:39:39
// *
// */
//public class CircleIntQueue {
//
// // The total space. One space can never be used.
// public static final int TOTAL_SPACE = 10;
//
// // The data.
// int[] data;
//
// // The index for calculating the head. The actual head is head % TOTAL_SPACE
// int head;
//
// // The index for calculating the tail.
// int tail;
//
// /**
// * The constructor
// *
// */
// public CircleIntQueue() {
// data = new int[TOTAL_SPACE];
// head = 0;
// tail = 0;
// }// Of the first constructor
//
// /**
// * Enqueue.
// *
// * @param paraValue
// * The value of the new node.
// */
// public void enqueue(int paraValue) {
// if ((tail 1) % TOTAL_SPACE == head) {
// System.out.println("Queue full.");
// return;
// } // Of if
//
// data[tail % TOTAL_SPACE] = paraValue;
// tail ;
// }// Of enqueue
//
// public int dequeue() {
// if (head == tail) {
// System.out.println("No element int the queue");
// return -1;
// } // Of if
//
// int resultValue = data[head % TOTAL_SPACE];
//
// head ;
//
// return resultValue;
// }// Of dequeue
//
// /**
// *
// * Overrides the method claimed in Object, the superclass of any class.
// *
// * @param args
// */
// @Override
// public String toString() {
// String resultString = "";
//
// if (head == tail) {
// return "empty";
// } // Of if
//
// for (int i = head; i < tail; i ) {
// resultString = data[i % TOTAL_SPACE] ", ";
// } // Of for i
//
// return resultString;
// }// Of toString
//
// /**
// * The entrance of the program.
// *
// * @param args
// * Not used now.
// */
// public static void main(String[] args) {
// // TODO Auto-generated method stub
// CircleIntQueue tempQueue = new CircleIntQueue();
// System.out.println("Initialized, the list is: " tempQueue.toString());
//
// for (int i = 0; i < 5; i ) {
// tempQueue.enqueue(i 1);
// } // Of for i
// System.out.println("Enqueue, the queue is: " tempQueue.toString());
// int tempValue = tempQueue.dequeue();
// System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
//
// for (int i = 0; i < 6; i ) {
// tempQueue.enqueue(i 10);
// System.out.println("Enqueue, the queue is: " tempQueue.toString());
// } // Of for i
//
// for (int i = 0; i < 3; i ) {
// tempValue = tempQueue.dequeue();
// System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
// } // Of for i
//
// for (int i = 0; i < 6; i ) {
// tempQueue.enqueue(i 100);
// System.out.println("Enqueue, the queue is: " tempQueue.toString());
// } // Of for i
// }// Of main
//
//}// Of CircleIntQueue
package datastructure.queue;
/**
*
* @author Ling Lin E-mail:linling0.0@foxmail.com
*
* @version 创建时间：2022年4月15日 下午6:39:39
*
*/
public class CircleIntQueue {
// The total space. One space can never be used.
public static final int TOTAL_SPACE = 10;
// The data.
char[] data;
// The index for calculating the head. The actual head is head % TOTAL_SPACE
int head;
// The index for calculating the tail.
int tail;
/**
* The constructor
*
*/
public CircleIntQueue() {
data = new char[TOTAL_SPACE];
head = 0;
tail = 0;
}// Of the first constructor
/**
* Enqueue.
*
* @param paraValue
* The value of the new node.
*/
public void enqueue(char paraValue) {
if ((tail 1) % TOTAL_SPACE == head) {
System.out.println("Queue full.");
return;
} // Of if
data[tail % TOTAL_SPACE] = paraValue;
tail ;
}// Of enqueue
public char dequeue() {
if (head == tail) {
System.out.println("No element int the queue");
return '\0';
} // Of if
char resultValue = data[head % TOTAL_SPACE];
head ;
return resultValue;
}// Of dequeue
/**
*
* Overrides the method claimed in Object, the superclass of any class.
*
* @param args
*/
@Override
public String toString() {
String resultString = "";
if (head == tail) {
return "empty";
} // Of if
for (int i = head; i < tail; i ) {
resultString = data[i % TOTAL_SPACE] ", ";
} // Of for i
return resultString;
}// Of toString
/**
* The entrance of the program.
*
* @param args
* Not used now.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CircleIntQueue tempQueue = new CircleIntQueue();
System.out.println("Initialized, the list is: " tempQueue.toString());
for (char i = '0'; i < '5'; i ) {
tempQueue.enqueue(i);
} // Of for i
System.out.println("Enqueue, the queue is: " tempQueue.toString());
char tempValue = tempQueue.dequeue();
System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
for (char i = 'a'; i < 'f'; i ) {
tempQueue.enqueue(i);
System.out.println("Enqueue, the queue is: " tempQueue.toString());
} // Of for i
for (int i = 0; i < 3; i ) {
tempValue = tempQueue.dequeue();
System.out.println("Dequeue " tempValue ", the queue is: " tempQueue.toString());
} // Of for i
for (char i = 'A'; i < 'F'; i ) {
tempQueue.enqueue(i);
System.out.println("Enqueue, the queue is: " tempQueue.toString());
} // Of for i
}// Of main
}// Of CircleIntQueue
运行结果：
这篇好文章是转载于：编程之路
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 编程之路
- 本文地址： /boutique/detail/tanhhacjjh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13
