数据结构学习一队列整理
程序员文章站
2024-03-18 11:34:34
...
队列
1.定义
- 一种先进先出的数据结构,从队尾入队,队头出队。
2.实现
class MyQueue {
// 队列
private List<Integer> data;
// 头指针
private int p_start;
//队列的初始化
public MyQueue() {
data = new ArrayList<Integer>();
p_start = 0;
}
/** 入队成功了,返回true */
public boolean enQueue(int x) {
data.add(x);
return true;
};
/**出队,成功返回true */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
p_start++;
return true;
}
/** 获取队首元素 */
public int Front() {
return data.get(p_start);
}
/** C判断队列是否为空 */
public boolean isEmpty() {
return p_start >= data.size();
}
};
public class Main {
public static void main(String[] args) {
MyQueue q = new MyQueue();
q.enQueue(5);
q.enQueue(3);
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
}
}
3.队列实现的步骤
- 构造一个存放数据的队列
- 队列的数据结构:存放数据的队列集合、指示队首坐标的“指针”
- 队列的初始化
- 入队操作
- 判断队列是否满了
- 出队操作
- 判断队列是否空了
- 查看队首元素(第一个出队的元素)
4.特点
- 按顺序处理元素
循环队列
1.定义
- 将队首和队尾相连,通过两个指向队首和队尾的“指针”完成首尾相连,可以高效的利用队列的空间。
2.实现
class CircleQueue {
private int[] data;
private int head;
private int tail;
private int size;
//初始化队列
CilcleQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
//判断队列为空
public boolean isEmpty() {
return tail == -1;
}
//判断队列是否为满
public boolena isFull() {
return (tail + 1) % size == head;
}
//入队
public boolean enQueue(int value) {
if(isFull() == true) {
return false;
}
if(isEmpty() == true) {
head += 1;
}
tail = (tail+1) % size;
data[tail] = value;
return true;
}
//出队
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
//获取队头元素
public int Front() {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
//获取队尾元素
public int Rear() {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
}
3.实现步骤
- 构造循环队列的数据结构
- 存放队列数据的数组、指向队首和队尾的“指针”、队列长度
- 队列的初始化
- 入队
- 判断队满;判断队空,则将指向队首元素的“指针”+1
- 出队
- 判断队空,则将指向队首和队尾的“指针”重新赋值为初始值
- 查看队首元素
- 查看队尾元素
队列的判空与判满的条件
- 判空:根据队尾"指针"是否为初始值-1
- 判满:根据队尾"指针"+1对队列长度取余是否等于队首"指针"
使用内置队列库
实现
public static void main(String[] args) {
//定义一个链队列
LinkedList<Integer> q = new LinkedList();
//入队
q.add(1);
q.add(2);
q.offer(3);
System.out.println(q);
//出队
q.remove();
System.out.println(q);
if(aQueue.isEmpty())
System.out.println("true");
System.out.println("false");
}
}
上一篇: Java集合之Queue