定义

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

实现

栈既可以通过数组实现，也可以通过链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。不管基于数组还是链表，入栈、出栈的时间复杂度都为 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 协议》，转载必须注明作者和本文链接