堆栈.md

:数据结构线性表之堆栈

吴亲库里 库里的深夜食堂

​

✏️一.栈的特点

栈是仅限在栈顶进行插入和删除的线性表.对栈来说,表尾端称之为栈顶,表头端称之为栈底.假设栈S=(a1,a2,a3,a4,a5....an),那么a1为栈的栈底,an为栈顶元素.对栈的操作是按照后进先出的原则,因此栈又称之为(LIFO)数据结构.

✏️二.栈的表示和实现

和线性表类似,栈也有两种存储的方式.顺序栈,即栈的存储是利用一组连续的存储单元依次存放自栈底到栈顶的元素.同时还要定义指针top指向栈顶元素在顺序栈中的位置.通常的做法是top=0表示空栈.一般在使用栈的过程中难以预料所需要的空间大小.所以预先分配大小的容量,当栈的使用空间不够时,再进行动态的扩容.top作为栈顶的指针,初始的时候指向栈底,当有元素入栈时,top自增,当从栈中删除一个元素时,top--,然后删除元素,所以top始终指向栈顶的下一个空位置.

LOC(ai+1)=LOC(ai)+L      //申明 这里的i,i+1是下标

线性结构的顺序表示以元素在计算机中的物理位置相邻来表示逻辑位置相邻，相邻两个元素之间的位置以物理位置的角度分析就是相差一位，只要确定了存储线性表的起始位，那么我们就能任意存储线性表中元素，下图具体表示

​

✏️三.栈的使用场景

栈的使用场景很多,例如idea的撤销回退功能,浏览器前进和后退功能.数制的转换,表达式求值,八皇后.......

✏️四.用栈实现代码

/**
 * 使用栈实现十进制转8精制,其他转换类似
 */
function tenChageEight($num)
{
    $data=[];
    while($num) {
        $val = $num % 8;
        $num = intval(floor($num / 8));
        array_unshift($data, $val);
    }
    $data2=[];
    while(!empty($data)){
        array_push($data2,array_shift($data));
    }
    return implode($data2);
}
var_dump(tenChageEight(1348));

---

class Stack
{
    private $stack=[];
    private $size=0;
    public function __construct($size)
{
        $this->size=$size;
    }

    /**
     *推入栈顶
     */
    public function push($value)
{
        if(count($this->stack)>=$this->size){
            return false;
        }
        array_unshift($this->stack,$value);

    }
    /**
     *出栈
     */
    public function pop()
{
        if($this->size==0){
            return false;
        }
        array_shift($this->stack);
    }
    /**
     *获取栈顶元素
     */
    public function top()
{
        if($this->size==0){
            return false;
        }
        return current($this->stack);
    }

    public function data()
{
        return $this->stack;
    }

}

$stack=new Stack(10);
$stack->push(2);
$stack->push(10);
$stack->push(8);
$stack->pop();
var_dump($stack->top());
var_dump($stack->data());

联系

​