当前位置:首页 > PHP教程 > php高级应用 > 列表

如何用PHP实现队列算法

发布:smiling 来源: PHP粉丝网  添加日期:2020-03-30 22:36:49 浏览: 评论:0 

本篇文章主要讲述的是用PHP实现队列算法,具有一定的参考价值,有需要的朋友可以了解一下。

队列是一种特殊的线性表,它只允许在表的前端,可以称之为front,进行删除操作;而在表的后端,可以称之为rear进行插入操作。队列和堆栈一样,是一种操作受限制的线性表,和堆栈不同之处在于:队列是遵循“先进先出”原则,而堆栈遵循的是“先进后出”原则。队列进行插入操作的端称为队尾,进行删除操作的称为队头,只允许在队尾进行插入操作,在队头进行删除操作。

队列的数据元素又称为队列元素,在队尾中插入一个元素称为入队,在队头删除一个元素称为出队。具体实现参考代码:

  1. <?php 
  2.  
  3. /** 
  4.  
  5. *  php队列算法 
  6.  
  7. *   
  8.  
  9. *  Create On 2010-6-4 
  10.  
  11. *  Author Been 
  12.  
  13. *  QQ:281443751 
  14.  
  15. *  Email:binbin1129@126.com 
  16.  
  17. **/ 
  18.  
  19. class data { 
  20.  
  21.     //数据 
  22.  
  23.     private $data
  24.  
  25.       
  26.  
  27.     public function __construct($data){ 
  28.  
  29.         $this->data=$data
  30.  
  31.         echo $data.":哥进队了!<br>"
  32.  
  33.     } 
  34.  
  35.       
  36.  
  37.     public function getData(){ 
  38.  
  39.         return $this->data; 
  40.  
  41.     } 
  42.  
  43.     public function __destruct(){ 
  44.  
  45.         echo $this->data.":哥走了!<br>"
  46.  
  47.     } 
  48.  
  49.  
  50. class queue{ 
  51.  
  52.     protected $front;//队头 
  53.  
  54.     protected $rear;//队尾 
  55.  
  56.     protected $queue=array('0'=>'队尾');//存储队列 
  57.  
  58.     protected $maxsize;//最大数 
  59.  
  60.       
  61.  
  62.     public function __construct($size){ 
  63.  
  64.         $this->initQ($size); 
  65.  
  66.     } 
  67.  
  68.     //初始化队列 
  69.  
  70.     private function initQ($size){ 
  71.  
  72.         $this->front=0; 
  73.  
  74.         $this->rear=0; 
  75.  
  76.         $this->maxsize=$size
  77.  
  78.     } 
  79.  
  80.     //判断队空 
  81.  
  82.     public function QIsEmpty(){ 
  83.  
  84.         return $this->front==$this->rear; 
  85.  
  86.     } 
  87.  
  88.     //判断队满 
  89.  
  90.     public function QIsFull(){ 
  91.  
  92.         return ($this->front-$this->rear)==$this->maxsize; 
  93.  
  94.     } 
  95.  
  96.     //获取队首数据 
  97.  
  98.     public function getFrontDate(){ 
  99.  
  100.         return $this->queue[$this->front]->getData(); 
  101.  
  102.     } 
  103.  
  104.     //入队 
  105.  
  106.     public function InQ($data){ 
  107.  
  108.         if($this->QIsFull())echo $data.":我一来咋就满了!(队满不能入队,请等待!)<br>"
  109.  
  110.         else { 
  111.  
  112.             $this->front++; 
  113.  
  114.             for($i=$this->front;$i>$this->rear;$i--){ 
  115.  
  116.                 //echo $data; 
  117.  
  118.                 if($this->queue[$i])unset($this->queue[$i]); 
  119.  
  120.                 $this->queue[$i]=$this->queue[$i-1]; 
  121.  
  122.             } 
  123.  
  124.             $this->queue[$this->rear+1]=new data($data); 
  125.  
  126.             //print_r($this->queue); 
  127.  
  128.             //echo $this->front; 
  129.  
  130.             echo '入队成功!<br>'
  131.  
  132.         } 
  133.  
  134.     } 
  135.  
  136.     //出队 
  137.  
  138.     public function OutQ(){ 
  139.  
  140.         if($this->QIsEmpty())echo "队空不能出队!<br>"
  141.  
  142.         else
  143.  
  144.             unset($this->queue[$this->front]); 
  145.  
  146.             $this->front--; 
  147.  
  148.             //print_r($this->queue); 
  149.  
  150.             //echo $this->front; 
  151.  
  152.             echo "出队成功!<br>"
  153.  
  154.         } 
  155.  
  156.     } 
  157.  
  158.  
  159. $q=new queue(3); 
  160.  
  161. $q->InQ("小苗"); 
  162.  
  163. $q->InQ('马帅'); 
  164.  
  165. $q->InQ('溜冰'); 
  166.  
  167. $q->InQ('张世佳'); 
  168.  
  169. $q->OutQ(); 
  170.  
  171. $q->InQ("周瑞晓"); 
  172.  
  173. $q->OutQ(); 
  174.  
  175. $q->OutQ(); 
  176.  
  177. $q->OutQ(); 
  178.  
  179. $q->OutQ(); 

本案例中有两个类:

第一个是data类,用于实现数据的存放以及队列元素的入队出队情况;

第二个是queue类,用于队列元素的一些入队出队操作。

队列中包含四个属性:

front(队列的头部)

rear(队列的尾部)

maxsize(队列的长度,即队列元素个数)

queue(存放所有已入队队列元素的对象)

场景说明

1.初始化队列时,生成一个队列,传入一个参数作为maxsize初始化队列把队尾rear设为0,队头front也设为0,此时queue中只有0号元素,并且rear和front都指向它。

2.入队时,先需要判断队列是否已满(front-rear == maxsize),如果已满不可在插入,如果未满则允许插入。插入时,front自增,然后依次让队列所有元素向前移动一位(让出队尾位置以便插入新元素),然后生成新的data对象插入到队尾位置。

3.出队时,判断队列是否为空(front == rear),如果为空时,无法出队。如果不为空时,删除front指向的对象,并且front自减,完成出队。

运行结果如下:

  1. 小苗:哥进队了! 
  2.  
  3. 入队成功 
  4.  
  5. 马帅:哥进队了! 
  6.  
  7. 入队成功 
  8.  
  9. 溜冰:哥进队了! 
  10.  
  11. 入队成功 
  12.  
  13. 张世佳:我一来咋就满了!(队满不能入队,请等待!) 
  14.  
  15. 小苗:哥走了! 
  16.  
  17. 出队成功! 
  18.  
  19. 周瑞晓:哥进队了! 
  20.  
  21. 入队成功 
  22.  
  23. 马帅:哥走了! 
  24.  
  25. 出队成功! 
  26.  
  27. 溜冰:哥走了! 
  28.  
  29. 出队成功! 
  30.  
  31. 周瑞晓:哥走了! 
  32.  
  33. 出队成功! 
  34.  
  35. 队空不能出队! 
  36.  
  37. 队空不能出队! 

Tags: PHP队列算法

分享到: