• 【java数据结构】栈和队列

    目录

    栈

    什么是栈

    java中的集合--->栈

     栈的使用

    栈的底层实现

    栈的应用之逆波兰表达式

    栈的应用之括号匹配问题

    队列

    什么是队列？

    数组实现队列

    链表实现队列

    栈

    什么是栈

    栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。

    栈这种数据结构是一种线性的数据结构，底层既可以由数组实现也可以利用链表来实现，栈有两种操作，都是对栈顶进行操作，分别是插入push()和删除pop()操作，所以是一种后进先出或者先进后出的一种数据结构，在生活中，经常就会有栈的存在，比如那在打开网页的时候，看见对你好奇感兴趣的东西你就会一直点开网页看(压栈的过程)，但是当我们看完我们想要的内容，我们就依次的关闭网页(出栈的过程)，而当我们又要打开以前的网页...关闭网页(都是一系列的压栈出栈过程循环往复)。

    java中的集合--->栈

    在java中，为了开发的方便，有了Stack接口，通过它我们就可以利用栈这种数据结构应用一些场景。

    stack常用的方法

     栈的使用

    我们一般使用栈也是要利用泛型。

    1. public static void main(String[] args) {
    2.     Stack<Integer> stack = new Stack<>();//栈的定义
    3.     stack.push(1);//栈的插入
    4.     stack.push(2);
    5.     stack.push(3);
    6.     stack.push(4);
    7.     System.out.println(stack.pop());//栈的弹出
    8.     System.out.println(stack.peek());//显示栈顶元素，不弹出
    9.     System.out.println(stack.size());//栈的容量大小(栈中有几个元素)
    10.     System.out.println(stack.empty());//判断栈是否为空
    11. }

    打印结果：

    1. 4
    2. 3
    3. 3
    4. false

    栈的底层实现

    栈既可以利用数组实现，也可以利用双向链表实现，对其插入和弹出时间复杂度都是O(1),对于访问元素最坏情况下就是O(1).

    这里采用数组实现

    1. public class MyStack {
    2.  
    3.     public int[] elem;//利用数组实现栈
    4.     public int usedSize;//有效个数
    5.  
    6.     public MyStack(){//构造方法-->用来初始化
    7.         this.elem = new int[5];//初始化数组容量为5
    8.         this.usedSize = 0 ;//最开始有效数据个数为0
    9.     }
    10.  
    11.     public int size(){//有效个数大小就是当前栈的容量
    12.          return this.usedSize;
    13.     }
    14.  
    15.     public boolean empty(){//判断栈是否为空
    16.          return this.usedSize==0;//当有效个数为0是代表栈为空
    17.     }
    18.  
    19.     public int peek(){//有效数据个数相当于数组有效长度 -1就是数组最后一个元素也就是栈顶元素
    20.          return this.elem[this.usedSize-1];
    21.     }
    22.  
    23.     private boolean isFull(){//当有效数组长度等于数组默认长度时证明栈已经满了
    24.         return this.elem.length == this.usedSize;
    25.     }
    26.  
    27.     public int push(int key){//插入元素-->栈顶
    28.          if(isFull()){//如果栈满了就需要扩容-->这里采用2倍扩容
    29.             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    30.          }
    31.          this.elem[usedSize++] = key;//将当前key插入到usedSize中，同时长度要+1
    32.          return key;
    33.     }
    34.  
    35.     public int pop(){//将栈顶元素弹出
    36.          int ret = this.elem[this.usedSize-1];
    37.          this.usedSize--;//有效长度-1
    38.          return ret;//返回从栈顶弹出的元素
    39.     }
    40.  
    41. }

    栈的应用之逆波兰表达式

    什么是逆波兰表达式呢？？-->来源力扣150. 逆波兰表达式求值

    逆波兰表达式：

    逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

    平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
    该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
    逆波兰表达式主要有以下两个优点：

    去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
    适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

    也就是说我们平常写的对数的加法减法乘法除法，都是这样的..的例如： ( 1 + 2 ) * ( 3 + 4 )-->中缀表达式，而我们这样能让计算机读懂呢？？->这就引入了今天的逆波兰表达式也就是后缀表达式，我们就让中缀表达式转成后缀表达式。

    例如：1+2*3+(4*2+5)*6

    •  将所有运算都加上大括号
    • 将运算符移动到对应括号的外面
    • 去掉所有括号

    好了我们就得到了一个后缀表达式-->也就是计算机能读懂的计算

    那计算机是怎么通过这样的后缀表达式来计算出结果呢？？？

    那就是我们这样神奇的数据结构-->栈

    • 遇到数字就加入到栈中
    • 遇到运算符就出两个数字
    • 第一次出的放在运算符右边，第二次出的放运算符左边
    • 计算完成之后继续放入栈中
    • 最终栈顶元素就是最终表达式计算的结果

    代码实现：

    1. class Solution {
    2.     public int evalRPN(String[] tokens) {
    3.         //思路：遇到数字就入栈，如果遇到数字符号就出两个数进行计算
    4.         //计算结果继续入栈，一直遍历字符串结束
    5.         Stack<Integer> stack = new Stack<>();
    6.         for(int i =0;i<tokens.length;++i){
    7.             String str = tokens[i];
    8.             if(!isNumCharacter(str)){//判断是否是符号
    9.                //如果是数字的话就将其入栈
    10.                int num = Integer.parseInt(str);
    11.                stack.push(num);
    12.             }else{
    13.                 //如果是字符就弹栈，弹出两个数字
    14.                 int num2 = stack.pop();
    15.                 int num1 = stack.pop();
    16.                 switch(str){
    17.                     case "+":
    18.                          stack.push(num1+num2);
    19.                          break;
    20.                     case "-":
    21.                          stack.push(num1-num2);
    22.                          break;
    23.                     case "*":
    24.                          stack.push(num1*num2);
    25.                          break;
    26.                     case "/":
    27.                          stack.push(num1/num2);
    28.                          break;
    29.                 }
    30.             }
    31.         }
    32.         return stack.peek();
    33.     }
    34.     //用来判断这个字符串是否是字符
    35.     public boolean isNumCharacter(String s){
    36.         if(s.equals("+")||s.equals("*")||
    37.         s.equals("-")||s.equals("/")){
    38.             return true;
    39.         }
    40.         return false;
    41.     }
    42. }

    栈的应用之括号匹配问题

    -->20. 有效的括号

    这个也是栈的应用经典问题

    输入：s = "( )"         输出：true        输入：s = "( )[ ]{ }"        输出：true
    输入：s = "( ]"         输出：false        输入：s = "( [ ) ]"          输出：false
    输入：s = "{ [ ] }"       输出：true

    这个题就是一共有三种括号【】{} （）然后这三个可以混合也可以不混合，看是否是匹配的？

    思路：

    左括号都入栈，然后看遍历的字符是否与其匹配，如果匹配将栈顶左括号弹出继续遍历，如果最后栈中还有元素，或者还有没遍历完的字符串但栈已经为空都是不匹配的

    1. class Solution {
    2.     public boolean isValid(String s) {
    3.        //如果是左括号就入栈
    4.        Stack<Character> stack = new Stack<>();
    5.        for(int i =0;i<s.length();++i){
    6.             //如果是左括号就入栈
    7.             if(s.charAt(i)=='('||s.charAt(i)=='['
    8.             ||s.charAt(i)=='{'){
    9.                 stack.push(s.charAt(i));
    10.             }else {
    11.                 //如果不是右括号那就要与栈顶元素进行比较
    12.                 if(stack.empty()){
    13.                     //如果栈为空，无法比较
    14.                     return false;
    15.                 }else {
    16.                     //栈不为空看是否是匹配的情况
    17.                     if((stack.peek()=='('&&s.charAt(i)==')')
    18.                     ||(stack.peek()=='{'&&s.charAt(i)=='}')||
    19.                     (stack.peek()=='['&&s.charAt(i)==']')){
    20.                         stack.pop();
    21.                     }else {
    22.                         //如果相等弹出栈顶元素
    23.                        return false;
    24.                     }
    25.                 }
    26.             }
    27.        }
    28.            return stack.empty();
    29.     }
    30. }

    队列

    什么是队列？

    队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue

    队列也是一种线性结构，与栈不同，栈是先进后出，而队列呢是先进先出，主要维护两个指针域，一个是front，一个是rear，当我们进行插入操作的时候也就是rear操作也就是入队 enqueue。当我们要删除元素时，删除对头元素也就是出队 dequeue。

    队列既可以利用数组实现(叫做顺序队列，改进之后变成循环队列)，也可以利用链表实现。

    数组实现队列

    • 顺序队列

    最开始我们只利用front作为对头元素front固定不动。

     但是这样的缺点是我们插入的时间复杂度是O(1),而删除是从对头元素删除，这样的时间复杂度是O(N)。

    之后有发明了一种，那为啥对头固定不动呢？？？,然后设置了对头可以移动，不一定就是下标为0就是对头元素，任意下标都可以为对头元素，这样时间复杂度就都是O(1).

     但是这样又有缺点就是会出现假溢出的情况。

    那什么是假溢出呢？？就是原本数组没有满还可以继续插入元素，然因为对头front==队尾rear，此时就认为是满了，那怎么办呢？？？

    最后有发明了一种循环数组，那既然前面还有空间，我们能不能让它卷起来呢，也就是rear在front前面，成了一个循环队列，这样就避免了上面的情况

     对于环形队列有以下几个问题

    • 走到下一步怎么走？？难道是rear = rear+1么？？？front = front+1么？？

     如果不是从7下标走到0下标，rear=rear+1没毛病，但是因为是循环队列，我们要让rear走到0下标位置，此时就不能怎这么走了，计算公式应该是 rear = (rear+1)%arr.length。

    • 怎么判断队列是空呢？？

    当front==rear相遇时我们证明它是空的队列。

    • 怎么判断队列是否为满呢? ？

    这里有三种方式来判断队列是否为满。

    1. 利用计数器的方法，当计数=数组长度的时候，我们就证明它是满的。
    2. 利用标记的方法，刚开始rear和front相遇时我们设置标记flag=0，当rear和front再次相遇的时候我们将标记置为1，证明队列已经是满的。
    3. 还可以采用空一个空间，来进行判断是否为满，当(rear+1)%arr.length == front时候就认为是满的情况

    我们这里采用第三种方法来判断队列是否为满

     代码实现：

    1. class MyCircularQueue {
    2.  
    3.     private int[] elem;//利用数组实现队列
    4.     private int front;//头指针
    5.     private int rear;//尾指针
    6.  
    7.     public MyCircularQueue(int k) {//由于让k个空间全部放满元素,k+1用来空一个元素判断队列是否满？？
    8.         this.elem = new int[k+1];//初始化k+1个空间
    9.     }
    10.     
    11.     public boolean enQueue(int value) {
    12.         //如果满了就不能入队
    13.         if(isFull()){
    14.             return false;
    15.         }
    16.         this.elem[rear] = value;
    17.         this.rear = (this.rear+1)%this.elem.length;//存放一个元素，向前走一步
    18.         return true;
    19.     }
    20.     
    21.     public boolean deQueue() {
    22.         if(isEmpty()){//如果队列为空，不能删除元素
    23.             return false;
    24.         }
    25.         this.front = (this.front+1)%this.elem.length;
    26.         return true;
    27.     }
    28.     
    29.     public int Front() {//获取队头元素
    30.         if(isEmpty()){
    31.             return -1;
    32.         }
    33.         return this.elem[front];
    34.     }
    35.     
    36.     public int Rear() {//获取对尾元素
    37.         if(isEmpty()){
    38.             return -1;
    39.         }
    40. //这里特殊情况就是rear为0的情况为数组长度-1就是队尾元素，否则的话就是rear-1
    41.         int index = this.rear==0?this.elem.length-1:rear-1;
    42.         return this.elem[index];
    43.     }
    44.     
    45.     public boolean isEmpty() {//当头指针和尾指针相遇的时候就代表队列为空
    46.         return this.front == this.rear;
    47.     }
    48.     
    49.     public boolean isFull() {//空一个判断是否为满
    50.         return (this.rear+1)%this.elem.length == this.front;
    51.     }
    52. }

    链表实现队列

     

    Description:

    利用链表实现一个队列--->利用单链表带两个索引一个front在前面 一个rear在后面 -->我们采用尾入头出这样时间复杂度都是O(1)

    代码实现：

    1. /**
    2.  * Description:利用链表实现一个队列--->利用单链表带两个索引
    3.  *一个front在前面 一个rear在后面 -->我们采用尾入头出这样时间复杂度都是O(1)
    4.  */
    5. public class MyQueue {
    6.  
    7.     static class Node{
    8.         //创建一个单链表，有两个索引值
    9.         private int val;//节点的值
    10.         private Node next;//节点next指针指向下一个节点
    11.         public Node(int val){
    12.             this.val = val;
    13.         }
    14.     }
    15.     private Node front;//队头-->头出队
    16.     private Node rear;//队尾--->尾入队
    17.     private int usedSize;
    18.     /**
    19.      * 入队
    20.      * @param val-
    21.      */
    22.     public void offer(int val){
    23.         if(front==null){
    24.             Node node = new Node(val);
    25.             front = node;
    26.             rear = node;
    27.             this.usedSize++;
    28.         }else {
    29.             Node node = new Node(val);
    30.             //尾入队
    31.             rear.next = node;
    32.             rear = node;
    33.             this.usedSize++;
    34.         }
    35.     }
    36.  
    37.     /**
    38.      * 获取队列大小
    39.      */
    40.     public int size(){
    41.          return this.usedSize;
    42.     }
    43.  
    44.     /**
    45.      * 出队-->对头出队相当于头删
    46.      */
    47.     public int poll(){
    48.         if(isEmpty()){
    49.             return -1;
    50.         }
    51.         int ret =0;
    52.         if(front.next==null){
    53.             //只剩下一个节点的时候
    54.             ret = front.val;
    55.             front=null;
    56.             rear=null;
    57.             this.usedSize--;
    58.         }else {
    59.             ret = front.val;
    60.             front = front.next;
    61.             this.usedSize--;
    62.         }
    63.         return ret;
    64.     }
    65.  
    66.     /**
    67.      * 判断队列是否为空
    68.      */
    69.     public boolean isEmpty(){
    70.          return this.usedSize==0;
    71.     }
    72.  
    73.     /**
    74.      * 获取对头元素
    75.      */
    76.     public int peek(){
    77.         if(isEmpty()){
    78.             return -1;
    79.         }
    80.         return front.val;
    81.     }
    82.  
    83. }

  • 相关阅读:
    《第一行代码》读书笔记(2)—日志工具Log
    中基协：推荐使用电子合同
    MySQL创建表的时候建立联合索引的方法
    AVL树简介
    Java手写桶排序和算法案例拓展
    y120.第七章 服务网格与治理-Istio从入门到精通 -- Istio流量治理快速入门(六)
    C++学习day--19 内存分布
    SQL Server教程 - T-SQL-游标（CURSOR）
    vscode rust 环境搭建
    使用python对比两个json文件的不同并输出
  • 原文地址：https://blog.csdn.net/m0_61210742/article/details/125550237