登录  /  注册
首页 > 常见问题 > 正文

程序员,你应该知道的数据结构之栈

angryTom
发布: 2019-08-23 17:01:35
转载
1928人浏览过

程序员,你应该知道的数据结构之栈

  数据结构中的栈不要与 Java 中的栈混淆,他们俩不是一回事,数据结构中的栈是一种受限制的线性表,栈具有先进后出、后进先出的特点,因为栈只允许访问最后一个数据项,即最后插入的数据项。也许你会有疑问,栈既然有这么多限制,为什么不用数组或者链表而使用栈?在开发中,我们有特定的场景,根据特定的场景去选用数据结构,栈的适用场景非常多,比如浏览器的前进与后退、字符串括号的合法性等,我们使用栈来实现就比较好,因为栈相对数组、链表来说对外提供的接口要少很多,接口少了,出错的概率就减少了,对风险的可控性就提高了。

推荐教程:PHP视频教程

实现一个栈

  从栈的定义中可以看出,栈主要有两个操作,一个是新增一条数据,我们叫做入栈,另一个是获取一条数据,称为出栈,下面两张图是入栈出栈示意图。

php81.png

php82.png

  栈的实现有两种方式,一种是基于数组实现的,我们叫作顺序栈,另一种是基于链表实现的,我们叫作链式栈。下面是两种栈的实现代码

基于数组的顺序栈

/**
 * 基于数组的顺序栈
 */
 public class ArrayStack {    // 栈最大容量
    private int maxSzie;    // 存放内容
    private String[] array;    // 栈顶元素
    private int top;    
    public ArrayStack(int size){      
      this.maxSzie = size;        
      this.array = new String[this.maxSzie];        
      this.top = 0;
    }  
      /**
     * 入栈操作
     *
     * @param data 数据
     * @return 0:入栈失败 1:入栈成功
     */
    public int push(String data) {      
      if (top == maxSzie) return 0;
        array[top] = data;
        top++;        
        return 1;
    }    
    /**
     * 出栈操作
     *
     * @return
     */
    public String pop() {     
       if (top == 0) return null;        
       return array[--top];
    }    
    /**
     * 获取栈顶元素
     *
     * @return
     */
    public String peek() {     
       return array[top - 1];
    }    
    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {    
        return top == 0;
    }
}
登录后复制

基于链表的链式栈

/**
 * 基于链表的链式栈
 */public class LinkStack {    // 始终指向栈的第一个元素
    private Node top = null;    
    /**
     * 压栈
     *
     * @param data
     * @return
     */
    public int push(String data) {
        Node node = new Node(data);        
        if (top == null) {
            top = node;
        } else {
            node.next = top;
            top = node;
        }       
         return 1;
        }   
     /**
     * 出栈
     *
     * @return
     */
    public String pop() {     
       if (top == null) return null;
        String data = top.getData();
        top = top.next;       
         return data;
    }   
     /**
     * 节点信息
     */
    private static class Node {      
      private String data;      
      private Node next;        
      public Node(String data) {        
          this.data = data;          
          this.next = null;
        }       
      public String getData() {          
        return this.data;
        }
    }
}
登录后复制

  栈的实现比较简单,因为栈涉及的操作不多,主要就入栈和出栈两个操作。

栈的应用

检测字符串括号的合法性

  我们有时候需要检测字符串括号的合法性,即一个左括号需要匹配一个右括号,这个我们可以使用栈来实现。我们可以从一个合法的括号来理解为什么使用栈?如果括号使用合法,最后一个左括号跟第一个右括号是匹配的,倒数第二个左括号和第二个右括号匹配的,以此类推,这符合我们栈的特性先进后出。

  假设我们有三种括号:圆括号 ()、方括号 [] 和花括号{},我们使用栈来检测括号的合法性。我们将左括号全部压栈,当出现右括号时,我们就进行匹配,这时候有如下三种情况:

  ●栈为空,说明没有左括号,括号使用不合法

  ●栈中取出来的左括号跟右括号不匹配,括号使用不合法

  ●栈中取出的左括号跟右括号匹配,括号使用暂时合法

  当整个字符串都扫描完成后,检测栈中是否还有值,如果栈为空,则说明括号使用合法,反正,则括号使用不合法。

实现代码

public static boolean BracketChecker(String data) {
    char[] chars = data.toCharArray();
    ArrayStack stack = new ArrayStack(chars.length);    
    for (char ch : chars) {
            switch (ch){
                        case '{':            
                        case '[':            
                        case '(':
                                stack.push(ch);                
                                break;            
                         case '}':            
                         case ']':            
                         case ')':             
                                if (!stack.isEmpty()){                 
                                   char ch1 = stack.pop();                    
                                   if ((ch=='}' && ch1 !='{')
                                        ||(ch==']' && ch1 !='[')
                                        ||(ch==')' && ch1 !='(')

                    ){                 
                           return false;
                    }
                }else {    
                           return false;
                }     
                break;            
        default:            
            break;
        }
    }   
    return stack.isEmpty();
}
登录后复制

浏览器前进、后退功能

  我们使用浏览器都知道,浏览器可以前进、后退功能,浏览器的前进后退也符合栈的特点,我们最先访问的网页肯定要最后才能倒回去。我们一起来看看栈怎么实现这个功能?

  我们需要定义两个栈,我们将首次访问的页面压栈到第一个栈中,当点击后退时,从第一个栈中取出数据放入到第二个栈,当点击前进按钮时,从第二个栈取出数据放入第一个栈。当第一个栈没有数据时,说明没有页面可以点击后退了,当第二个栈没有数据时,说明没有页面可以点击前进了。这样我们就通过栈实现了浏览器前进、后退功能。

以上就是程序员,你应该知道的数据结构之栈的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:博客园网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号