>> 欢迎您 客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章 返回首页
>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → Java数据结构与算法 - 栈和队列
发表一个新主题 开启一个新投票 回复文章 您是本文章第 20776 个阅读者 刷新本主题
 * 贴子主题:  Java数据结构与算法 - 栈和队列 回复文章 点赞(0)  收藏  
作者:flybird    发表时间：2020-02-06 17:37:51     消息  查看  搜索  好友  邮件  复制  引用
          
                              
      Java的数据结构主要涉及三种数据存储类型：栈，队列，优先级队列。这些数据存储类型的生命周期比数组等数据结构要短得多，在程序执行期间才被创建。栈的主要机制可以用数组来实现；队列，优先级队列可以使用数组或者一种特别的树 - 堆来实现。通过对数组进行封装，使得他们面向的问题更加专业。

      1）在这些数据结构中，只有一个数据项可以被访问。

      2）栈的操作是在栈顶压入一个数据项，以及从栈顶移除一个数据项。

      3）队列的操作是在队尾压入数据，在队头取出数据。

      4）优先级队列的操作是有序的插入数据，从队头取出关键字最小、最大的数据。

         1. 栈

       1.1. 栈的实现

       栈只允许访问一个数据项，即最后插入的数据项。移除这个数据项才能访问第二个数据项。一般来说将数组经过一定包装，使之满足压栈，弹栈的性质就能实现栈的基本能力。栈通常包含三个数据成员，两个基本方法：一个数组，一个最大栈空间，一个top指针；压栈，弹栈（读取栈顶元素）。                    
  1.        /**
  2.        *  @file 简单地说, 栈就是将数组进行封装来更方便的实现一些功能
  3.        *  @author zkj
  4.        *  @date 2017-07-27
  5.        */
  7.        class  Stack {
  8.      // 数据成员
  9.      private  int maxSize;
  10.      private  int[] stackArray;
  11.      private  int top;
  13.      // 构造函数
  14.        public  Stack ( int size) {
  15.      maxSize = size;
  16.      stackArray =  new  int[maxSize];
  17.      top = - 1;
  18.      }
  20.      // 压栈
  21.        public  void  push ( int element) {
  22.      if (!isFull())
  23.      stackArray[++top] = element;
  24.      }
  26.      // 弹栈
  27.        public  int  pop () {
  28.      return stackArray[top--];
  29.      }
  30.      }

   1.2 栈的应用

      栈的主要应用：文本匹配，比如检测源程序中括号匹配问题；算术表达式解析，比如3 * （4 + 5）；大部分微处理器基于栈的体系结构，在函数被调用时压栈，弹栈。

       1.2.1 文本括号匹配

       对于一串文本，检查括号是否匹配，比如abc{defg[hijklm(nopq)rstu]v}wxyz，检测括号是否配对。解决办法：遍历字符串，将{, [, ( 依次入栈（普通字符不入栈），当遍历到), ] }时，弹栈，进行比较，看两者是否匹配。                        

  1.       // 栈类：实现栈操作
  2.        class  StackChar {
  3.      // 数据成员
  4.      private  int maxSize;
  5.      private  char[] stackArray;
  6.      private  int top;
  8.      // 构造函数
  9.        public  StackChar ( int size) {
  10.      maxSize = size;
  11.      stackArray =  new  char[maxSize];
  12.      top = - 1;
  13.      }
  15.      // 压栈
  16.        public  void  push ( char element) {
  17.      if (!isFull())
  18.      stackArray[++top] = element;
  19.      }
  21.      // 弹栈
  22.        public  char  pop () {
  23.      return stackArray[top--];
  24.      }
  26.      // 栈满？
  27.        public  boolean  isFull () {
  28.      if (top == maxSize)
  29.      return  true;
  30.      else
  31.      return  false;
  32.      }
  34.      // 栈空？
  35.        public  boolean  isEmpty () {
  36.      if (top <  0)
  37.      return  true;
  38.      else
  39.      return  false;
  40.      }
  41.      }

  1.       // 检查是否匹配
  2.        class  BracketChecker {
  3.      private String input;
  5.        public  BracketChecker (String in) {
  6.      input = in;
  7.      }
  9.        public  void  check () {
  10.      int stackSzie = input.length();
  11.      StackChar theStack =  new StackChar(stackSzie);
  13.      for ( int i =  0; i < stackSzie; i++) {
  14.      char ch = input.charAt(i);
  15.      switch (ch) {
  16.      case  '{':
  17.      case  '[':
  18.      case  '(':
  19.      theStack.push(ch);
  20.      break;
  21.      case  '}':
  22.      case  '>':
  23.      case  ')':
  24.      if (!theStack.isEmpty()) {
  25.      char chx = theStack.pop();
  26.      if ((chx ==  '{' && ch !=  '}') || (chx ==  '[' && ch !=  ']') || (chx ==  '(' && ch !=  ')')) {
  27.      System.out.println( "Error: " + ch +  " at " + i);
  28.      }
  29.      }
  30.      else
  31.      System.out.println( "Error: " + ch +  " at " + i);
  32.      default:
  33.      break;
  34.      }
  35.      }
  37.      if (!theStack.isEmpty()) {
  38.      System.out.println( "Error: missing right delimiter.");
  39.      }
  40.      }
  41.      }

         2. 队列

      栈的特性是：先进后出；队列则是：先进先出。比如打印机打印东西的顺序，银行叫号排队系统等等。队列六个基本元素：存储数据的数组，头指针，尾指针，队列最大尺寸，数据进队列，数据出队列。

       2.1 队列的实现                  

  1.       // 队列类
  2.        class  Queue {
  3.      // 数据成员
  4.      private  int[] arr;
  5.      private  int head;
  6.      private  int tail;
  7.      private  int maxSize;
  9.      // 构造函数
  10.        public  Queue ( int size) {
  11.      maxSize = size;
  12.      head = - 1;
  13.      tail = - 1;
  14.      }
  16.      // 压入队列
  17.        public  void  push ( int element) {
  18.      if (tail <= maxSize){
  19.      arr[++tail] = element;
  20.      }
  21.      }
  23.      // 移除队列
  24.        public  int  pop () {
  25.      return arr[++head];
  26.      }
  27.      }

         3. 优先级队列

      优先级队列是指队列中的元素按照某种顺序进行排列，比如数值型数据的大小顺序，字符型数据字典序等等。有序插入，队头取出。

                                                                                                                          
----------------------------
原文链接:https://blog.csdn.net/ZK_J1994/article/details/76184916

程序猿的技术大观园：www.javathinker.net





[这个贴子最后由 flybird 在 2020-02-06 21:08:27 重新编辑]
Java精品书籍推荐
Java最新视频教程推荐
  Java面向对象编程-->输入与输出（下）
  JavaWeb开发-->JSP技术详解（Ⅱ）
  JSP与Hibernate开发-->数据库事务的概念和声明
  Java网络编程-->非阻塞通信
  精通Spring-->组合（Composition）API
  Vue3开发-->Vue指令
本站其他相关文章
  Codility 算法测验
  算法学习与收集：一些有用的算法网站和网页
  常见的调度算法
  算法的概念、特征和基本类型简介
  进程调度算法总结
  分布式一致Hash算法-存储之道
  Java 选择排序算法
  如何面对“算法”的困惑？
  用Java写算法：快速排序
  对称算法非对称算法哈希算法区别
  Citrix Netscaler负载均衡算法
  令牌桶算法
  活动安排问题（贪心算法）
  用Java实现回文数算法
  好书推荐：《小灰的算法之旅》
  更多...
 IPIP: 已设置保密
楼主      
共1页 0条记录 当前第1页
发表一个新主题 开启一个新投票 回复文章

中文版权所有： JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶，分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权，请与本站管理员联系。