当前位置：首页 > news >正文

Java - 数据结构，队列

news 2025/9/17 9:59:47

一、什么是队列

普通队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）
在这里插入图片描述
双端队列：可以在对头或者队尾进行插入或者删除操作。

普通队列和双端队列

从上面知道双向列表可以当普通队列使用，也可以当双端队列使用，也可以当栈使用。

二、队列常用的方法

2.1、Queue

在这里插入图片描述
注意add函数和offer函数

public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.add(1);//添加元素queue.add(2);//添加元素queue.add(3);//添加元素queue.offer(4);//添加元素queue.offer(5);//添加元素queue.offer(6);//添加元素System.out.println(queue.peek());//获取对头元素，但是不删除System.out.println(queue.element());//获取对头元素，但是不删除System.out.println(queue.poll());//获取对头元素，并且删除对头元素System.out.println(queue.remove());//获取对头元素，并且删除对头元素}

2.2、Deque

在这里插入图片描述

public static void main(String[] args) {Deque<Integer> deque = new LinkedList<>();deque.add(1);//默认在队尾添加元素deque.addFirst(2);//在对头添加元素deque.addLast(3);//在队尾添加元素deque.offer(4);//在队尾添加元素deque.offerLast(5);//在队尾添加元素deque.offerFirst(6);//在队头添加元素System.out.println(deque);System.out.println(deque.peek());//获取元素，但是不删除System.out.println(deque.peekFirst());//获取队头元素，但是不删除System.out.println(deque.peekLast());//获取队尾元素，但是不删除System.out.println(deque.poll());//获取队头元素，并且删除System.out.println(deque.pollFirst());//获取队头元素，并且删除System.out.println(deque);}

三、单链表模拟实现队列

在这里插入图片描述
单链表可以实现队列，那双向链表也可以实现队列
使用单链表第三种方式实现队列
offer（）- 在队列里面添加元素

/*** 在队列里面添加元素，实际上就是尾插法* @param val*/public void offer(int val){//要插入节点，那就要先创造一个节点Node node = new Node(val);//这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入if(head == null){//head == null说明是第一次插入head = node;last = node;}else {last.next = node;last = last.next;}}

在这里插入图片描述

poll（） - 出队列

/*** 出队列，并且删除元素* @return*/public int poll(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}int oldVal = head.val;head = head.next;return oldVal;}/*** 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE* @return*/public boolean isEmpty(){return this.head == null;}

使用的单链表实现简单的队列

//使用单链表实现队列，首先就要定义节点
class Node{//值域public int val;//指针域public Node next;public Node(int val){this.val = val ;}
}
public class MyQueue {//单链表实现队列，那就要加上一个尾指针public Node head;//头结点public Node last;//尾巴节点/*** 在队列里面添加元素，实际上就是尾插法* @param val*/public void offer(int val){//要插入节点，那就要先创造一个节点Node node = new Node(val);//这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入if(head == null){//head == null说明是第一次插入head = node;last = node;}else {last.next = node;last = last.next;}}/*** 出队列，并且删除元素* @return*/public int poll(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}int oldVal = head.val;head = head.next;return oldVal;}/*** 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE* @return*/public boolean isEmpty(){return this.head == null;}/*** 获取对头的元素* @return*/public int peek(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}return head.val;}
}

四、循环队列

我们说了可以利用链表实现队列，那能不能利用数组实现队列？？？
在这里插入图片描述
上图转载于：https://blog.csdn.net/DarkAndGrey/article/details/122511544

队列面试题

设计循环队列

上图转载于：https://blog.csdn.net/DarkAndGrey/article/details/122511544

代码如下：

public class MyCircularQueue {//我们知道循环队列是有数组实现的，所以要创建一个数组，并且还有表示对头和队尾的下标public int[] elem;public int front;//对头的下标public int rear;//队尾的下标/*** 构造方法，初始化数组的大小* @param k*/public MyCircularQueue(int k) {this.elem = new int[k+1];}/*** 入队列* @param value* @return*/public boolean enQueue(int value) {//在入队列的时候先判断队列是否满，满了不能入if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}/*** 出队列* @return*/public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;return true;}/*** 返回对头下标的元素* @return*/public int Front() {if(isEmpty()){return -1;}return elem[front];}/*** 获取队尾元素* @return*/public int Rear() {if(isEmpty()){return -1;}int index = 0;if(rear == 0){index = elem.length - 1;}else{index = rear - 1;}return elem[index];}public boolean isEmpty() {//front的下一个是rear，那就说明空了return front == rear;}/*** 判断队列是否满* @return*/public boolean isFull() {//rear的下一个如果是front，那这个队列就满了if((rear+1) % elem.length == front){return true;}return false;}
}

用队列实现栈