数据结构与算法分析——栈

定义

栈是一种操作受限的线性表,只支持在一端进行插入和删除操作(入栈和出栈)。后进先出、先进后出是它最大的特点。当某个数据集合只在一端插入和删除数据,并满足先进后出的特性时,就可以选择栈这种数据结构。

数据结构与算法分析——栈

实现

栈既可以通过数组实现,也可以通过链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。

class stack {
    private $size;
    private $top = -1;
    private $stack = array();
    public function __construct( $size ){
       $this->size = $size ;
    }
    #判断栈是否为空
    public function isEmpty() {
        return ( $this->top == -1 ? true : false ) ;
    }
    #判断栈是否已满
    public function isFull(){
        return ( $this->top < $this->size-1 ? false : true);
    }
    #入栈
    public function pushStack( $data ) {
        if( $this->isFull() ){
            return false;
        }
        $stack[] = $data;
        $top++;
        return true;
    }
    #出栈
    public function popStack(){
        if( $this->isEmpty() ){
            return false;
        }
        unset( $stack[ $top ] );
        $top--;
        return true;
    }
}

应用

基于栈结构对数据存取采用 " 先进后出、后进先出 " 原则的特点,它可以用于实现很多功能。

1,浏览器的回退、前进功能。

2,括号匹配问题。

3,数值的进制转换功能。

拿括号匹配做个例子:
这里我们假设只有圆括号、方括号和花括号。{[](){}}或 [{()}] 等是合规的格式,而 {[}()] 为不合规的格式。

  1. 从左向右依次扫描字符串,当扫描到左括号时,将其入栈;
  2. 当扫描到右括号时,从栈顶取出左括号。如果匹配,则继续扫描字符串。如果不匹配或栈空,说明是不合规格式。
  3. 当字符串扫描结束,如果栈空,则是合规字符。如果栈不空,则是不合规格式。

额外说下浏览器的前进和后退功能。

我们可以使用两个栈,m 和 n,将浏览的页面依次压入栈 m中。当点击后退按钮时,依次从栈 m 中出栈,并依次放入栈 n 中。当我们点击浏览器的前进按钮时,我们依次从栈 n 中取出数据,放入栈 m 中。当栈 m 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 n 中没有数据,那就说明没有页面可以点击前进按钮浏览了。这样,浏览器的前进和后退功能就实现了。

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 2

return ( $this->top == -1 ? true : false ) ;

1周前 评论

有两个问题比较疑惑:

  1. 出栈方法 popStack 为什么返回布尔型,返回出栈的内容是不是更好一些?
    2.出栈和入栈方法里的 $top++$top-- 是不是应该换成 $this->top++$this->top-- ?
1周前 评论
g-sabo (楼主) 1周前

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!