Java笔记14——栈和队列

目录

1. 栈(Stack)

1.1 概念

栈的实现

快速生成栈:JDK中的栈叫 Stack

栈的实现完整代码:

力扣关于栈的两道练习题:

2. 队列(Queue)

2.1 概念

队列实现

用JKD生成队列

 ​编辑

 实现队列的完整队列

力扣关于队列的练习题:

2.3 循环队列

循环队列实现

力扣循环队列练习题

双端队列 (Deque)

双端队列的使用


1. 栈(Stack)

1.1 概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

       进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据在栈顶。

 

 栈的特点:

 添加元素只能从栈顶添加

 取出元素也只能从栈顶取出

最先添加的元素就在当前栈的最底端,最后添加的元素就在栈的最顶端。

从栈中取出元素的顺序和从栈中添加的元素的顺序恰好相反~~
 

先进后出,后进先出的线性表

之前学的线性表:

栈在现实生活中的应用(无处不在的栈的应用)

1.无处不在的undo(撤销)操作
在任何一个编辑器中输错了一个内容使用ctrl +z就返回到了上一次输入的内容

在浏览器上浏览网页时,左上角有返回上一次的这个操作。

这些都是栈这个结构的应用。 

2. 操作系统栈:程序在执行过程中,从A函数调用B函数,从B函数调用C函数,返回执行时.如何得知从哪开始继续执行呢,其实背后就是栈这个结构~~

栈的实现

基于数组实现的栈–顺序栈

基于链表实现的栈–链式栈
 

注释:栈只能在栈顶插入元素,在栈顶删除元素的结构

最适合的就是基于动态数组实现的顺序栈,把一个动态数组90°翻转过来看

数组末尾插入和删除元素,数组末尾就是此时的栈顶!!

 不管是基于哪种实现的栈都必须满足三个核心操作:

实现代码:

1.

2.

 3.

4.isEmpty是自定义方法,判断当前栈是否为空的,所以需要去写一个。

 5.

注释: 这个栈的实现其实跟我们之前写的动态数组差不多,只不过它更加的严格罢了,只能从尾部添加和删除等等。

6.最后实现toString方法打印,并且用我们刚学的StringBuilder方法

虽然栈实现起来非常简单,但是栈的应用非常广泛,而且有很多问题其实栈只是作为辅助结构解决。

快速生成栈:JDK中的栈叫 Stack

头文件:

 比如说生成一个保存字符的栈:

栈的实现完整代码:

package seqlist.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 *  基于动态数组实现的顺序栈
 */
public class MyStack<E> {
    //记录当前元素个数
    private int size;
    //实际储存数据的动态数组,此时在栈中只能在数组末尾添加和删除元素
    private List<E> data = new ArrayList<>();

    /**
     * 向当前栈中添加元素 -> 压栈操作
     */
    public void push(E val){
        this.data.add(val);
        size ++;
    }

    /**
     * 弹出当前的栈顶元素,返回栈顶元素的值
     */
    public E pop(){
        //其实就是动态数组的尾删,但需要先判断是否为空
        if(isEmpty()){
            // 栈为空无法弹出,弄个异常
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //数组末尾删除元素
        E rep = data.remove(size - 1);
        size --;
        return rep;
    }

    //判断当前栈是否为空
    private boolean isEmpty() {
        return size == 0;
    }

    /**
     * 查看当前栈顶元素值,不弹出该元素
     */
    public E peck(){
        if(isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek");
        }
        return data.get(size - 1);
    }

    @Override
    public String toString() {
      StringBuilder sb = new StringBuilder();
      sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if(i != size - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();//最后把sb转换为字符串,并返回
    }
}

力扣关于栈的两道练习题:

20. 有效的括号 – 力扣(LeetCode)

155. 最小栈 – 力扣(LeetCode)

2. 队列(Queue)

2.1 概念

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

其实栈和队列是—码事,都是对只能在线性表的一端进行插入和删除。因此,其实栈和队列可以相互转换~~~

 现实生活中:各式各样的”排队”操作
 

同样的,队列也有基于数组实现的队列和基于链表实现的队列:

顺序队列

链表队列
 

刚刚讲过,栈用动态数组实现比较好。可队列呢?想想队列的头删除情况

如果是数组的话要怎么删?数组后面的所有元素都要往前移动一位,效率是不是太低了?

而如果是链表的话就很简单了,head = head.next ,然后再切断下原来头的连接就完成了。

队列实现

1. 这是父类接口,我们接下来要实现各种不一样的子类

 2.1 在同级包下创建一个impl的包,里面放的都是子类实现

注释:上面的Node应该写成 Node<E>

加深理解: 

2.2

2.3  覆写实现父类的抽象方法

 2.4

接下来就是实现里面个个抽象方法的过程了,跟我们之前实现链表差不多,之前链表里面保存的是int,Node。 现在学了泛型,可以是任意类型了,所以是 Node<E> 

1. 添加元素,跟栈的push一样

 2.

 3.

4.

 5.

队列的核心思路就是 尾插,头删。 

 测试:记得要向上转型

 运行结果:

用JKD生成队列

在JDK中队列也叫 Queue,子类有 LinkedList 等等之类的

比如:生成一个保存int的普通队列

 

 里面还有好多别的:  

 注释:是需要导入类的

 实现队列的完整队列

package seqlist.queue.impl;

import seqlist.queue.Queue;

import java.util.NoSuchElementException;

/**
 * 基于链表实现的普通队列
 */

class Node<E>{
    E val;//保存元素的值
    Node<E> next;//保存下一个的地址

    public Node(E val) {
        this.val = val;
    }
}

public class LinkedQueue<E> implements Queue<E> {
    //当前队列中的元素个数
    private int size;
    //当前队列的对首元素
    private Node<E> head;
    //当前队列的尾部元素
    private Node<E> tail;

    @Override
    public void offer(E val) {
        //产生一个新节点
        Node<E> node = new Node<>(val);
        if(head == null){
            head = node;
        }else{
            tail.next = node;
        }
        tail = node;//因为队列实行的是尾插,这步不管是否为空都执行
        size ++;
    }

    @Override//出队操作
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        //删除当前的对首元素,即head
        E val = head.val;
        Node<E> node = head;//保存待删除的头节点
        head = head.next;//换头节点位置
        node.next = null;//断开连接
        size --;
        return val;
    }

    @Override //查看队首元素
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        return head.val;
    }

    @Override //判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //模拟实现toString方法
    @Override
    public String toString() {
       StringBuilder sb = new StringBuilder();
       sb.append("front [");

        for (Node<E> x = head; x != null; x = x.next) {
            sb.append(x.val);
            if(x.next != null)
                sb.append(" -> ");
        }
        sb.append("] tail");
        return sb.toString();
    }

}

力扣关于队列的练习题:

225. 用队列实现栈 – 力扣(LeetCode)

232. 用栈实现队列 – 力扣(LeetCode)

2.3 循环队列

实际中我们有时还会使用一种队列叫循环队列。

如操作系统课程讲解生产者消费者模型或MySQL数据库的InnoDB存储引擎中的redo日志就会使用循环队列。 环形队列通常使用数组实现。

循环队列基本都是使用长度固定的数组来实现,数组在实现队列时,若从数组头部删除元素需要频繁的移动后面的元素带来效率比较低。
 

出队和入队操作,使用两个引用,一个head,一个tail,添加元素在数组尾部添加,删除元素只需要移动head引用指向的地址即可(逻辑删除)
 

循环队列就是使用长度固定的数组来实现,数组头部就是队首(head),数组的尾部就是队尾(tail)。数组[head.tail)是循环队列的有效元素
 

有种特殊情况:

 这怎么判断数组是为空还是满?

我们此时数组为空和数组满head == tail,因此没法区分当前循环队列到底是空还是满。
 

所以有个规定:在循环队列中浪费一个空间,判断队列是否已满。上面图片数组第二种情况其实就是满的状态了。

有三点:

 

 

 

用代码实现以下基于整型的循环队列

循环队列实现

 继承一下父类队列接口。Alt + 回车

 1.

2. 基本参数

 3. 

4. 这里需要拓展一个方法判断数组是否满

 注释:这里head 和 tail相当于数组下标,索引。

 5.

6.

 7.

8. 最后写一个打印方法toString方法

这里有个问题,所以的最后一位有效元素应该是多少? 

都说tail是最后一位元素的下一位,所以最后元素的下标为 tail – 1 ?

这里有个特殊情况: 因为这是循环队列,当 tail  = 0 呢? -1 是不能做余数的

所以用三木运算符做两种情况分析

测试一下:

 

 

如果此时再添加一个元素,就会报错,因为已经满了。

 再测试一下其他功能

 

 

注释:循环的本质就是对所以进行 取模操作  走到尾了下一步就变成头。

 

力扣循环队列练习题

622. 设计循环队列 – 力扣(LeetCode)

 

双端队列 (Deque)

 概念 双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,

deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队,也可以从队尾出队和入队

基础接口的功能

 以后无论使用的是栈还是接口,统─使用双端队列接口
不推荐使用Stack这个类,这个类已经是被时代所淘汰的,效率很低,都是同步操作。
双端队列的一个常用子类就是 LinkedList 

 

双端队列的使用

关机键是:Deque

这些引用接口的操作都是需要头文件滴

用双端队列接口创建一个 栈 

 用双端队列接口创建一个 队列

 发现:无论是创建一个栈还是队列,在双端队列里面一样都是

 

 

除了名字不一样外,其他都一样。 

 入栈是push,入队列是offer。

出栈叫 pop,出节点叫 poll


版权声明:本文为m0_61608447原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。