力扣- 用队列实现栈(PHP实现)

[collinxz-coder]

原题

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

题解

栈是一种后进先出的数据结构，栈内元素从顶端压入，从顶端弹出。而队列则与栈相反是先进先出的数据结构，队列中元素从后端压入，从前端弹出。

栈

队列

我们使用 PHP 中的数组来模拟队列，为了遵循先进先出的规则，我们使用 array_shift() 函数来弹出元素。

使用两个 list 来实现栈

为了满足栈的特性，我们需要维护两个数组 q1 和 q2，同时使用了一个额外的变量来保存栈顶元素。

class Stack
{
    private $q1 = [];
    private $q2 = [];
    private $top;
}

压入元素

在压入元素的时候，我们只需要直接往 q1 中追加元素并且将刚追加的元素值赋值给 $top。

public function push($x) 
{
    $this->q1[] = $x;
    $this->top = $x;
}

弹出元素

这个算法的核心在于弹出元素。由于队列是先进先出，而栈则是后进先出，所以我们需要先将 q1 中第一个元素~倒数第二个元素先弹出来放到 q2 中保存，然后剩下的这个元素就是栈要弹出的元素。最后再将 q1 和 q2 的值交换一下即可。

function pop() 
{
    while (count($this->q1) > 1) {
        $this->top = array_shift($this->q1);
        $this->q2[] = $this->top;
    }
    $value = array_shift($this->q1);
    $temp = $this->q1;
    $this->q1 = $this->q2;
    $this->q2 = $temp;
    if (count($this->q1) <= 0) $this->top = null;
    return $value;
}

需要注意的是，我们在每次弹出元素时，都重新给 top 赋值了，并且判断了 q1 是否为空，如果为空，则 top 的值也应该为 null。

完整代码

class MyStack {
    public $q1 = [];
    public $q2 = [];
    public $top;

    /**
     * Initialize your data structure here.
     */
    function __construct() {

    }

    /**
     * Push element x onto stack.
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->q1[] = $x;
        $this->top = $x;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     * @return Integer
     */
    function pop() {
        while (count($this->q1) > 1) {
            $this->top = array_shift($this->q1);
            $this->q2[] = $this->top;
        }
        $value = array_shift($this->q1);
        $temp = $this->q1;
        $this->q1 = $this->q2;
        $this->q2 = $temp;
        if (count($this->q1) <= 0) $this->top = null;
        return $value;
    }

    /**
     * Get the top element.
     * @return Integer
     */
    function top() {
        return $this->top;
    }

    /**
     * Returns whether the stack is empty.
     * @return Boolean
     */
    function empty() {
        return count($this->q1) <= 0;
    }
}

使用一个 list 来实现栈

除了使用第二个数组来暂存队列的值，我们还可以直接使用一个数组来实现栈。

压入

当我们将一个元素从队列入队的时候，根据队列的性质这个元素会存在队列的后端。但当我们实现一个栈的时候，最后入队的元素应该在前端，而不是在后端。为了实现这个目的，每当入队一个新元素的时候，我们可以把队列的顺序反转过来。

function push($x) {
    $this->q1[] = $x;
    for ($i = count($this->q1); $i > 1; $i--) {
        $this->q1[] = array_shift($this->q1);
    }
}

**注意：**上面代码中，一定要注意 for 循环中的 $i > 1，因为我们刚添加的数据在队列的后端，所以我们把其前面的元素全都弹出重新压入到当前元素的后面，这样就实现了栈的入队在前端的特性。

其它几个方法就不是那么重要了，我就直接把代码贴出来。

class MyStack {
    public $q1 = [];

    /**
     * Initialize your data structure here.
     */
    function __construct() {

    }

    /**
     * Push element x onto stack.
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->q1[] = $x;
        for ($i = count($this->q1); $i > 1; $i--) {
            $value = array_shift($this->q1);
            $this->q1[] = $value;
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     * @return Integer
     */
    function pop() {
        return array_shift($this->q1);
    }

    /**
     * Get the top element.
     * @return Integer
     */
    function top() {
        return count($this->q1) > 0 ? $this->q1[0] : null; 
    }

    /**
     * Returns whether the stack is empty.
     * @return Boolean
     */
    function empty() {
        return count($this->q1) <= 0;
    }
}