数据结构 - 4(栈和队列6000字详解)

2023-10-15 01:36

本文主要是介绍数据结构 - 4(栈和队列6000字详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一:栈

1.1 栈的概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

  • 压栈(push):栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
  • 出栈(pop):栈的删除操作叫做出栈。出数据在栈顶。

在这里插入图片描述
在这里插入图片描述

栈这种结构在现实生活中也很常见:
在这里插入图片描述
在这里插入图片描述

1.2 栈的使用

方法功能
Stack()构造一个空的栈
E push(E e)将e入栈,并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空

下面是这些方法的使用示例:

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());  // 获取栈中有效元素个数---> 4System.out.println(s.peek());  // 获取栈顶元素---> 4s.pop();  // 4出栈,栈中剩余1  2  3,栈顶元素为3System.out.println(s.pop());  // 3出栈,栈中剩余1 2  栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}}

1.3栈的模拟实现

在这里插入图片描述
从上图中可以看到,Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的。

public class MyStack {int[] array;  // 数组用于存储栈元素int size; // 记录栈中元素的个数// 构造方法,创建一个初始容量为3的数组作为栈的存储空间public MyStack(){array = new int[3];}// 入栈操作,将元素 e 加入到栈顶,并返回入栈的元素public int push(int e){ensureCapacity();// 确保栈的容量足够array[size++] = e;// 将元素 e 加入到数组中,更新 size 的值return e;// 返回入栈的元素}// 出栈操作,将栈顶元素移出并返回该元素public int pop(){int e = peek(); // 调用 peek 方法获取栈顶元素,并记录在变量 e 中size--; // 栈中元素个数减少1return e;// 返回出栈的元素}// 返回栈顶元素的值,但不删除栈顶元素public int peek(){if(empty()){ // 如果栈为空,则抛出异常throw new RuntimeException("栈为空,无法获取栈顶元素");}return array[size-1];// 返回栈顶元素的值}// 返回栈中元素的个数public int size(){return size;}// 判断栈是否为空public boolean empty(){return 0 == size;}// 确保栈的容量足够,如果栈已满,则将栈的容量扩大为原来的2倍private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

二:队列

2.1 队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)

在这里插入图片描述

2.2 队列的使用

在Java中,Queue是个接口,底层是通过链表实现的。
在这里插入图片描述
下面是队列中常用的方法:

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

注意:

  • Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

下面是这些方法的使用示例:

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());}
}

2.3队列的模拟实现

队列中既然可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构 和 链式结构。所以队列的实现也可以采用这两种方式,但是具体采用哪种实现方式取决于具体的需求和场景。

  1. 顺序结构:使用数组或列表等连续的内存空间来存储队列元素。顺序结构实现队列的优点是简单、易于理解和实现,并且访问元素的时间复杂度为 O(1)。缺点是在插入和删除操作时可能需要进行元素的搬移,这会造成时间复杂度为 O(n)。

  2. 链式结构:使用链表的形式来存储队列元素。链式结构实现队列的优点是插入和删除操作的时间复杂度为 O(1),无需进行元素的搬移。缺点是需要额外的指针来维护节点之间的连接,且节点的分配和释放可能会引起额外的内存开销和碎片问题。

所以说如果你以访问为主,那么采用顺序结构,如果你以插入和删除为主,那么采用链式结构

在这里插入图片描述

2.3.1顺序结构实现队列

因为我以及在代码中通过注释进行了详细的解答,在此就不过多赘述了。

public class Queue {private int capacity;           // 队列的容量private int[] elements;         // 存储队列元素的数组private int front;              // 队列的头指针private int rear;               // 队列的尾指针private int size;               // 队列的当前大小// 队列的构造方法public Queue(int capacity) {this.capacity = capacity;this.elements = new int[capacity];this.front = 0;this.rear = -1;this.size = 0;}// 入队列---向队尾插入新元素public void offer(int element) {// 检查队列是否已满if (size == capacity) {throw new IllegalStateException("Queue is full");}// 队尾指针移动到下一个位置rear = (rear + 1) % capacity;// 将新元素插入队尾elements[rear] = element;// 队列大小加1size++;}// 出队列---将队头元素删除并返回public int poll() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 获取队头元素int element = elements[front];// 队头指针移动到下一个位置front = (front + 1) % capacity;// 队列大小减1size--;// 返回队头元素return element;}// 获取队头元素---返回队头元素的值,但不删除public int peek() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 返回队头元素return elements[front];}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}
}

2.3.2链式结构实现队列

public class Queue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;// 双向链表节点的构造方法ListNode(int value){this.value = value;}}ListNode first;  // 队头ListNode last;   // 队尾int size = 0;// 入队列---向双向链表尾部插入新节点public void offer(int e){ListNode newNode = new ListNode(e);if (first == null) {// 如果队列为空,新节点同时成为队头和队尾first = newNode;} else {// 如果队列不为空,将新节点插入到队尾last.next = newNode;newNode.prev = last;}// 更新队尾为新节点last = newNode;// 队列大小加1size++;}// 出队列---将双向链表第一个节点删除public int poll(){// 队列为空,返回nullif (first == null) {return null;} else if (first == last) {// 队列中只有一个元素,将队头和队尾设置为null即可last = null;first = null;} else {// 队列中有多个元素,将第一个节点删除int value = first.value;first = first.next;// 删除节点的引用关系,避免内存泄漏first.prev.next = null;first.prev = null;return value;}// 队列大小减1--size;// 返回删除的值return value;}// 获取队头元素---获取双向链表的第一个节点的值public int peek(){// 如果队列为空,返回nullif (first == null) {return null;}// 返回队头的值return first.value;}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty(){return first == null;}
}

2.4 循环队列

2.4.1索引公式

循环队列的视图如下:

在这里插入图片描述

我们该如何去实现一个循环队列呢?答案是通过 %取模

举个例子:

int a = b % 7

在这个例子中,我们不管b取何值,a的取值返回是不是始终在0到6之间,所以我们通过这个性质就可以很好的把队列的首和尾建立关联,即尾向后走一步就到了头,因此我们就可以很好的去实现一个循环队列了

在循环队列中,(index + offset) % array.length(index + array.length - offset) % array.length 是我们常用的索引计算方式。其中:

  • index 是当前元素的索引。
  • offset 是偏移量,它决定了要添加/访问的元素在当前索引的基础上偏移了多少个位置。
  • array.length 是数组的长度,它表示整个循环队列的大小。

下面我们对这两个公式进行解释:

  1. (index + offset) % array.length
    • 当我们需要向循环队列的下一个位置插入元素时,我们使用这种索引计算方式。
    • 假设队列在索引5处结束,我们需要向后移动1个位置,即在索引7处插入元素。使用 (5 + 1) % 8,得到的值是6,即有效的索引。

在这里插入图片描述

  1. (index + array.length - offset) % array.length
    • 当我们需要从循环队列的上一个位置移除元素时,我们使用这种索引计算方式。
    • 假设队列在索引2处结束,我们需要向前移动1个位置,即从索引1处移除元素。使用 (2 + 8 - 1) % 8,得到的值是1,即有效的索引。

在这里插入图片描述

这两种计算方式都确保了索引在循环队列中的有效范围内,因为它们会通过取模运算将索引限制在数组长度范围内。这样,我们可以在循环队列中正确地插入和移除元素。

2.4.2 队列区分空和满

当我们使用一个固定大小的数组作为队列的底层数据结构。在循环队列中,我们使用两个指针,一个指向队列的头部,即出队列的位置,另一个指向队列的尾部,即入队列的位置。

当队列为空时,这两个指针指向同一个位置,即头部与尾部指针相等。而当队列满时,尾部指针的下一个位置就是头部指针所在的位置。

那么我们该怎么区分队列是空还是满呢?

为了区分队列是空还是满,我们可以采用三种常用的方法:

  1. 使用 size 属性记录:

通过添加一个 size 属性来记录队列中的元素数量,可以方便地判断队列是空还是满。当队列为空时,size 的值为 0,当队列满时,size 的值等于队列的容量。

  1. 保留一个位置:

在循环队列的实现中,可以将一个位置始终空置不用,用于区分队列是空还是满。例如,当队列为空时,头部指针和尾部指针都指向同一个位置;当队列满时,尾部指针的下一个位置就是头部指针所在的位置。通过查看这个空置位置是否为空,可以判断队列是空还是满。

  1. 使用标记:

可以在循环队列中使用一个额外的标记来区分队列是空还是满。这个标记可以是一个布尔值或者一个特殊的值,用于表示队列的状态。例如,当队列为空时,可以将标记设置为 true;当队列满时,可以将标记设置为 false。通过判断标记的值,可以确定队列的状态。

这些方法都可以用于区分队列是空还是满,具体选择哪种方法取决于个人偏好和实际需求。

2.5 Deque双端队列

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。

在这里插入图片描述
Deque是一个接口,使用时必须创建LinkedList的对象。
在这里插入图片描述
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

这篇关于数据结构 - 4(栈和队列6000字详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/214516

相关文章

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab