首页 > 资讯 > 后端开发 > Python >Java数据结构专题解析之栈和队列的实现

534

分享到

Java数据结构专题解析之栈和队列的实现

2024-04-02 19:04:59 534人浏览八月长安

Python 官方文档：入门教程 => 点击学习

摘要

目录1. 栈1.1 概念1.2 助解图题1.3 栈的数组实现1.4 问题1.5 栈的单链表实现2. 队列2.1 概念2.2 问题2.3 队列的单链表实现2.4 数组实现队列2.5 循

1. 栈

1.1 概念

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

1.2 助解图题

助解图：

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

助解题：

题一：一个栈的入栈顺序是 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 * +

方法步骤（快捷方法）：

在这里插入图片描述

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

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

题三：通过栈返回后缀表达式 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 概念

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

在这里插入图片描述

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 数组实现队列

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

在这里插入图片描述

解决方法：

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

2.5 循环队列

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

在这里插入图片描述

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

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

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

在这里插入图片描述

问题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 双端队列

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

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

在这里插入图片描述

3. 栈和队列练习题

3.1 有效的括号

题目（OJ 链接）：

给定一个只包括 ‘('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

题解：使用栈，遍历字符串，是左括号就进行入栈，是右括号就与栈顶元素比较。


public boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char ch=s.charAt(i);
        switch(ch){
            case ')':
                if(stack.empty()||stack.pop()!='('){
                    return false;
                }
                break;
            case '}':
                if(stack.empty()||stack.pop()!='{'){
                    return false;
                }
                break;
            case ']':
                if(stack.empty()||stack.pop()!='['){
                    return false;
                }
                break;
            default:
                stack.push(ch);
                break;
        }
    }
    if(stack.empty()){
        return true;
    }
    return false;
}

3.2 用队列实现栈

题目（OJ链接）：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

题解：

由于队列是先进先出，栈是先进后出，故一个队列无法满足实现栈的能力。而使用两个队列，对于入栈，我们我只要找到栈不为空的队列进行入队就行；对于出栈，我们只要将不为空的队列的除最后一个入队的元素全部转移到另一个空队列中，再将留下的元素出队

代码：


class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    public MyStack() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }
    // 入栈
    public void push(int x) {
        if(!q1.isEmpty()){
            q1.offer(x);
        }else if(!q2.isEmpty()){
            q2.offer(x);
        }else{
            q1.offer(x);
        }
    }
    // 出栈
    public int pop() {
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                if(!q1.isEmpty()){
                    q2.offer(val1);
                }
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                if(!q2.isEmpty()){
                    q1.offer(val2);
                }
            }
            return val2;
        }
    }
    // 得到栈顶元素不删除
    public int top() {
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                q2.offer(val1);
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                q1.offer(val2);
            }
            return val2;
        }
    }
    // 判断栈是否为空
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

3.3 用栈实现队列

题目（OJ 链接）：

请你仅使用两个栈实现先入先出队列。

题解：

我们可以创建两个栈 s1、s2，s1 用来入队，s2 用来出队

代码：


class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    // 入队
    public void push(int x) {
        s1.push(x);
    }
    // 出队
    public int pop() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    // 返回队首元素，不删除
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    // 判断队列是否为空
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

3.4 实现一个最小栈

题目（OJ 链接）：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

题解：

我们可以创建两个栈，一个栈就是用来存储删除元素，另一个就是专门用来存储最小值的栈。注意这个最小值是存储该元素时该栈的最小值

代码：


class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    // 入栈
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }
    // 出栈
    public void pop() {
        int val=stack.pop();
        if(minStack.peek()==val){
            minStack.pop();
        }
    }
    // 得到栈顶元素，不删除
    public int top() {
        return stack.peek();
    }
    // 得到此时栈的最小值
    public int getMin() {
        return minStack.peek();
    }
}

3.5 设计循环队列

题目（OJ 链接）：

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

题解：

通过 (下标+1)%数组长度 的方式将数组形成一个循环，先设定好数组为空和为满的条件。注意防止题目将数组存满，开数组时的大小要注意。

代码：


class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elem=new int[k+1];
    }
    // 入队列
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.elem[rear]=value;
        this.rear=(this.rear+1)%this.elem.length;
        return true;
    }
    // 出队列
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.elem.length;
        return true;
    }
    // 得到队首元素，不删除
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.elem[front];
    }
    // 得到队尾元素，不删除
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear-1];
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return this.rear==this.front;
    }
    // 判断队列是否满了
    public boolean isFull() {
        return (this.rear+1)%this.elem.length==this.front;
    }
}

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

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: Java数据结构专题解析之栈和队列的实现

本文链接: https://www.lsjlt.com/news/155336.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

Java数据结构专题解析之栈和队列的实现

目录1. 栈1.1 概念1.2 助解图题1.3 栈的数组实现1.4 问题1.5 栈的单链表实现2. 队列2.1 概念2.2 问题2.3 队列的单链表实现2.4 数组实现队列2.5 循...

99+

2022-11-12
Java数据结构学习之栈和队列

目录一、栈1.1 概述1.1.1 线性表的概念1.1.2 栈的概念1.1.3 栈的应用二、队列2.1 队列的概念2.2 队列的实现2.3 队列的应用一、栈 1.1 概述 Java为什...

99+

2022-11-12
Java数据结构之栈与队列实例详解

目录一，栈1，概念2，栈的操作3，栈的实现 4，实现mystack二，队列1，概念 2，队列的实现 3，实现myqueue栈、队列与数组的区别？总结一，栈 1，概念在我们软件应用...

99+

2022-11-12
数据结构TypeScript之栈和队列详解

目录栈结构特点出栈和入栈面向对象方法封装栈队列结构特点出队和入队面向对象方法封装队列栈结构特点栈是线性表的其中一种，用于存储固定顺序的元素，元素增删具有先进后出的特点。出栈和入...

99+

2023-01-30

TypeScript数据结构栈队列 TypeScript数据结构
Javascript数据结构之栈和队列详解

目录前言栈（stack）栈实现解决实际问题栈的另外应用简单队列（Queue）队列实现队列应用 - 树的广度优先搜索（breadth-first search，BFS）优先队列优先队列...

99+

2022-11-13
Javascript数据结构之栈和队列怎么实现

本篇内容主要讲解“Javascript数据结构之栈和队列怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Javascript数据结构之栈和队列怎么实现”吧!栈（stack）栈是一种具有「...

99+

2023-06-30
Java深入了解数据结构之栈与队列的详解

目录一，栈1，概念2，栈的操作3，栈的实现①入栈②出栈③获取栈顶元素④判断栈是否为空 4，实现mystack二，队列1，概念2，队列的实现①入队②出队③获取队首元素3，实现...

99+

2022-11-13
如何在java数据结构中实现栈和队列

这期内容当中小编将会给大家带来有关如何在java数据结构中实现栈和队列，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。java 数据结构中栈和队列的实例详解栈和队列是两种重要的线性数据结构，都是在一个特定的...

99+

2023-05-31

java ava
C语言数据结构进阶之栈和队列的实现

目录栈的实现：一、栈的概念和性质二、栈的实现思路三、栈的相关变量内存布局图四、栈的初始化和销毁五、栈的接口实现：1.入栈2.出栈3.获取栈顶的数据4.获取栈的元素个数5.判断栈是否为...

99+

2022-11-12
java数据结构之队列的入队和出队

用java实现队列的入队出队首先要定义几个变量与数组：a：表示队列的数组（推荐学习：java课程）rear：表示队列尾，这里初始化为0（入队一个元素下标就往后移动一位）front：表示队列头，同样初始化为0（出队一...

99+

2016-04-08

java教程 java
Python数据结构之栈、队列的实现代码分享

1. 栈栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放...

99+

2022-06-04

数据结构队列代码
C++数据结构的栈与队列实例分析

今天小编给大家分享一下C++数据结构的栈与队列实例分析的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。1. 栈1.1 栈的概念...

99+

2023-06-30
怎么分析Java数据结构中的栈与队列

今天就跟大家聊聊有关怎么分析Java数据结构中的栈与队列，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。一，栈1，概念在我们软件应用，栈这种后进先出数据结构的应用是非常普遍的。比如你...

99+

2023-06-29
c语言数据结构之栈和队列详解(Stack&Queue)

目录简介栈一、栈的基本概念1、栈的定义2、栈的常见基本操作二、栈的顺序存储结构1、栈的顺序存储2、顺序栈的基本算法3、共享栈（两栈共享空间）三、栈的链式存储结构1、链栈2、链栈的基本...

99+

2022-11-13
C语言数据结构之栈与队列的相互实现

目录一、用对列实现栈代码实现二、用栈实现队列代码实现一、用对列实现栈题干要求：细节分析：队列是先进先出；要实现的栈是先进后出。解题思路：假设：先用一个队列储存数据 N 个，...

99+

2022-11-13
Java队列数据结构的实现

1.队列的基本概念什么是队列队列是一种特殊的线性表它只允许在表的前端（队头）进行删除操作在表的后端（队尾）进行插入操作队列是一个有序表(可以用数组或链表实现)队列先进先出队列开辟...

99+

2022-11-12
Python 数据结构之队列的实现

Python 队列 Queue 队列是一种先进先出(FIFO)的数据类型, 新的元素通过入队的方式添加进 Queue 的末尾, 出队就是从 Queue 的头部删除元素. 用列表来做 Queue: ...

99+

2022-06-04

数据结构队列 Python
Java数据结构之堆(优先队列)的实现

堆（优先队列）是一种典型的数据结构，其形状是一棵完全二叉树，一般用于求解topk问题。根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点，可分为大顶堆和小顶堆，本文实现大顶堆。 ...

99+

2022-11-13
Java数据结构之优先级队列实例分析

本文小编为大家详细介绍“Java数据结构之优先级队列实例分析”，内容详细，步骤清晰，细节处理妥当，希望这篇“Java数据结构之优先级队列实例分析”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。一、堆的概念堆的定义：...

99+

2023-06-29
java实现队列queue数据结构详解

目录概念队列中两个主要操作队列遵循以下条件：队列的数组实现总结概念队列是一种非原始（特殊）的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操...

99+

2022-11-13