• 【数据结构】栈和队列

    目录

    栈

    1、概念

    2、 栈的使用

    3、 栈的模拟实现

    相关概念区分

     队列

    1、 概念

    2、队列的使用

    3、队列模拟实现

    4、 循环队列

    为什么要有循环列队

    如何区分空与满

    5、双端队列 )

    栈

    1、概念

    栈(Stack) ：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为 栈顶 ，另一端称为栈底。栈中的数据元素遵守 后进先出 LIFO （ Last In First Out ）的原则。
    压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
    出栈：栈的删除操作叫做出栈。 出数据在栈顶 。

    来道例题： 

    1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
    A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

    注意： 进栈过程中可以出栈，答案选C

    2、 栈的使用

    Stack是Java提供的类，其中包含了可以对栈进行一系列操作的常见方法

    栈的方法：

    方法功能
    Stack （ ）构造一个空的栈
    E push ( E e）将e入栈,并返回e
    E pop ( )将栈顶元素出栈并返回
    E peek ( )获取栈顶元素
    int size ( )获取栈中有效元素个数
    boolean empty ( )检测栈是否为空

    代码示例：

    1. public static void main(String[] args) {
    2.         Stack<Integer> stack=new Stack<>();
    3.         stack.push(40);
    4.         stack.push(30);
    5.         stack.push(20);
    6.         stack.push(10);
    7.         System.out.println(stack);//[40, 30, 20, 10]
    8.         System.out.println(stack.search(new Integer(40)));//返回40下标4
    9.         System.out.println(stack.pop());//删除栈顶元素10并返回
    10.         System.out.println(stack.peek());//获取栈顶元素 20
    11.     }

    3、 栈的模拟实现

    从上图中可以看到， Stack 继承了 Vector ， Vector 和 ArrayList 类似，都是动态的顺序表，不同的是 Vector 是线程安全的。

     代码实例：

    1. public class Mystack {
    2.     int []elem;
    3.     int size;
    4.  
    5.     public Mystack(){
    6.         elem=new int[10];
    7.     }
    8.  
    9.     public int push(int e){
    10.         ensureCapacity();
    11.        elem[size++] = e;
    12.         return e;
    13.     }
    14.  
    15.     public int peek(){
    16.         if(empty()){
    17.             throw new RuntimeException("栈为空，无法获取栈顶元素");
    18.         }
    19.         return elem[size-1];
    20.     }
    21.  
    22.     public boolean empty(){
    23.         return 0 == size;
    24.     }
    25.  
    26.     public int pop(){
    27.         int e = peek();
    28.         size--;
    29.         return e;
    30.     }
    31.  
    32. //扩容
    33.     private void ensureCapacity(){
    34.         if(size==elem.length)
    35.             elem= Arrays.copyOf(elem,size*2);
    36.     }
    37. }

    相关概念区分

    栈、虚拟机栈、函数栈帧；这里对这几个概念进行一个浅浅的区分

    • 栈是一种数据结构
    • 虚拟机栈是JVM的一块内存
    • 函数栈帧是调用方法时为方法开辟的一块内存

     队列

    1、 概念

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

    2、队列的使用

    在 Java 中， Queue 是个接口，底层是通过链表实现 的。

     Queue方法：

    方法功能
    boolean offer (E e )入队列
    E poll ( )出队列
    peek ( )获取队头元素
    int size ( )获取队列有效元素个数
    boolean isEmpty(  )检测队列是否为空
    注意： Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
    代码实例： 
    1. public static void main(String[] args) {
    2.         
    3.             Queue<Integer> q = new LinkedList<>();
    4.             q.offer(1);
    5.             q.offer(2);
    6.             q.offer(3);
    7.             q.offer(4);
    8.             q.offer(5); // 从队尾入队列
    9.             System.out.println(q.size());
    10.             System.out.println(q.peek()); // 获取队头元素
    11.             q.poll();
    12.             System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
    13.             if(q.isEmpty()){
    14.                 System.out.println("队列空");
    15.             }else{
    16.                 System.out.println(q.size());
    17.             }
    18.     }

    3、队列模拟实现

    队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构 。 列的实现使用一般使用链式结构 
    1. public class MyQueue {
    2.         // 双向链表节点
    3.         public static class ListNode{
    4.             ListNode next;
    5.             ListNode prev;
    6.             int value;
    7.             ListNode(int value){
    8.                 this.value = value;
    9.             }
    10.         }
    11.         ListNode first; // 队头
    12.         ListNode last; // 队尾
    13.         int size = 0;
    14.         // 入队列---向双向链表位置插入新节点
    15.         public void offer(int e){
    16.             ListNode newNode = new ListNode(e);
    17.             if(first == null){
    18.                 first = newNode;
    19. // last = newNode;
    20.             }else{
    21.                 last.next = newNode;
    22.                 newNode.prev = last;
    23. // last = newNode;
    24.             }
    25.             last = newNode;
    26.             size++;
    27.         }
    28.         // 出队列---将双向链表第一个节点删除掉
    29.         public int poll(){
    30. // 1. 队列为空
    31. // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    32. // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
    33.             int value = 0;
    34.             if(first == null){
    35.                 return -1;
    36.             }else if(first == last){
    37.                 last = null;
    38.                 first = null;
    39.             }else{
    40.                 value = first.value;
    41.                 first = first.next;
    42.                 first.prev.next = null;
    43.                 first.prev = null;
    44.             }
    45.             --size;
    46.             return value;
    47.         }
    48.         // 获取队头元素---获取链表中第一个节点的值域
    49.         public int peek(){
    50.             if(first == null){
    51.                 return -1;
    52.             }
    53.             return first.value;
    54.         }
    55.         public int size() {
    56.             return size;
    57.         }
    58.         public boolean isEmpty(){
    59.             return first == null;
    60.         }
    61. }

    4、 循环队列

    实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

    为什么要有循环列队

    用数组实现队列时：

    用循环队列可以解决空间浪费的问题

    如何用代码将数组是变为循环队列

    rear向后移动公式

    rear =（ rear+1）% array.length

    rear向前移动公式 

    rear =（ rear-1+ array.length）% array.length

    如何区分空与满

    在未放元素时，rear=front，随着元素放满，rear与front相遇时，代表队列已满。那么，如何用代码区分队列为空与队列为满呢

    有三种办法：

    • 计数器：通过添加 count 属性记录
    • 使用标记，定义boolean 类型元素
    • 保留一个位置不放元素（判断rear下一个是否为 front ）

    小伙伴可以做道题练练手 

    设计循环队列

    5、双端队列 

    双端队列（deque）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。
    那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
    Deque是一个接口，使用时必须创建LinkedList的对象。
    在实际工程中，使用 Deque 接口是比较多的，栈和队列均可以使用该接口
    Deque stack = new ArrayDeque<>();// 双端队列的线性实现
    Deque queue = new LinkedList<>();// 双端队列的链式实现

    本篇文章到此结束，接下来会对二叉树相关知识进行讲解 

  • 相关阅读:
    Win11系统怎么设置默认浏览器教学
    UMLChina建模知识竞赛第4赛季第17轮
    深入推导理解sample softmax loss
    Jmeter系列-环境部署、详细介绍、安装目录介绍（1）
    svn(乌龟svn)和SVN-VS2022插件(visualsvn) 下载
    【前后端交互与HTTP协议】（HTTP协议、本地存储、Ajax&Fetch 与跨域请求）
    实现注册手机号用户
    【服务器】在 Linux CLI 下安装 Anaconda
    【小样本学习】2022 KDD Task-Adaptive Few-shot Node Classification
    保护数据隐私：深入探索Golang中的SM4加密解密算法
  • 原文地址：https://blog.csdn.net/m0_73107796/article/details/141003460