什么是队列？

队列是一种特殊的线性表，它只允许在表的前端，可以称之为front，进行删除操作；而在表的后端，可以称之为rear进行插入操作。

队列和堆栈一样，是一种操作受限制的线性表，和堆栈不同之处在于：队列是遵循“先进先出”原则，而堆栈遵循的是“先进后出”原则。队列进行插入操作的端称为队尾，进行删除操作的称为队头，只允许在队尾进行插入操作，在队头进行删除操作。

队列的数据元素又称为队列元素，在队尾中插入一个元素称为入队，在队头删除一个元素称为出队。

实现代码：

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

运行结果如下：

Tags: php队列步骤

分享到：