数据结构基础03：队列
2021/10/15 23:20:37
本文主要是介绍数据结构基础03：队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
队列的应用
队列也是一种线性结构，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
先进先出（First In First Out）
数组队列
数组队列的实现
enqueue()、dequeue()、getFront()、getSize()、isEmpty()方法就足够操作队列了
public class Algorithm {
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>(20);
for (int i = 0; i < 5; i++) {
queue.enqueue(i);
System.out.println(queue);
}
System.out.println(queue.getSize());
System.out.println(queue.getFront());
System.out.println(queue);
queue.dequeue();
System.out.println(queue);
System.out.println(queue.isEmpty());
}
}
/**
* 创建队列接口，定义抽象方法
*/
interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E element);
E dequeue();
E getFront();
}
/**
* 实现队列接口，创建数组队列类
*/
class ArrayQueue<E> implements Queue<E>{
/**
* 使用动态数组实现队列
*/
Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
/**
* 重写队列接口的方法
*/
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void enqueue(E element) {
array.addLast(element);
}
@Override
public E dequeue() {
return array.removeFirst();
}
/**
* getFront()方法查看队首元素
*/
@Override
public E getFront() {
return array.getFirst();
}
/**
* 重写toString()方法打印队列的信息，如果调用array.toString()方法，打印的是动态数组的信息
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("Queue: front [");
for (int i = 0; i < array.getSize(); i++) {
str.append(array.get(i));
if (i != array.getSize() - 1){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
class Array<E> {
private E[] data;
private int size;
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
public Array(){
this(10);
}
public void add(int index, E element){
if (index < 0 || index > size){
throw new IllegalArgumentException("索引值非法");
}
if (size == data.length){
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
public void addLast(E element){
add(size, element);
}
public void remove(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("索引值非法");
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
data[size] = null;
if (size == data.length / 2 && data.length / 2 != 0){
resize(data.length / 2);
}
}
public E removeFirst(){
if (size == 0) {
throw new IllegalArgumentException("索引值非法");
}
E tem = data[0];
remove(0);
return tem;
}
public int getSize(){
return size;
}
public E get(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("索引值非法");
}
return data[index];
}
public E getFirst(){
return get(0);
}
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public boolean isEmpty(){
return size == 0;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("数组的容量为%d，元素个数为%d\n", data.length, size));
str.append("[");
for (int i = 0; i < size; i++) {
str.append(data[i]);
if (i != size - 1){
str.append(", ");
}
}
str.append("]");
return str.toString();
}
}
数组队列的复杂度分析
getFront()、getSize()、isEmpty()方法的时间复杂度为O(1)
enqueue()方法的均摊复杂度为O(1)
dequeue()方法的时间复杂度是O(n)，因为每次出队时，后面的所有元素都要往前移一位
循环队列
循环队列的实现
循环队列在队首元素出队时，只是将front标志位加一，而不进行所有元素的移动。当元素填满后面的位置时，如果front标志位不为零，就将tail标志位设为零，将元素添加进前部的空间
当元素刚好填满队列时，front == 0，tail == length - 1（tail取不到length）；或者使用了前部的空间时满了，front == tail + 1（留一个空位）
综合两种情况，front == (tail + 1) % length代表队列满了，而front == tail代表队列空了
public class Algorithm {
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>(5);
for (int i = 0; i < 6; i++) {
queue.enqueue(i);
System.out.println(queue);
}
System.out.println(queue.getSize());
System.out.println(queue.getFront());
queue.dequeue();
System.out.println(queue);
System.out.println(queue.isEmpty());
}
}
/**
* 创建队列接口，定义抽象方法
*/
interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E element);
E dequeue();
E getFront();
}
/**
* 实现队列接口，创建循环队列类
*/
class LoopQueue<E> implements Queue<E>{
/**
* 使用动态数组实现循环队列
*/
private E[] data;
private int front, tail, size;
public LoopQueue(int capacity){
/**
* 因为循环队列会浪费一个空间，为了确保能存储capacity个元素，初始化时加1
*/
data = (E[]) new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(5);
}
/**
* 重写循环队列接口的方法
*/
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
/**
* front == tail时，说明队列没有元素
*/
return front == tail;
}
@Override
public void enqueue(E element) {
/**
* 入队判断是否满了
* front == (tail + 1) % data.length时，说明队列元素满了，需要扩容
* 如果front == 0，此时tail是等于data.length - 1的，然后就会扩容，所以取不到data.length
*/
if (front == (tail + 1) % data.length){
resize(2 * (data.length - 1));
}
data[tail] = element;
/**
* tail不能直接加1，因为可能等于data.length - 1，因此加1后对长度取余，循环取值
*/
tail = (tail + 1) % data.length;
size++;
}
@Override
public E dequeue() {
/**
* 出队判断是否为空，空了只能抛出异常
*/
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
E tem = data[front];
/**
* 因为该元素为引用，所以在不需要时将其赋值为null，避免空间泄露
*/
data[front] = null;
front = (front + 1) % data.length;
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return tem;
}
public void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
/**
* getFront()方法查看队首元素
*/
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[front];
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, size));
for (int i = 0; i < size; i++) {
str.append(data[(front + i) % data.length]);
/**
* 此处不能写(front + i) % data.length != tail - 1
* 因为如果tail为0，就出现负索引了
*/
if ((front + i + 1) % data.length != tail){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
循环队列的复杂度分析
dequeue()方法的均摊复杂度降为了O(1)
数组队列和循环队列的性能比较
import java.util.Random;
public class Algorithm {
public static void main(String[] args) {
int count = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
System.out.println("数组队列用时：" + test(arrayQueue, count) + "秒");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
System.out.println("循环队列用时：" + test(loopQueue, count) + "秒");
}
/**
* 多态性可以让接口接收不同的实现接口的类对象
*/
public static double test(Queue<Integer> name, int count){
Random random = new Random();
long startTime = System.nanoTime();
for (int i = 0; i < count; i++) {
name.enqueue(random.nextInt(count));
}
for (int i = 0; i < count; i++) {
name.dequeue();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
}
interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E element);
E dequeue();
E getFront();
}
class LoopQueue<E> implements Queue<E>{
private E[] data;
private int front, tail, size;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(5);
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public void enqueue(E element) {
if (front == (tail + 1) % data.length){
resize(2 * (data.length - 1));
}
data[tail] = element;
tail = (tail + 1) % data.length;
size++;
}
@Override
public E dequeue() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
E tem = data[front];
data[front] = null;
front = (front + 1) % data.length;
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return tem;
}
public void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[front];
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, size));
for (int i = 0; i < size; i++) {
str.append(data[(front + i) % data.length]);
if ((front + i + 1) % data.length != tail){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
class ArrayQueue<E> implements Queue<E>{
Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void enqueue(E element) {
array.addLast(element);
}
@Override
public E dequeue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("Queue: front [");
for (int i = 0; i < array.getSize(); i++) {
str.append(array.get(i));
if (i != array.getSize() - 1){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
class Array<E> {
private E[] data;
private int size;
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
public Array(){
this(10);
}
public void add(int index, E element){
if (index < 0 || index > size){
throw new IllegalArgumentException("索引值非法");
}
if (size == data.length){
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
public void addLast(E element){
add(size, element);
}
public void remove(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("索引值非法");
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
data[size] = null;
if (size == data.length / 2 && data.length / 2 != 0){
resize(data.length / 2);
}
}
public E removeFirst(){
if (size == 0) {
throw new IllegalArgumentException("索引值非法");
}
E tem = data[0];
remove(0);
return tem;
}
public int getSize(){
return size;
}
public E get(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("索引值非法");
}
return data[index];
}
public E getFirst(){
return get(0);
}
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public boolean isEmpty(){
return size == 0;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("数组的容量为%d，元素个数为%d\n", data.length, size));
str.append("[");
for (int i = 0; i < size; i++) {
str.append(data[i]);
if (i != size - 1){
str.append(", ");
}
}
str.append("]");
return str.toString();
}
}
作业1：浪费一个空间，不使用size变量
public class Algorithm {
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>(5);
for (int i = 0; i < 6; i++) {
queue.enqueue(i);
System.out.println(queue);
}
System.out.println(queue.getSize());
System.out.println(queue.getFront());
queue.dequeue();
System.out.println(queue);
System.out.println(queue.isEmpty());
}
}
interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E element);
E dequeue();
E getFront();
}
class LoopQueue<E> implements Queue<E>{
private E[] data;
private int front, tail;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity + 1];
front = 0;
tail = 0;
}
public LoopQueue(){
this(5);
}
@Override
public int getSize() {
/**
* 比较front和tail的前后顺序就可以算出队列大小
*/
if (front <= tail) {
return tail - front;
}
else {
return tail + data.length - front;
}
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public void enqueue(E element) {
if (front == (tail + 1) % data.length){
resize(2 * (data.length - 1));
}
data[tail] = element;
tail = (tail + 1) % data.length;
}
@Override
public E dequeue() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
E tem = data[front];
data[front] = null;
front = (front + 1) % data.length;
if (getSize() == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return tem;
}
public void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < getSize(); i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = getSize();
}
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[front];
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, getSize()));
for (int i = 0; i < getSize(); i++) {
str.append(data[(front + i) % data.length]);
if ((front + i + 1) % data.length != tail){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
作业2：使用size变量，不浪费一个空间
public class Algorithm {
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>(5);
for (int i = 0; i < 6; i++) {
queue.enqueue(i);
System.out.println(queue);
}
System.out.println(queue.getSize());
System.out.println(queue.getFront());
queue.dequeue();
System.out.println(queue);
System.out.println(queue.isEmpty());
}
}
interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E element);
E dequeue();
E getFront();
}
class LoopQueue<E> implements Queue<E>{
private E[] data;
private int front, tail, size;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(5);
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E element) {
if (size == data.length) {
resize(2 * data.length);
}
data[tail] = element;
tail = (tail + 1) % data.length;
size++;
}
@Override
public E dequeue() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
E tem = data[front];
data[front] = null;
front = (front + 1) % data.length;
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return tem;
}
public void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[front];
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length, size));
for (int i = 0; i < size; i++) {
str.append(data[(front + i) % data.length]);
if ((front + i + 1) % data.length != tail){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
双端队列
双端队列，队首和队尾都可以入队和出队
队首出队和队尾入队和普通队列一样，需要新增队首入队和队尾出队的方法
public class Algorithm {
public static void main(String[] args) {
Deque<Integer> queue = new Deque<>(5);
for (int i = 0; i < 10; i++) {
/**
* 偶数在队首入队，奇数在队尾入队
*/
if (i % 2 == 0) {
queue.addFront(i);
System.out.println(queue);
}
else {
queue.addLast(i);
System.out.println(queue);
}
}
for (int i = 0; i < 10; i++) {
/**
* 偶数在队首出队，奇数在队尾出队
*/
if (i % 2 == 0) {
queue.removeFront();
System.out.println(queue);
}
else {
queue.removeLast();
System.out.println(queue);
}
}
System.out.println(queue.isEmpty());
}
}
interface Queue<E> {
int getSize();
boolean isEmpty();
/**
* 新增队首入队和队尾出队的方法
*/
void addFront(E element);
void addLast(E element);
E removeFront();
E removeLast();
E getFront();
E getLast();
}
class Deque<E> implements Queue<E>{
private E[] data;
private int front, tail, size;
public Deque(int capacity){
data = (E[]) new Object[capacity];
front = 0;
tail = 0;
size = 0;
}
public Deque(){
this(5);
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void addLast(E element) {
if (size == data.length) {
resize(2 * data.length);
}
data[tail] = element;
tail = (tail + 1) % data.length;
size++;
}
@Override
public void addFront(E element){
if (size == data.length){
resize(2 * data.length);
}
/**
* 队首入队，需要判断front是否为0
*/
front = front == 0 ? data.length - 1 : front - 1;
data[front] = element;
size++;
}
@Override
public E removeFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
E tem = data[front];
data[front] = null;
front = (front + 1) % data.length;
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return tem;
}
@Override
public E removeLast(){
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
/**
* 队尾出队，需要判断tail是否为0
*/
tail = tail == 0 ? data.length - 1 : tail - 1;
E tem = data[tail];
data[tail] = null;
size--;
if (size == data.length / 4 && data.length / 2 != 0){
resize(data.length / 2);
}
return tem;
}
public void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[front];
}
@Override
public E getLast(){
if (isEmpty()){
throw new IllegalArgumentException("队列空了");
}
return data[tail == 0 ? data.length - 1 : tail - 1];
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length, size));
for (int i = 0; i < size; i++) {
str.append(data[(front + i) % data.length]);
/**
* i != size - 1判断是否是最后一个元素更方便
*/
if (i != size - 1){
str.append(", ");
}
}
str.append("] tail");
return str.toString();
}
}
拓展：为什么不推荐使用Stack类实现栈，而用Deque类
因为Stack类继承了Vetor类，可以使用父类的其他方法操作栈，破坏了类的封装性
而Deque作为双端队列，可以实现栈的功能。但事实上，由于其可以双端进行操作，也破坏了类的封装性
虽然Java推荐使用Deque类实现栈，但最好的方式是自己设计一个栈类
这篇关于数据结构基础03：队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-01Java部署教程：新手入门指南
- 2024-11-01Java部署教程：从入门到实践
- 2024-11-01Java订单系统教程：新手入门指南
- 2024-11-01Java分布式教程：新手入门指南
- 2024-11-01Java管理系统教程：新手入门详解
- 2024-11-01Java监控系统教程：从入门到实践
- 2024-11-01SpringCloud Alibaba入门：轻松搭建微服务架构
- 2024-11-01Swagger入门：新手必读指南
- 2024-11-01Swagger入门：轻松搭建API文档
- 2024-11-01uni-APP入门：新手快速上手指南
