数据结构之队列的详解

news/2024/11/30 2:32:47/

文章目录

  • 一.什么是队列
  • 二.队列的使用
    • 2.1 队列的基本操作
    • 2.2 队列的基本使用
  • 三.队列的模拟实现
    • 3.1 数组实现队列
    • 3.2 链表实现队列
  • 四.队列的应用
    • 4.1 设计循环队列
    • 4.2 设计双端队列
    • 4.3 队列实现栈
    • 4.4 栈实现队列
  • 五.总结

一.什么是队列

  • 队列是一种先入先出(FIFO)的线性表数据结构
  • 添加和删除操作只在表的两端进行,一端为队头,另一端为队尾
  • 添加操作在队尾进行,称为入队或进队,删除操作在队头进行,称为出队

二.队列的使用

2.1 队列的基本操作

在这里插入图片描述
队列的图示
在这里插入图片描述

2.2 队列的基本使用

java内部的api

在这里插入图片描述

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}

三.队列的模拟实现

  • 可以使用数组或链表实现队列
  • 使用数组实现时,需要维护两个指针front和rear,分别指向队头和队尾的下一个位置
  • 使用链表实现时,链表的头节点作为队头,尾节点作为队尾
  • 实现需要包含的方法有:入队add、出队remove、获取队头peek、判断是否为空isEmpty等

3.1 数组实现队列

public class ArrayQueue {private int front;private int rear;private int[] arr;private int capacity;public ArrayQueue(int capacity) {this.capacity = capacity;front = rear = 0;arr = new int[capacity];}// 入队操作,将元素加入队尾public void add(int elem) {if (rear == capacity) {System.out.println("队列已满");return;}arr[rear] = elem;rear++;}// 出队操作,移除队头元素public int remove() {if (front == rear) {System.out.println("队列为空"); return -1;}int elem = arr[front];front++;return elem;}  // 获取队头元素public int peek() {if (front == rear) {System.out.println("队列为空");return -1;}return arr[front];}  // 判断队列是否为空public boolean isEmpty() {return front == rear;}
}

3.2 链表实现队列

/*** @Author 12629* @Description：*/
public class MyQueue {static class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;public Node last;public int usedSize;//入队public void offer(int val) {Node node = new Node(val);if(head == null) {head = node;last = node;}else {last.next = node;last = node;}usedSize++;}public int poll() {if(empty()) {throw new EmptyException("队列为空");}int ret = head.val;head = head.next;if(head == null) {last = null;//只有一个节点 那么last也要置空}usedSize--;return ret;}public boolean empty() {return usedSize == 0;}public int peek() {if(empty()) {throw new EmptyException("队列为空");}return head.val;}public int getUsedSize() {return usedSize;}
}

四.队列的应用

4.1 设计循环队列

其实我们在设计循环队列的时候,我们最重要的一点就是如何考虑空与满的情况
大家肯定很难理解我在说什么,大家看我接下来的操作.
在这里插入图片描述
我们只要解决上面俩个核心问题,就能完整的构造循环队列
这思路巧妙的应用了一个取模运算
在这里插入图片描述

当然这里我们提供了三种思路:

  1. 通过添加 size 属性记录
 public boolean enQueue(int value) {if (size == elem.length) return false; //判断满elem[rear] = value;rear = (rear + 1) % elem.length;size++;return true;}public boolean deQueue() {if (size == 0) return false; //判断空front = (front + 1) % elem.length;size--;return true;}
  1. 保留一个位置
public class MyCircularQueue {private int[] elem;private int front;private int rear;public MyCircularQueue(int k) {elem = new int[k+1];  //多一位}public boolean enQueue(int value) {if ((rear + 1) % elem.length == front) return false; //判断满elem[rear] = value;rear = (rear + 1) % elem.length;  return true;}  
}
  1. 使用标记
  public boolean enQueue(int value) {if (full) return false;   //判断满elem[rear] = value;rear = (rear + 1) % elem.length;  if (rear == front) full = true; //修改标记return true;}public boolean deQueue() {if (isEmpty()) return false;  //判断空front = (front + 1) % elem.length;full = false;     //修改标记return true;}

具体步骤:
5. 使用数组elem存储队列元素,定义front和rear指针表示队头和队尾位置。
6. enQueue(value)方法:先判断队列是否已满,未满则将元素加入rear位置,rear加1取模防止越界。
7. deQueue()方法:先判断队列是否为空,非空则front加1取模。
8. Front()方法:直接返回front位置元素,队空则返回-1。
9. Rear()方法:直接返回rear-1位置元素,队空则返回-1。需要判断rear是否为0,是则返回length-1位置元素。
10. isEmpty()方法:通过判断front和rear是否相等确定队列是否为空。
11. isFull()方法:通过判断rear+1位置是否等于front确定队列是否已满。
时间复杂度分析:

  • enQueue和deQueue方法时间复杂度O(1)。
  • 其他方法时间复杂度O(1)。
    空间复杂度分析:O(n),数组使用O(n)空间。

具体代码:

class MyCircularQueue {private int[] elem;private int front;//表示队列的头private int rear;//表示队列的尾public MyCircularQueue(int k) {//如果是浪费空间 这里必须处理多加一个1this.elem = new int[k+1];}/*** 入队列* @param value* @return*/public boolean enQueue(int value) {//1、检查是否队列是满的if(isFull()){return false;}//2、elem[rear] = value;//rear++;rear = (rear+1) % elem.length;return true;}/*** 出队列* @return*/public boolean deQueue() {if(isEmpty()) {return false;}//front++;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 = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {return front == rear;}/*** 队列是否为满* @return*/public boolean isFull() {/* if( (rear+1) % elem.length == front) {return true;}return false;*/return (rear+1) % elem.length == front;}
}

4.2 设计双端队列

具体思路:

  1. 可以使用链表或数组实现,这里我们使用数组实现。定义数组elem存储数据,front和rear分别表示头尾指针。
  2. 添加方法:
  • addFront(val):将元素插入至队头,front减1取模,将val放入front位置。
  • addRear(val):将元素插入至队尾,rear加1取模,将val放入rear位置。
  1. 移除方法:
  • removeFront():移除队头元素,front加1取模,返回front位置元素。
  • removeRear():移除队尾元素,rear减1取模,返回rear位置元素。
  1. 获取方法:
  • getFront():返回front位置元素,队空则返回-1。
  • getRear():返回rear位置元素,队空则返回-1。
  1. 判断方法:
  • isEmpty():当front==rear时,队列为空,返回true,否则返回false。
  • isFull():当(rear+1)%len==front时,队列已满,返回true,否则返回false。len为数组长度。
  1. 扩容方法:当添加元素时判断队列已满,调用扩容方法expand将数组size*2,并把原数据复制过来。

具体代码:

public class Deque {private int[] elem;private int front;private int rear;private int len;public Deque(int capacity) {elem = new int[capacity];front = rear = 0;len = 0;}//在队头添加元素public void addFront(int val) {if (isFull()) expand();front = (front - 1 + elem.length) % elem.length;elem[front] = val;len++;}//在队尾添加元素public void addRear(int val) {if (isFull()) expand();elem[rear] = val;rear = (rear + 1) % elem.length; len++;}  //移除队头元素public int removeFront() {if (isEmpty()) return -1;int ret = elem[front];front = (front + 1) % elem.length;len--;return ret;}//移除队尾元素public int removeRear() {if (isEmpty()) return -1;rear = (rear - 1 + elem.length) % elem.length;int ret = elem[rear];len--;return ret;}//获取队头元素public int getFront() {if (isEmpty()) return -1;return elem[front];} //获取队尾元素public int getRear() {if (isEmpty()) return -1;return elem[(rear - 1 + elem.length) % elem.length];}  //判断队列是否为空public boolean isEmpty() {return front == rear; }//判断队列是否已满public boolean isFull() {return (rear + 1) % elem.length == front; }//扩容方法private void expand() {int[] newElem = new int[elem.length * 2];for (int i = 0; i < len; i++) {newElem[i] = elem[(i + front) % elem.length]; }front = 0;rear = len;elem = newElem;}
}

4.3 队列实现栈

队列实现栈,在实现栈之前,我们先了解一下栈是怎么工作的,看下图

在这里插入图片描述

再看看两个队列是怎么实现栈的过程,我们用队列模拟,要记住一个核心规则

在这里插入图片描述
我演示一下入栈的规则
在这里插入图片描述
出栈的模拟演示:
在这里插入图片描述

代码如下:

import java.util.LinkedList;
import java.util.Queue;class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);}else {qu1.offer(x);}}public int pop() {if(empty()) {return -1;//两个队列都为空，意味着当前的栈为空}if(!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size-1; i++) {//for (int i = 0; i < qu1.size()-1; i++) {int val = qu1.poll();qu2.offer(val);}return qu1.poll();}else {int size = qu2.size();for (int i = 0; i < size-1; i++) {int val = qu2.poll();qu1.offer(val);}return qu2.poll();}}//peekpublic int top() {if(empty()) {return -1;//两个队列都为空，意味着当前的栈为空}if(!qu1.isEmpty()) {int size = qu1.size();int val = -1;for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}else {int size = qu2.size();int val = -1;for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

4.4 栈实现队列

栈实现队列,还是老样子,我们还是来看看队列的工作状态
在这里插入图片描述
具体我们使用俩个栈模拟出队的操作

在这里插入图片描述

具体代码:

import java.util.Stack;class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}

五.总结

  • 队列是一种先入先出的线性表数据结构
  • 可以使用数组或链表实现队列,实现需要包含的方法有入队add、出队remove等
  • 队列操作的时间复杂度均为O(1),不受队列大小影响

http://www.ppmy.cn/news/60730.html

相关文章

【Linux内核解析-linux-5.14.10-内核源码注释】内核源码中宏定义理解

【Linux内核解析-linux-5.14.10-内核源码注释】内核源码中宏定义理解

内核宏定义1 这是Linux内核中的start_kernel函数的一部分代码。它的作用是初始化内核的一些基本组件和数据结构。 asmlinkage: 这是一个函数声明修饰符&#xff0c;指示编译器把函数参数放在堆栈中&#xff0c;而不是寄存器中。 __visible: 这是另一个函数声明修饰符&#x…
阅读更多...
使用Linux运维常识

使用Linux运维常识

一.基础操作 1.终端常用快捷键 快捷键描述ctrl键盘左键向左跳一个单词ctrl键盘右键向右跳一个单词Ctrl c停止当前正在运行的命令。Ctrl z将当前正在运行的命令放入后台并暂停它的进程。Ctrl d关闭当前终端会话。Ctrl l清屏&#xff0c;也可以用clear命令实现Tab自动补全当…
阅读更多...
文字的显示

文字的显示

文字的显示 文章目录 文字的显示1.文字编码方式2.英文和汉字的点阵显示3.显示中文“中”和“A”show_font.c结果 1.文字编码方式 数字>代表什么->显示为什么 GBK国标拓展 下列代码用不同编码方式保存utf-8.c ansi.c #include <stdio.h>int main(int argc ,char *…
阅读更多...
05-Vue技术栈之使用脚手架

05-Vue技术栈之使用脚手架

1、初始化脚手架 1.1 说明 Vue 脚手架是 Vue 官方提供的标准化开发工具&#xff08;开发平台&#xff09;。最新的版本是 5.x。文档: https://cli.vuejs.org/zh/ 1.2 具体步骤 第一步&#xff08;仅第一次执行&#xff09;&#xff1a;全局安装vue/cli npm install -g vue…
阅读更多...
CSDN竞赛第49期题解

CSDN竞赛第49期题解

第49期比赛页面&#xff1a;第49期编程竞赛 一、 小海豚喜欢打游戏&#xff0c;现在它在操纵游戏人物小C逃脱废弃的隧道&#xff0c;逃生装置在小C的前方 X 米远的位置。但是游戏机只有 两个按钮&#xff1a;前进和后退&#xff0c;按前进&#xff0c;小C会前进 m 米&#xff…
阅读更多...
网络安全之黄金票据，白银票据

网络安全之黄金票据，白银票据

前言&#xff1a;今天来给大家讲讲黄金票据和白银票据Kerberos认证#金票Golden ticket# 原理#伪造金票的场景和所需条件#利用方式#银票SILVER TICKET# 原理#伪造银票所需条件#金票和银票的区别# 获取的权限不同#认证流程不同#加密方式不同# 前言&#xff1a;今天来给大家讲讲黄…
阅读更多...
84.python input输入函数知识拓展

84.python input输入函数知识拓展

文章目录 1. input函数知识回顾2. input常犯错误解析3. 用函数转换从终端输入的数据3.1 输入的数为整数&#xff0c;则用int转换为整数3.2 输入的数为浮点数&#xff0c;则用float转换为浮点数3.3 不考虑输入的数据类型&#xff0c;则用eval函数转换 4. 变量的多种赋值方式4.1 …
阅读更多...
Java中有什么异常机制? 有哪些异常分类? 常见异常的详解以及解决异常思路?

Java中有什么异常机制? 有哪些异常分类? 常见异常的详解以及解决异常思路?

Java中的异常机制是一种处理程序在运行时可能发生的不可预测情况的方式。异常是指在程序执行期间遇到的错误或其他意外事件&#xff0c;它会中断程序的正常执行流程。Java中的异常分为两类&#xff1a;Checked Exception&#xff08;已检查异常&#xff09;和Unchecked Excepti…
阅读更多...
最新文章

Copyright @ 2022~2023