[Bài đọc] Queue

Queue (hàng đợi) là một cấu trúc dữ liệu danh sách, trong đó việc thêm và lấy các phần tử được thực hiện theo quy tắc FIFO(Fist-In/First-Out), có nghĩa là phần tử nào được thêm vào đầu tiên thì được lấy ra đầu tiên. Nguyên tắc này cũng được gọi là LILO, có nghĩa là phần tử nào được thêm vào sau cùng thì được lấy ra sau cùng.

Hãy tưởng tượng Queue như một hàng đợi ở các quầy mua hàng hoặc ở sân bay. Người nào đến trước thì được phục vụ trước (và xong việc trước), người nào đến sau thì được phục vụ sau, lần lượt như vậy.

Các thao tác thông dụng của Queue bao gồm:

• init – tạo một hàng đợi
• enqueue – thêm một phần tử vào phần cuối (đuôi – tail) của hàng đợi.
• dequeue – lấy ra phần tử đầu tiên (đầu – head) của hàng đợi (đầu).
• isEmpty – trả về true/false để xác định xem hàng đợi này có chứa phần tử nào hay không.

Triển khai Queue

Có thể triển khai một Queue đơn giản như bên dưới:

Lớp Element đại diện cho 1 phần tử trong Queue:

class Element{  
  public $value; 
   public $next;}

Thuộc tính $value chứa giá trị của phần tử, thuộc tính $next trỏ đến phần tử phía sau nó.

Lớp Queue:

class Queue
{ 
   private $font = null; 
   private $back = null;  
  /**   
  * Check whether the queue is empty or not  
   * @return boolean   
  * public function isEmpty(){ return false; }  //stub  
   */   
 public function isEmpty() 
   {       
 return $this->font == null; 
   } 
   /**    
 * Insert element at the back of queue 
    * @param $value 
    * public function enqueue($value){} //stub   
  */    public function enqueue($value)    {   
     $oldBack = $this->back;   
     $this->back = new Element(); 
       $this->back->value = $value;   
     if ($this->isEmpty()) {     
       $this->font = $this->back;   
     } else {      
      $oldBack->next = $this->back;     
   }   
 }  
  /**   
  * Remove element from the font of queue   
  * @return $value  
   * public function dequeue(){ return 0; } 
//stub     
*/    public function dequeue()    {  
      if ($this->isEmpty()) {       
     return null;      
  }        $removedValue = $this->font->value; 
       $this->font = $this->font->next;  
      return $removedValue;    }
}

Bây giờ, chúng ta có thể sử dụng Queue:

$queue = new Queue();
$queue->enqueue("start");
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
$queue->enqueue(4);
$queue->enqueue("End");
while(!$queue->isEmpty())
{  echo $queue->dequeue()."\n";}