• 【数据结构与算法】栈与队列相关算法的实现

    目录

    检查括号是否成对出现

    反转字符串

    循环队列的实现

    使用队列实现栈

    使用栈实现队列

    检查括号是否成对出现

    算法要求

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断该字符串是否有效。
    有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。

    比如: "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是 

    解题思路     

    1、我们可以通过一个HashMap来存放所有括号类型，右括号为键，左括号为值。

    2、遍历字符串，如果是左括号就入栈，右括号则和栈顶元素作比较，如果刚好形成一对完成括号，则继续。否则说明不是一对完整括号。

    3、遍历结束后判断栈中元素是否全部取出，只有全部取出，说明这个字符串中符号成对出现。

    1.     /**
    2.      * 判断这个符号字符串中符号是否成对出现
    3.      * @param s
    4.      * @return
    5.      */
    6.     public static boolean isValid(String s){
    7.         //创建一个hashMap把所有符号都存入
    8.         Map maps =new HashMap<>();
    9.         maps.put(')','(');
    10.         maps.put(']','[');
    11.         maps.put('}','{');
    12.  
    13.         Stack stack =new Stack<>();
    14.         //将字符串转换为字符数组
    15.         char[] chars= s.toCharArray();
    16.         //遍历字符数组
    17.         for (int i = 0; i 
    18.             //判断这个符号是否为右括号
    19.             if (maps.containsKey(chars[i])){
    20.                 //栈中如果为空赋值为#否则取出栈顶元素
    21.                 char isEmpty =stack.isEmpty()?'#':stack.pop();
    22.                 //判断这个右括号对应的左括号是否等于栈顶元素
    23.                 if (isEmpty!=maps.get(chars[i])){
    24.                     return false;
    25.                 }
    26.             }else {
    27.                 //如果为左括号则入栈
    28.                 stack.push(chars[i]);
    29.             }
    30.         }
    31.         //遍历结束 如果栈中还有元素 则说明其中没有对应括号
    32.         return stack.isEmpty();
    33.     }

    测试

    1.     public static void main(String[] args) {
    2.         System.out.println("[]{}()中符号是否成对出现："+isValid("[]{}()"));
    3.         System.out.println("{([})}中符号是否成对出现："+isValid("{([])}"));
    4.         System.out.println("([)]中符号是否成对出现："+isValid("([)]"));
    5.         System.out.println("(()中符号是否成对出现："+isValid("(()"));
    6.     }

    测试结果

    反转字符串

    这个就直接运用栈的后进先出原则，把字符串依次入栈再出栈就行。

    1.    /**
    2.     * 字符串的反转
    3.     * @param s
    4.     * @return
    5.     */   
    6.     public static String stringReversal(String s){
    7.         Stack stack =new Stack<>();
    8.         for (int i =0;i
    9.             stack.push(s.charAt(i));
    10.         }
    11.         String news="";
    12.         for (int i = 0, len = stack.size(); i < len; i++) {
    13.             news+=stack.pop();
    14.         }
    15.         return news;
    16.     }

    测试

    1.     public static void main(String[] args) {
    2.         String ts ="the shy";
    3.         String yskm ="you should know me";
    4.         System.out.println("ts反转前："+ts);
    5.         System.out.println("ts反转后："+stringReversal(ts));
    6.         System.out.println("yskm反转前："+yskm);
    7.         System.out.println("yskm反转后："+stringReversal(yskm));
    8.  
    9.     }

    测试结果

    循环队列的实现

    和队列相比，循环队列的优点就是不会造成假溢出，因为当队尾到达数组的末尾时，如果数组头部还有空间，则会继续向头部移动。会形成一个循环，除非队尾与队头相邻，则队列才满。

    1. /**
    2.  * 循环队列的实现
    3.  * @author CC
    4.  * @version 1.0
    5.  * @since2023/9/28
    6.  */
    7. public class CircularQueue {
    8.     private int[] array;//使用数组来存储
    9.     private int front;//对头
    10.     private int rear;//队尾
    11.  
    12.     //实例队列并设置初始容量
    13.     public CircularQueue(int capacity){
    14.         this.array =new int[capacity];
    15.     }
    16.  
    17.  
    18.     /**
    19.      * 入队
    20.      * @param element
    21.      * @throws Exception
    22.      */
    23.     public void offer(int element) throws Exception {
    24.         //队尾不能存值 所以队尾的下一个元素如果是队头 说明队列已满
    25.         if ((rear+1)%array.length==front){
    26.             throw new Exception("队列已满！");
    27.         }
    28.         //将值存入队尾
    29.         array[rear] =element;
    30.         //队尾向后移动
    31.         rear =(rear+1)%array.length;
    32.     }
    33.  
    34.     /**
    35.      * 出队
    36.      * @return
    37.      * @throws Exception
    38.      */
    39.     public int pull() throws Exception {
    40.         //如果队头等于队尾 则只有一个可能 就是该队为空
    41.         if (rear==front){
    42.             throw new Exception("队列为空！");
    43.         }
    44.         //取出队头元素
    45.         int deQueueElement =array[front];
    46.         //队头向后移动
    47.         front=(front+1)%array.length;
    48.         return deQueueElement;
    49.     }
    50.  
    51.     /**
    52.      * 输出队列
    53.      * @return
    54.      */
    55.     @Override
    56.     public String toString() {
    57.         StringJoiner sj =new StringJoiner("-");
    58.         for (int i=front;i!=rear;i=(i+1)%array.length){
    59.             sj.add(String.valueOf(array[i]));
    60.         }
    61.         return sj.toString()+"-队尾";
    62.     }
    63. }

    测试

    1. /**
    2.  * @author CC
    3.  * @version 1.0
    4.  * @since2023/9/28
    5.  */
    6. public class CTest {
    7.     public static void main(String[] args) throws Exception {
    8.         CircularQueue queue = new CircularQueue(5);
    9.         queue.offer(1);
    10.         queue.offer(2);
    11.         queue.offer(3);
    12.         queue.offer(4);
    13.         System.out.println("接连将1、2、3、4分别入队后："+queue);
    14.         queue.pull();
    15.         System.out.println("发生一次出队后："+queue);
    16.         queue.offer(5);
    17.         System.out.println("将5入队后："+queue);
    18.     }
    19. }

    测试结果

    使用队列实现栈

    实现原理

    通过创建两个队列，一个为出栈队列，一个为入栈队列。首先入栈队列是一直为空的，在入栈时先将元素存入入栈队列，再将出栈队列的元素依次存入入栈队列，这就将刚入元素就被放入了队尾。然后交换两个队列，出栈时将出栈队列队头元素出栈，也就是最早入栈的元素。

    1. /**
    2.  * @author CC
    3.  * @version 1.0
    4.  * @since2023/9/30
    5.  */
    6. public class MyStack {
    7.     private Queue queue1; //出栈队列
    8.     private Queue queue2; //入栈队列
    9.  
    10.     /**
    11.      * 初始化栈 底层使用链表存储
    12.      */
    13.     public MyStack() {
    14.         queue1 = new LinkedList();
    15.         queue2 = new LinkedList();
    16.     }
    17.  
    18.     /**
    19.      * 入栈
    20.      * @param item
    21.      */
    22.     public void push(int item) {
    23.         //将元素存入队列2
    24.         queue2.offer(item);
    25.         //将队列1中元素依次出队 并存入队列2
    26.         while (!queue1.isEmpty()){
    27.             queue2.offer(queue1.poll());
    28.         }
    29.         //交换队列1 与 队列2
    30.         Queue temp = queue1;
    31.         queue1 = queue2;
    32.         queue2 = temp;
    33.     }
    34.  
    35.     /**
    36.      * 出栈
    37.      * @return
    38.      */
    39.     public int pop(){
    40.         return queue1.poll();
    41.     }
    42.  
    43.     /**
    44.      * 获取栈顶元素
    45.      * @return
    46.      */
    47.     public int top(){
    48.         return queue1.peek();
    49.     }
    50.  
    51.     /**
    52.      * 判断该栈是否为空
    53.      * @return
    54.      */
    55.     public boolean isEmpty(){
    56.         return queue1.isEmpty();
    57.     }
    58.  
    59.  
    60.     /**
    61.      * 输出栈中元素
    62.      * @return
    63.      */
    64.     @Override
    65.     public String toString() {
    66.         StringJoiner sj =new StringJoiner("-");
    67.         for (Integer integer : queue1) {
    68.             sj.add(String.valueOf(integer));
    69.         }
    70.         return "栈顶"+sj.toString();
    71.     }
    72. }

    测试

    1. /**
    2.  * @author CC
    3.  * @version 1.0
    4.  * @since2023/9/30
    5.  */
    6. public class MyStackT {
    7.     public static void main(String[] args) {
    8.         MyStack stack =new MyStack();
    9.         stack.push(1);
    10.         stack.push(2);
    11.         stack.push(3);
    12.         stack.push(4);
    13.         System.out.println("1、2、3、4依次入栈后："+stack);
    14.  
    15.         System.out.println("出栈元素："+stack.pop());
    16.         System.out.println("出栈一次后："+stack);
    17.  
    18.         System.out.println("查看栈顶元素(不取出)："+stack.top());
    19.  
    20.         System.out.println("查看栈顶元素后:"+stack);
    21.         System.out.println("该栈是否为空："+stack.isEmpty());
    22.         System.out.println("出栈元素："+stack.pop());
    23.         System.out.println("出栈元素："+stack.pop());
    24.         System.out.println("出栈元素："+stack.pop());
    25.         System.out.println("该栈是否为空："+stack.isEmpty());
    26.     }
    27. }

     测试结果

    使用栈实现队列

    实现原理

    创建两个栈，一个为入队栈、一个为出队栈。入队栈的出栈顺序为后进先出。因为出队时，需要把入队栈的元素依次出栈再入栈到出队栈。后进先出的后进先出就为先进先出。所以出队栈的出栈顺序为先进先出。以此来实现和队列相同逻辑，先进先出。

    1. /**
    2.  * @author CC
    3.  * @version 1.0
    4.  * @since2023/9/30
    5.  */
    6. public class MyQueue {
    7.     private Stack inStack =new Stack<>(); //入队栈
    8.     private Stack outStack =new Stack<>(); //出队栈
    9.  
    10.     /**
    11.      * 入队
    12.      * @param item
    13.      */
    14.     public void offer(int item){
    15.         //将出堆栈中的元素依次放入入队栈中
    16.         while (!outStack.isEmpty()){
    17.             inStack.push(outStack.pop());
    18.         }
    19.         //入队栈入栈
    20.         inStack.push(item);
    21.     }
    22.  
    23.     /**
    24.      * 出队
    25.      * @return
    26.      */
    27.     public int poll(){
    28.         //将入堆栈中的元素依次放入出队栈中
    29.         while (!inStack.isEmpty()){
    30.             outStack.push(inStack.pop());
    31.         }
    32.         //出堆栈出栈
    33.         return outStack.pop();
    34.     }
    35.  
    36.     /**
    37.      * 判断队中是否为空
    38.      * @return
    39.      */
    40.     public boolean isEmpty(){
    41.         return inStack.isEmpty()&outStack.isEmpty();
    42.     }
    43.  
    44.     /**
    45.      * 查看队列元素
    46.      * @return
    47.      */
    48.     @Override
    49.     public String toString() {
    50.         while (!inStack.isEmpty()){
    51.             outStack.push(inStack.pop());
    52.         }
    53.         StringJoiner sj =new StringJoiner("-");
    54.         for (Integer integer : outStack) {
    55.             sj.add(integer.toString());
    56.         }
    57.         return "队尾-"+sj.toString();
    58.     }
    59. }

    测试

    1. public class MyQueueT {
    2.     public static void main(String[] args) {
    3.         MyQueue myQueue =new MyQueue();
    4.         // 入队
    5.         myQueue.offer(1);
    6.         myQueue.offer(2);
    7.         myQueue.offer(3);
    8.         myQueue.offer(4);
    9.         myQueue.offer(5);
    10.         System.out.println("依次入队1、2、3、4、5后："+myQueue);
    11.  
    12.         // 出队
    13.         System.out.println("出队:"+myQueue.poll()); // 1
    14.         System.out.println("出队:"+myQueue.poll()); // 2
    15.         System.out.println("出队:"+myQueue.poll()); // 3
    16.         System.out.println("连续三次出队后："+myQueue);
    17.         // 入队
    18.         myQueue.offer(6);
    19.         myQueue.offer(7);
    20.         myQueue.offer(8);
    21.         System.out.println("依次入队6、7、8后："+myQueue);
    22.         // 出队
    23.         System.out.println("出队:"+myQueue.poll()); // 4
    24.         System.out.println("出队:"+myQueue.poll()); // 5
    25.         System.out.println("出队:"+myQueue.poll()); // 6
    26.         System.out.println("连续三次出队后："+myQueue);
    27.         System.out.println("队内是否为空："+myQueue.isEmpty());
    28.  
    29.         System.out.println("出队:"+myQueue.poll()); // 7
    30.         System.out.println("出队:"+myQueue.poll()); // 8
    31.         System.out.println("队内是否为空："+myQueue.isEmpty());
    32.     }
    33. }

    测试结果

  • 相关阅读:
    电脑电源灯一闪一闪开不了机怎么办
    汇编基础(1)--ARM32
    十二、SpringBoot文件上传使用及流程分析【文件上传参数解析器】
    备战数学建模48-数学规划模型终结篇(全)(攻坚战13)
    前端面试题JS篇（3）
    Opencv 基本操作三 实现各个形态学处理并实现多图展示
    精心整理了超详细的Linux入门笔记，零基础也能看懂，一学就会
    辅助驾驶功能开发-执行器篇(03)-Mobileye Control Requirements
    leetcode-二叉搜索树与双向链表-89
    python的/ 和// 学习
  • 原文地址：https://blog.csdn.net/c1390527393/article/details/133430258