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 助解图题

助解图:

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

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

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

助解题:

  • 题一: 一个栈的入栈顺序是 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)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

题解:

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

代码:

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 链接):

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

题解:

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

代码:

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 栈和队列的实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数据结构之栈的详解

    目录 栈的抽象定义 顺序栈-----------使用数组表示栈空间 总结 栈是先进后出的特殊线性表,只允许在表的末端进行插入和删除,后面将介绍两种实现栈的方式,分别是基于数组的实现.基于链表的实现. 栈的抽象定义 class Mystack { public: Mystack() {} virtual void push(int &x) = 0; virtual bool pop(int &x) = 0; virtual bool Top(int &x) const = 0; vi

  • 打印Java程序的线程栈信息方式

    打印Java程序的线程栈信息 jstack可以得知当前线程的运行情况 安装jstack等命令集,jstack是开发版本jdk的一部分,不是开发版的有可能找不到 yum install -y java-1.8.0-openjdk-devel 查看要打印堆栈的java进程ID jps -l 打印堆栈 sudo -u admin jstack pid > jstack.txt 特别要注意的是jstack需要使用与进程一致的用户才能正确导出堆栈,否则会报错如下 Unable to open socket

  • java数据结构基础:循环链表和栈

    目录 循环链表: 实现思路: 代码实现: 栈: 实现思路: 代码实现: 总结 循环链表: 与单链表的最后一个节点的指针域为null不同,循环链表的最后一个节点的指针指向头结点 实现思路: 初始化时将头结点指向自身,添加节点到链表末尾时,将新节点的指针指向头结点 在遍历链表时,判断是否遍历到链表末尾,需要判断当前指针的下一个节点是否为头结点 代码实现: 节点类CircleNode: public class CircleNode { public int data; public CircleNo

  • java虚拟机中栈的运行知识点总结

    运行原理 1.不同线程中所包含的栈帧是不允许存在相互引用的. 2.如果当前方法调用了其他方法,方法返回之际,当前栈帧会传回此方法的执行结果给当前一个栈针,并且虚拟机会丢弃当前栈帧,使得前一个栈帧重新成为当前栈帧. 3.Java方法有两种返回函数的方式,一种是正常的函数返回,使用return指令:另一种是抛出异常.不管使用哪种方式,都会导致栈帧被弹出. 实例 public class StackFrameTest { public static void main(String[] args) {

  • java数据结构基础:栈

    目录 准备工作 编码环节 push方法 pop方法 empty方法 全部代码 总结 准备工作 工具:idea+jdk8 技术要求:java基础语法 编码环节 首先,我们得先确定下来,用什么数据来模拟栈的操作.由于是一个一个的元素放入栈里面,我们可以考虑用数组来实现. 以上是Java官方文档中的栈定义,我们也只需要实现三个方法:判断是否为空.移除栈顶对象.添加元素到栈的尾部 所以我们事先得定义一个数组: Objects[] arr; 数组定义好了之后呢,想想,我们怎么去获取到栈尾部或者栈首的元素呢

  • 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 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • Java数据结构与算法之栈(动力节点Java学院整理)

    stack,中文翻译为堆栈,其实指的是栈,heap,堆.这里讲的是数据结构的栈,不是内存分配里面的堆和栈. 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的. 队列就是排队买苹果,先去的那个可以先买. 栈 public class Stack { private int array[]; private int max; private int top; public Stack(int max){ this.max = max; array = new int[m

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • 带你了解Java数据结构和算法之栈

    目录 1.栈的基本概念 2.Java模拟简单的顺序栈实现 3.增强功能版栈 4.利用栈实现字符串逆序 5.利用栈判断分隔符是否匹配 6.总结 1.栈的基本概念 栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表.它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来).栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针. 栈是允许在同一端进行插入和删除操

  • Swift算法之栈和队列的实现方法示例

    一.概述 栈和队列在数据结构中是比较重要的一个数据结构. 其实对于栈和队列并不需要太深入的介绍,栈和队列的核心内容是栈是先进后出.队列是先进先出.在实际开发中有些场景也可能会用到,比如 APP 中用户可以撤销操作,比如下棋 APP 中的悔棋操作,返回上一步就是先进后出(后进先出),也就是栈的特性. 比如在售票 APP 中,为先下订单的用户先出票,就需要用到队列.当然这两个只是在简单场景下的情况,实际开发中情况可能更复杂,比如售票 APP 为会员用户优先出票等. 接下来就通过 Swift 去实现栈

随机推荐