标签归档:

算法学习四、栈

栈是一种“操作受限”的线性表,后进者先出,先进者后出,这就是典型的“栈”结构。当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

栈的实现

栈主要包含两个操作,入栈和出栈。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈

class StackOnArray
{
    public $data;
    public $count;// 栈中元素个数
    public $length;// 栈的长度


    public function __construct($length)
    {
        $this->data = [];
        $this->length = $length;
        $this->count = 0;
    }


    public function getLength()
    {
        return $this->count;
    }


    public function push($value)
    {
        if ($this->count == $this->length) {
            return false;
        }
        $this->data[$this->count] = $value;
        $this->count++;


        return true;
    }


    public function pop()
    {
        if ($this->count == 0) {
            return false;
        }
        $tmp = $this->data[$this->count - 1];
        $this->count--;


        return $tmp;
    }


    public function printSelf()
    {
        if ($this->count == 0) {
            echo 'NULL',PHP_EOL;
        }
        for ($i = 0; $i < $this->count; $i++) {
            echo $this->data[$i] . '->';
        }
        echo 'NULL',PHP_EOL;


        return true;

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。

注意,这里存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这 n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)。

栈在函数调用中的应用

对于如下代码

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}


int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

函数调用栈的情况

栈在表达式求值中的应用

加减乘除四则运算,可以通过两个栈来实现。其中一个保存操作数的栈,另一个是保存运算符的栈。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

栈在括号匹配中的作用

我们假设表达式中只包含三种括号,圆括号 ()、方括号[]和花括号{},并且它们可以任意嵌套。比如,{[] ()[{}]}或[{()}([])]等都为合法格式,而{[}()]或[({)]为不合法的格式。现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?

这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。

如何实现浏览器的前进和后退功能

我们使用两个栈,X 和 Y,我们把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当我们点击前进按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中。当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。