札记之两个栈实现队列

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。

思路：

• 初始化2个栈，数据先进栈STACKA，出STACKA栈后进入STACKB，最后STACKB的出栈顺序即为出队列的顺序；
• 入队push：STACKA
• 出队pop: 如果STACKB中有数据，直接pop，若没有，则先将STACKAA的所有元素出栈，并入栈到STACKB，再pop

图示

代码实现

require 'linkstack.php'; 

class StackQueue
{
    private $stackA;
    private $stackB;

    public function __construct()
    {
        $this->stackA = new LinkedListStack(4);
        $this->stackB = new LinkedListStack(4);
    }

    public function push($item)
    {
        $this->stackA->push($item);
    }

    public function pop()
    {
       if ($this->stackB->stack->head == NULL) {
            while($this->stackA->stack->head) {
                $this->stackB->push($this->stackA->pop());
            }
        }
        return $this->stackB->pop();
    }

    public function display()
    {
        print_r($this->stackA);
        print_r($this->stackB);
    }
}
$queue = new StackQueue();
$queue->push(1111);
$queue->push(2222);
$queue->push(3333);
$queue->push(4444);
print_r($queue->pop());
echo PHP_EOL;
print_r($queue->pop());
echo PHP_EOL;
print_r($queue->pop());

结果：

1111
2222
3333

栈代码地址

札记之PHP栈的实现：[http://www.wangdengke.com/2019/07/17/札记之PHP栈的实现