邯郸网站制作地方,代运营电商公司排行榜,行业平台网站建设,wordpress 手机号注册栈和队列 一、栈 概念与特性二、Stack 集合类及模拟实现1、Java集合中的 Stack2、Stack 模拟实现 三、栈、虚拟机栈、栈帧有什么区别#xff1f;四、队列 概念与特性五、Queue集合类及模拟实现1、Queue的底层结构#xff08;1#xff09;顺序结构#xff08;2#xff09;链… 栈和队列 一、栈 概念与特性二、Stack 集合类及模拟实现1、Java集合中的 Stack2、Stack 模拟实现 三、栈、虚拟机栈、栈帧有什么区别四、队列 概念与特性五、Queue集合类及模拟实现1、Queue的底层结构1顺序结构2链式结构 2、Java集合中的 Queue3、Queue 模拟实现 六、设计循环队列1、循环队列涉及的两个关键问题1问题 1 解决方案2问题 2 解决方案 2、循环队列具体实现 七、Deque 集合类 一、栈 概念与特性
一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶另一端称为栈底。栈中的数据元素遵守后进先出 LIFOLast In First Out的原则。 二、Stack 集合类及模拟实现
1、Java集合中的 Stack 在Java集合中 Stack 集合类可以表示栈Stack继承了VectorVector和ArrayList类似都是动态的顺序表因此Stack 底层维护的也是一个动态顺序表。
我们可以先看一下Stack中给出的常用方法
构造方法
方法解释Stack()构造一个空的栈
常用方法
方法功能E push(E e)将元素 e 入栈并返回 eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
2、Stack 模拟实现
有了顺序表和链表的基础栈的实现就非常的简单了下面就直接给出顺序栈的实现代码大家可以参照注释进行理解
public class MyStack {// 数组public int[] elem;// 栈顶public int top;// 构造方法初始化顺序栈public MyStack() {elem new int[5];}//1.压栈E push(E e) //检测容量private boolean isFull() {return top elem.length;}public int push(int e) {if (isFull()) {// 如果栈满就扩容elem Arrays.copyOf(elem,2*elem.length);}elem[top]e;return e;}//2.出栈E pop() public int pop() {// 如果栈空抛异常这里可以自定义实现一个异常类if (empty()) {throw new EmptyException(空栈!);}// 正常出栈return elem[--top];}//3.获取栈顶元素E peek() public int peek() {return elem[top-1];}//4.获取栈中有效元素个数int size() public int size() {return top;}//5.检测栈是否为空boolean empty() public boolean empty() {return top 0;}
}上面实现的 栈 底层是一个动态数组它的入栈和出栈都达到了O(1)。其实栈的底层也可以实现成链表的结构 1 底层为单向链表。 如果底层维护一个单链表那么可以将入栈实现为头插出栈实现为头删这样以来它的时间复杂的也可以达到O(1)。 2底层为双向链表。 对于双向链表来说由于同时记录了head结点和last结点并且每个结点的前后结点都是明确的故无论是在头部使用插入删除模拟入栈出栈还是在尾部实现复杂度都可以达到O(1)。 这一点在Java集合类LinkedList中给出的接口方法中得到了体现它里面就提供了push()、pop()、peek()等方法。
三、栈、虚拟机栈、栈帧有什么区别 栈是一种数据结构用于存储和管理数据。虚拟机栈是JVM在执行Java程序时使用的一块内存区域包含了线程的栈帧。栈帧是虚拟机栈中的一个元素用于存储方法调用的信息。 四、队列 概念与特性
只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 的特点。
进行插入操作的一端称为队尾Tail/Rear进行删除操作的一端称为队头Head/Front 五、Queue集合类及模拟实现
1、Queue的底层结构
众所周知无论是栈也好队列也好它们的本质都是一个容器既然是容器那么底层就有两种结构顺序结构、链式结构。那么队列的底层究竟是用 顺序结构还是链式结构如果使用链式结构那么是使用单向还是双向呢下面我们一起来探讨一下
1顺序结构
我们知道队列的两个关键操作是入队和出队。如果使用顺序结构那么意味着它的底层将维护一个数组此时我们有两种实现方案 方案一 使用数组的头插完成入队使用数组的尾删实现出队方案二 使用数组的尾插完成入队使用数组的头删实现出队 方案一分析使用方案1入队的话使用头插法需要挪动数组元素复杂度为O(N)出队的复杂度可以达到O(1)。
方案二分析使用方案2入队复杂度可达到O(1)而出队由于使用的头删每次需要移动大量的元素复杂度达到了O(N)。所以这两种方案均不能保证入队和出队的复杂度达到O(1)因此不建议采用。但是可通过循环数组解决上述问题后面讲解
2链式结构 方案一使用单向链表。方案二使用双向链表。 方案一分析如果采用方案1使用单向链表我们需要定义两个特殊结点 头结点-head尾结点-last。由于链表是单向的所以如果此时我们采用头插表示入队复杂度可达到O(1)尾删表示出队由于链表是单向的所以还需要找到 last 结点的前一个结点复杂度达到了O(N)。所以需要使用尾插表示入队复杂度可达到O(1)头删表示出队复杂度也可达到O(1).
方案二分析如果采用方案2使用双向链表。由于链表是双向的所以 无论是将头插表示出队尾删表示入队还是尾插表示入队头删表示出队都可以达到复杂度为O(1).
2、Java集合中的 Queue
并且在Java集合中的Queue接口底层实现的就是一个双向链表 下面我们先查看一下Queue接口中一些常见的队列方法
方法功能boolean offer(E e)入队列将元素插入队列尾部E poll()出队列移除并返回队头元素E peek()获取队头元素但不移除int size()获取队列中有效元素的个数boolean isEmpty()检测队列是否为空
3、Queue 模拟实现
同样根据上面给出的队列方法下面就实现一个底层为双向链表的队列大家可以参照上述实现思路和代码注释进行理解
//原理先进先出
//思路双向链表头尾无所谓下面采用[头插、尾删]代替[入队、出队]
public class DQueue {// 定义双向链表节点static class Node {public int val;public Node prev;public Node next;public Node(int val) {this.val val;}}// 头结点public Node head;// 尾结点public Node last;// 队列长度public int size;//1.入队列boolean offer(E e) 【头插】public boolean offer(int e) {Node node new Node(e);// 判空if (isEmpty()) {head node;last node;} else {// 头插node.next head;head.prev node;head head.prev;}size;return true;}//2.出队列E poll() 【尾删】public int poll() {// 判空if (isEmpty()) {// 这里可以自定义异常throw new EmptyException(队列为空!);}// 接收出队元素int ret head.val;// 如果只有1个结点if (head.next null) {last null;head null;} else {// 大于1个结点last.prev.next null;last last.prev;}size--;return ret;}//3.获取队头元素int peek() public int peek() {// 判空if (isEmpty()) {// 这里可以自定义异常throw new EmptyException(队列为空!);}return head.val;}//4.获取队列中有效元素个数int size() public int getSize() {return size;}//5.检测队列是否为空boolean isEmpty() public boolean isEmpty() {return size 0;}
}六、设计循环队列
循环队列通过巧妙地利用数组的循环使用解决了普通队列在头部插入和删除操作时效率低下的问题使得offer()和poll()操作均能够在O(1)的时间复杂度内完成。这种结构经常在 生产者消费者模型敬请期待 中使用。
1、循环队列涉及的两个关键问题
循环队列的设计主要涉及两个关键问题 数组下标如何循环如何判断循环队列的空与满 1问题 1 解决方案
方案一 让 head 和 tail 使用加 1 取模操作。既保证当 head 和 tail 不处于数组尾下标时加 1 取模操作不影响下标正常递增又能保证 head 和 tail 处于数组尾下标时继续 入队 或 出队 下标循环。 方案二 判断 tail 和 head 与 数组长度 nums.length 是否相等相等则置 0 保证下标循环。
2问题 2 解决方案
方案一 设置 usedSize 变量记录队列元素个数。usedSize 为 0 队列为空usedSize 等于数组长度 nums.length 队列为满。 方案二 牺牲 1 个数组元素。当 head 等于 tail 时表示队列为空当 tail 1 等于 head 时表示队列为满。 2、循环队列具体实现
解决了上面两个问题下面的实现就是信手拈来。下面给出具体的实现代码大家可以参照注释理解判空 / 满 这里采用 useSize循环使用 head / tail 与 nums.length 判断
// 规定有效元素为[head,tail)
// 判空判满使用usedSize
// 下标循环使用head / tail 与 nums.length 判断
public class CircularQueue {// 数组private int[] elem;// 队头private int head;// 队尾的下一个private int tail;// 有效元素个数private int usedSize;// 使用构造方法初始化循环队列public CircularQueue(int k) {this.elem new int[k];this.head 0;this.tail 0;this.usedSize 0;}// 1.入队列put()public boolean put(int val) {// 判满if (isFull()) {return false;}// 正常入队情况elem[tail ] val;// 增加有效元素个数usedSize ;// 判断下标if (tail elem.length) {tail 0;}return true;}// 2.出队列take()public int take() {// 判空if (isEmpty()) {throw new EmptyException(队列为空!);}// 正常出队情况int val elem[head ];// 减少有效元素个数usedSize --;// 判断下标if (head elem.length) {head 0;}return val;}// 3.获取队头元素peekHead()public int peekHead() {// 判空if (isEmpty()) {throw new EmptyException(队列为空!);}int val elem[head --];return val;}// 4.获取队尾元素peekTail()public int peekTail() {// 判空if (isEmpty()) {throw new EmptyException(队列为空!);}// 由于 tail 指向最后一个有效元素的下一个所以需要考虑下标边界情况int index tail 0? elem.length -1:tail -1;int val elem[index];return val;}// 5.判空isEmpty()public boolean isEmpty() {return usedSize 0;}// 6.判满isFull()public boolean isFull() {return usedSize elem.length;}// 7.获取队列有效元素个数getSize()public int getSize() {return usedSize;}
}七、Deque 集合类
Deque表示一个双端队列即允许两端都可以进行入队和出队操作的队列。 在Java集合框架中Deque是一个接口它实现了LinkedList和ArrayDeque分别表示双端队列的线性实现 和 双端队列的链式实现。其中线性实现的底层为一个循环数组链式实现的底层为一个双向链表。 在实际工程中使用Deque接口是比较多的Deque接口中涵盖了队列和栈的功能接口实现栈和队列均可以使用该接口
DequeInteger stack1 new ArrayDeque(); // 线性实现
DequeInteger stack2 new LinkedList(); // 链式实现DequeInteger queue1 new ArrayDeque(); // 线性实现
DequeInteger queue2 new LinkedList(); // 链式实现
