代码随想录算法训练营第八天 | leetcode：用栈实现队列,用队列实现栈

_zzh 的个人博客 / 73 / 0 / 创建于 2个月前 / 更新于 2个月前

Problem: 232. 用栈实现队列

#需要注意的地方

出栈时，需要把入栈的数据全部装进出栈，否则会导致数据错误。

解题方法

使用两个栈，一个入栈对应队列进数据，一个出栈对应队列出数据。

复杂度

时间复杂度:

push和empty为O(1), pop和peek为O(n)

空间复杂度:

O(n)

code

 class MyQueue {
    /**
     */
    private $stackIn;
    private $stackOut;
    function __construct() {
        $this->stackIn = new SplStack();
        $this->stackOut = new SplStack();
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->stackIn->push($x);
    }

    /**
     * @return Integer
     */
    function pop() {
        $res = [];
        //判断出栈是否为空，为空查询入栈是否有数据，有数据则全部转入到出栈。
        //这里处理的是栈的top与pop不是队列的。
        if($this->stackOut->isEmpty()){
            while(!$this->stackIn->isEmpty()){
                // $this->stackOut->push($this->stackIn->top());
                // $this->stackIn->pop();
                $this->stackOut->push($this->stackIn->pop());
            }
        }
        $res = $this->stackOut->pop();
        // $this->stackOut->pop();
        return $res;
    }

    /**
     * @return Integer
     */
    function peek() {
        $res = $this->pop();
        $this->stackOut->push($res);
        return $res;
    }

    /**
     * @return Boolean
     */
    function empty() {
        //判断队列是否为空需要把入栈和出栈一起判断
        return $this->stackIn->isEmpty() && $this->stackOut->isEmpty();
    }
}

Problem: 225. 用队列实现栈

需要注意的地方

SplQueue继承自SplDoublyLinkedList。因此，SplQueue的对象支持方法push（）和pop（）。但请注意，如果您在SplQueue对象上使用push（）和pop（）方法，它的行为就像堆栈而不是队列。因此，请确保在SplQueue对象上只使用入队列enqueue()和出队列dequeue()方法，而不是push（）和pop（）方法

另外出队列方向是头部，栈顶是栈的头部，所以当入队列后，队列的尾部对应栈顶，但这里因为SplQueue继承自SplDoublyLinkedList。它的行为就像堆栈而不是队列。top()与bottom()指向也符合堆栈而不是队列。因此当需要指向栈头部时，直接使用top()即可。

解题方法

关键点：把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈顶所需要弹出的数据。如此循环，即弹出顺序与栈相同。

复杂度

时间复杂度:

pop为O(n)，其他为O(1)

空间复杂度:

O(n)

code

class MyStack {
    private $queue;
    /**
     * SplQueue继承自SplDoublyLinkedList。因此，SplQueue的对象支持方法push（）和pop（）。
     * 但请注意，如果您在SplQueue对象上使用push（）和pop（）方法，它的行为就像堆栈而不是队列。
     * top()与bottom()指向也符合堆栈而不是队列
     * 因此，请确保在SplQueue对象上只使用入队列enqueue()和出队列dequeue()方法，而不是push（）和pop（）方法。
     */
    function __construct() {
        $this->queue = new SplQueue();
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->queue->enqueue($x);
    }

    /**
     * @return Integer
     */
    function pop() {
        $result = [];
        $size = $this->queue->count();
        //需要保留末尾元素 先减减
        $size--;
        //把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈所需要弹出的数据
        while($size--){
            $this->queue->enqueue($this->queue->dequeue());
        }
        $result = $this->queue->dequeue();
        return $result;
    }

    /**
     * @return Integer
     */
    function top() {
        return $this->queue->top();
    }

    /**
     * @return Boolean
     */
    function empty() {
        return $this->queue->isEmpty();
    }
}