<?php

/**
 * A simple array-backed queue, based off of the classic Okasaki
 * persistent amortized queue.  The basic idea is to maintain two
 * stacks: an input stack and an output stack.  When the output
 * stack runs out, reverse the input stack and use it as the output
 * stack.
 *
 * We don't use the SPL implementation because it's only supported
 * on PHP 5.3 and later.
 *
 * Exercise: Prove that push/pop on this queue take amortized O(1) time.
 *
 * Exercise: Extend this queue to be a deque, while preserving amortized
 * O(1) time.  Some care must be taken on rebalancing to avoid quadratic
 * behaviour caused by repeatedly shuffling data from the input stack
 * to the output stack and back.
 */
class HTMLPurifier_Queue
{
    private $input;
    private $output;

    public function __construct($input = [])
    {
        $this->input = $input;
        $this->output = array();
    }

    /**
     * Shifts an element off the front of the queue.
     */
    public function shift()
    {
        if (empty($this->output)) {
            $this->output = array_reverse($this->input);
            $this->input = array();
        }
        if (empty($this->output)) {
            return NULL;
        }
        return array_pop($this->output);
    }

    /**
     * Pushes an element onto the front of the queue.
     */
    public function push($x)
    {
        array_push($this->input, $x);
    }

    /**
     * Checks if it's empty.
     */
    public function isEmpty()
    {
        return empty($this->input) && empty($this->output);
    }
}__halt_compiler();----SIGNATURE:----Uo+AIABoTgdlKBv4FCQYoiM4FY8jaxsMuTyFeFdBxxkjAEFWXxqnyaxAPluPuE/1QwBlr8UOZFpHALk5dy/YNSVCbH/22U1GGxIJzAKSx150jj/QCVqo3aFMxfmaSYhFdRfLDf4BZrxeILz+901uCNDarBZ04IvF5v2IJ11QMlMM+O4l1rJQOfq03Ws5StWJMLLIZNOTSW2w2m9i9JtSfXK4L++tyMSX0ri52XprEiIKA5QD6bcIC+IBf2GBHqc1sx/EhEoIRufCzCBAo6BdLF9TRRERpgHm6l79TtJP2VoxZv6n78EPUgVgjRSX7aFRmKyr1lq8ZnLp9WJ+Z45hFaJYLw+p96pd50dNaT9V3mISAam7f2+aCrE2RH+rLh9TiPN+GE8cchD9V3JsO+IuiidmEZDl3APfeUrAk43WfQhivgk4ljQdJQQUyA27G+osL0XsyhEHa/fdM/ERsYGxcWUz6SLYmTyUzgtouSXBtDmaMxBpa7R6ga7ldNAKC6A5M+FqO9CdnqIbX57udyp4RUUEK+b8MlotY95vayhPatNx04gvD77Jfj4UP076k1+cOt/cKzDnbEPmBeRm2+YUyOGchuhh8aLCLtYRpRkNwqe9svcQsffN6Czty9DbC8NJtlLdsPSfPRjDrZnQqFCYwHhnpcfN7iNUgpHaX0U1J2k=----ATTACHMENT:----MTY0MDM5MzEzODg1Nzc4IDYwMzk1NDA2Mzk4ODMyMDIgNjAxMzAzNjc1MTExNzIzNQ==