<?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 = array()) { $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); } }