数据结构栈和队列详解（java中的栈和队列）

1. 栈

1.1 概念

栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
特点：栈中的数据元素遵循先进后出的原则，但要注意进的同时也可以出，元素不是要全部进展后才能出栈
栈顶：进行数据插入和删除操作的一端
栈底：栈顶的另一端
压栈：栈的插入操作就做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作就叫做出栈，出数据在栈顶

1.2 助解图题

助解图：

手枪的弹夹其实就类似是一个栈

数据结构栈和队列详解（java中的栈和队列）

当我们压子弹的时候，就是压栈

数据结构栈和队列详解（java中的栈和队列）

当我们上膛后，打枪时，就是出栈

数据结构栈和队列详解（java中的栈和队列）

助解题：

题一：一个栈的入栈顺序是 a、b、c、d、e，该栈不可能的出栈顺序是（） A.edcba B.decba C.dceab D.abcde

结果为：C

题二：中缀表达式为 a + b * c + ( d * e + f ) * g，那么它的后缀表达式为什么？

结果为：a b c * + d e * f + g * +

方法步骤（快捷方法）：

数据结构栈和队列详解（java中的栈和队列）

该方法中将括号的运算符移到括号前面得到的结果就是前缀表达式

本题背景：我们平常使用的表达式一般为中缀表达式，中缀表达式便于人们的理解与计算。而后缀表达式的运算符更方便计算机的运算（如二叉树、堆栈的方法计算）

题三：通过栈返回后缀表达式 a b c * + d e * f + g * + 计算的结果

结果为：a + b * c + ( d * e + f ) * g

方法：当参数是数字时就压栈。当参数为运算符时，出栈第一个数作为运算符后的参数，出栈第二个参数作为运算符前的参数，将结果再压入栈中。

1.3 栈的数组实现

在 Java 中栈的底层其实是一个数组，并且它拥有压栈、出栈等等方法，借助这些我们来自己实现一个栈

public class MyStack{ // 定义一个整型的数组，也可以直接使用泛型 public int[] elem; // 定义数组已经使用的长度，初始时为0 public int usedSize; // 创建 MyStack 的构造方法 public MyStack(){ // 用 Mystack 创建对象时初始化数组的长度为10 this.elem=new int[10]; } // 判断栈是否已满 public boolean isFull(){ return usedSize==this.elem.length; } // 压栈 public int push(int val){ if(isFull()){ // 扩容 this.elem=Arrays.copyOf(this.elem,2*this.elem.length); } this.elem[this.usedSize++]=val; return val; } // 出栈 public int pop(){ if(empty()){ throw new RuntimeException("栈为空"); } this.usedSize--; return this.elem[this.usedSize]; } // 查看栈顶元素，不删除 public int peek(){ if(empty()){ throw new RuntimeException("栈为空"); } return this.elem[this.usedSize-1]; } // 判断栈是否为空 public boolean empty(){ return usedSize==0; } }

1.4 问题

我们上述的栈是用数组实现的，入栈和出栈的时间复杂度都为 O(1)

那么栈能否用单链表实现呢？

使用头插法：入栈时间复杂度为 O(1)，出栈时间复杂度为 O(1)
使用尾插法：入栈时间复杂度为 O(N)，出栈时间复杂度为 O(N)

综上分析，栈可以通过单链表的头插头删法实现

1.5 栈的单链表实现

接下来将使用单链表实现栈，注意要使用头插头删法

class Node{ public int val; public Node next; public Node(int val){ this.val=val; } } public class MyStack{ Node head=null; // 压栈 public int push(int val){ Node node=new Node(val); node.next = head; head = node; return head.val; } // 出栈 public int pop(){ if(empty()){ throw new RuntimeException("栈为空"); } int val=head.val; head=head.next; return val; } // 查看栈顶元素，不删除 public int peek(){ if(empty()){ throw new RuntimeException("栈为空"); } return head.val; } // 判断栈是否为空 public boolean empty(){ return head==null; } }

2. 队列

2.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表。
特点：队列具有先进先出的特点
对头：进行删除操作的一端
队尾：进行插入操作的一段

数据结构栈和队列详解（java中的栈和队列）

2.2 问题

在我们实现队列前，要思考队列是靠数组实现呢还是拿链表实现呢？

在 Java 当中，队列是由 LinkedList 实现的，它的底层是一个双向链表。

对于双向链表：我们只要在尾节点进行入队操作，在头节点进行出队操作就很容易实现
对于单链表：我们只要增加一个尾巴节点，然后尾巴节点进行入队操作，头节点进行出队操作也能实现

至于数组，我们上述通过它实现了栈，而栈的特点其实是先进后出，与队列的先进先出原则矛盾。使用数组来实现队列会很麻烦。

2.3 队列的单链表实现

根据 Java 中队列的一些方法，接下来我们来实现自己的队列

class Node{ public int val; public Node next; public Node(int val){ this.val=val; } } public class MyQueueLinked { private Node front; private Node rear; private int usedSize; // 入队列 public void offer(int val){ Node node=new Node(val); if(this.front==null){ this.front=node; this.rear=node; }else{ this.rear.next=node; this.rear=node; } this.usedSize++; } // 出队列 public int poll(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } int val=this.front.val; if(this.front.next==null){ this.front=null; this.rear=null; }else{ this.front=this.front.next; } this.usedSize--; return val; } // 得到队头元素不删除 public int peek(){ if(isEmpty()){ throw new RuntimeException("队列为空"); }else{ return this.front.val; } } // 判断队列是否为空 public boolean isEmpty(){ return this.usedSize==0; } // 得到队列长度 public int size(){ return this.usedSize; } }

上述队列是用单链表实现的，也叫链式队列。大家也可以自行尝试一下双链表实现队列。

2.4 数组实现队列

假设现在我们用数组模拟入队列和出队列的模型

数据结构栈和队列详解（java中的栈和队列）

解决方法：

方法一：出队时，移动数组将后面的元素往前覆盖（时间复杂度为 O(N)）
方法二：使用循环的方法，实现循环队列（时间复杂度为 O(1)）

2.5 循环队列

循环队列即数组使用了循环的方式，让数组方便队列的入队和出队。那么怎么实现呢？模型如下

数据结构栈和队列详解（java中的栈和队列）

front：指向的位置就是队列的头，既已经存放数据的第一个下标（删除数据一端）
rear：指向的位置就是队列的尾巴，即可以存放数据的第一个下标（插入数据一端）

问题1：如何判断 front = rear 时是空还是满？

为了能够区别是空还是满，我们常假定当 front = rear 时为空。而对于满的话，我们则会将这个数组保留一个空的位置，那么当 rear+1 = front 时，则队列满了

数据结构栈和队列详解（java中的栈和队列）

问题2：当 front 在数组最后一个位置时，如何再移它到数组的第一个位置呢？

(下标+1)%数组长度

接下来让我们实现循环队列

public class MyCircularQueue { private int[] elem; private int front; private int rear; public MyCircularQueue(int k){ this.elem=new int[k+1]; } // 判断队列是否满了 public boolean isFull(){ return (this.rear+1)%this.elem.length==this.front; } // 判断队列是否为空 public boolean isEmpty(){ return this.front==this.rear; } // 入队 public void enQueue(int val){ if(isFull()){ this.elem= Arrays.copyOf(this.elem,2*this.elem.length); } this.elem[this.rear]=val; this.rear=(this.rear+1)%this.elem.length; } // 出队 public int deQueue(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } int val=this.elem[this.front]; this.front=(this.front+1)%this.elem.length; return val; } // 得到队头元素 public int getFront(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return this.elem[this.front]; } // 得到队尾元素 public int getRear(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } if(this.rear==0){ return this.elem[this.elem.length-1]; } return this.elem[this.rear - 1]; } }

注意：

假设一个数组长度为3，做题时可能人家用例入队了3次，但是按照上述队列为满的方式，我们其实是保留了一个位置是不能存放数据的。因此对于这种题目我们可以将我们的数组开大一位

2.6 双端队列

双端队列：是指允许两端都可以进行入队和出队操作的队列
特点：元素可以从队头出队和入队，也可以从队尾出队和入队

双端队列较简单，可以使用双向链表实现，这里就展示一下双端队列的模型

数据结构栈和队列详解（java中的栈和队列）

到此这篇关于Java数据结构专题解析之栈和队列的实现的文章就介绍到这了,更多相关Java 栈和队列的实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/weixin_51367845/article/details/120931373

如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）

关于作者：访客

数据结构栈和队列详解（java中的栈和队列）

1. 栈

1.1 概念

1.2 助解图题

1.3 栈的数组实现

1.4 问题

1.5 栈的单链表实现

2. 队列

2.1 概念

2.2 问题

2.3 队列的单链表实现

2.4 数组实现队列

2.5 循环队列

2.6 双端队列

3. 栈和队列练习题

3.1 有效的括号

3.2 用队列实现栈

3.3 用栈实现队列

3.4 实现一个最小栈

3.5 设计循环队列

发表评论取消回复

业务办理

运营商合作

1. 栈

1.1 概念

1.2 助解图题

1.3 栈的数组实现

1.4 问题

1.5 栈的单链表实现

2. 队列

2.1 概念

2.2 问题

2.3 队列的单链表实现

2.4 数组实现队列

2.5 循环队列

2.6 双端队列

3. 栈和队列练习题

3.1 有效的括号

3.2 用队列实现栈

3.3 用栈实现队列

3.4 实现一个最小栈

3.5 设计循环队列

为您推荐：

发表评论 取消回复

业务办理

运营商合作

发表评论取消回复