Two way Queue Class Instance Implemented by php
- 2021-07-21 07:46:31
- OfStack
This article describes the example of php implementation of the two-way queue class and its usage, for PHP data structure and algorithm learning has a good reference value. Share it for your reference. The specific analysis is as follows:
(deque, full name double-ended queue) is a data structure with the properties of queue and stack. Elements in a bi-directional queue can be ejected from both ends, limiting insert and delete operations to both ends of the table.
In practical use, there can also be two-way queues with limited output (that is, one endpoint allows insertion and deletion, and the other endpoint only allows insertion) and two-way queues with limited input (that is, one endpoint allows insertion and deletion, and the other endpoint only allows deletion). However, if the elements inserted from a certain endpoint can only be deleted from that endpoint, the bidirectional queue will degenerate into two adjacent stacks at the bottom of the stack.
The DEQue. class. php class files are as follows:
<?php
/** php Two-way queue. Support limited queue length, limited input, limited output, and output must be the same as input
* Date: 2014-04-30
* Author: fdipzone
* Ver: 1.0
*
* Func:
* public frontAdd Front-end column entry
* public frontRemove Front-end dequeue
* public rearAdd Back-end column entry
* pulbic rearRemove Back-end dequeue
* public clear Empty alignment
* public isFull Determine whether the alignment column is full
* private getLength Gets alignment column length
* private setAddNum Record into column , Called when the output depends on the input
* private setRemoveNum Record out , Called when the output depends on the input
* private checkRemove Check whether the output depends on the input
*/
class DEQue{ // class start
private $_queue = array(); // Column alignment
private $_maxLength = 0; // Maximum column length, 0 Indicate unlimited
private $_type = 0; // Alignment column type
private $_frontNum = 0; // Number of front-end inserts
private $_rearNum = 0; // Number of back-end inserts
/** Initialization
* @param $type Alignment column type
* 1: Both ends can be input and output
* 2: The front end can only input, and the back end can input and output
* 3: The front end can only output, and the back end can input and output
* 4: Back-end can only input, front-end can input and output
* 5: The back end can only output, and the front end can input and output
* 6: Both ends can be input and output, and the input can only be output from which end
* @param $maxlength Maximum length of alignment column
*/
public function __construct($type=1, $maxlength=0){
$this->_type = in_array($type, array(1,2,3,4,5,6))? $type : 1;
$this->_maxLength = intval($maxlength);
}
/** Front-end column entry
* @param Mixed $data Data
* @return boolean
*/
public function frontAdd($data=null){
if($this->_type==3){ // Front-end input limit
return false;
}
if(isset($data) && !$this->isFull()){
array_unshift($this->_queue, $data);
$this->setAddNum(1);
return true;
}
return false;
}
/** Front-end dequeue
* @return Array
*/
public function frontRemove(){
if($this->_type==2){ // Front-end output limit
return null;
}
if(!$this->checkRemove(1)){ // Check whether you depend on input
return null;
}
$data = null;
if($this->getLength()>0){
$data = array_shift($this->_queue);
$this->setRemoveNum(1);
}
return $data;
}
/** Back-end column entry
* @param Mixed $data Data
* @return boolean
*/
public function rearAdd($data=null){
if($this->_type==5){ // Backend input limit
return false;
}
if(isset($data) && !$this->isFull()){
array_push($this->_queue, $data);
$this->setAddNum(2);
return true;
}
return false;
}
/** Back-end dequeue
* @return Array
*/
public function rearRemove(){
if($this->_type==4){ // Backend output limit
return null;
}
if(!$this->checkRemove(2)){ // Check whether you depend on input
return null;
}
$data = null;
if($this->getLength()>0){
$data = array_pop($this->_queue);
$this->setRemoveNum(2);
}
return $data;
}
/** Empty alignment
* @return boolean
*/
public function clear(){
$this->_queue = array();
$this->_frontNum = 0;
$this->_rearNum = 0;
return true;
}
/** Determine whether the alignment column is full
* @return boolean
*/
public function isFull(){
$bIsFull = false;
if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){
$bIsFull = true;
}
return $bIsFull;
}
/** Gets the current alignment length
* @return int
*/
private function getLength(){
return count($this->_queue);
}
/** Record into column , Called when the output depends on the input
* @param int $endpoint Endpoint 1:front 2:rear
*/
private function setAddNum($endpoint){
if($this->_type==6){
if($endpoint==1){
$this->_frontNum ++;
}else{
$this->_rearNum ++;
}
}
}
/** Record out , Called when the output depends on the input
* @param int $endpoint Endpoint 1:front 2:rear
*/
private function setRemoveNum($endpoint){
if($this->_type==6){
if($endpoint==1){
$this->_frontNum --;
}else{
$this->_rearNum --;
}
}
}
/** Check whether the output depends on the input
* @param int $endpoint Endpoint 1:front 2:rear
*/
private function checkRemove($endpoint){
if($this->_type==6){
if($endpoint==1){
return $this->_frontNum>0;
}else{
return $this->_rearNum>0;
}
}
return true;
}
} // class end
?>
The sample code for demo. php is as follows:
<?php
require "DEQue.class.php";
// Example 1
$obj = new DEQue(); // Both front and back ends can be entered, with unlimited length
$obj->frontAdd('a'); // Front-end column entry
$obj->rearAdd('b'); // Back-end column entry
$obj->frontAdd('c'); // Front-end column entry
$obj->rearAdd('d'); // Back-end column entry
// The array after entering the column should be cabd
$result = array();
$result[] = $obj->rearRemove(); // Back-end dequeue
$result[] = $obj->rearRemove(); // Back-end dequeue
$result[] = $obj->frontRemove(); // Front-end dequeue
$result[] = $obj->frontRemove(); // Front-end dequeue
print_r($result); // Exit order should be dbca
// Example 2
$obj = new DEQue(3, 5); // The front end can only output, and the back end can input and output, with the maximum length 5
$insert = array();
$insert[] = $obj->rearAdd('a');
$insert[] = $obj->rearAdd('b');
$insert[] = $obj->frontAdd('c'); // Because the front end can only output, it will return here false
$insert[] = $obj->rearAdd('d');
$insert[] = $obj->rearAdd('e');
$insert[] = $obj->rearAdd('f');
$insert[] = $obj->rearAdd('g'); // Exceeds length, returns false
var_dump($insert);
// Example 3
$obj = new DEQue(6); // Output depends on input
$obj->frontAdd('a');
$obj->frontAdd('b');
$obj->frontAdd('c');
$obj->rearAdd('d');
$result = array();
$result[] = $obj->rearRemove();
$result[] = $obj->rearRemove(); // Because the output depends on the input, this returns NULL
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
var_dump($result);
?>
Click here to download the complete example code.
I hope this paper is helpful to the study of PHP program algorithm design.