栈：后进先出、先进后出

队列：先进先出，后进后出

下面我们使用PHP来实现一下：

栈

class Stack{
	private $_list;
	public function __construct(){

		$this->_list=[];
	}

	public function append($item){
		array_push($this->_list,$item);

		return sizeof($this->_list);
	}

	public function pop(){
		return array_pop($this->_list);
	}
	

	public function list(){
		return $this->_list;
	}

	public function is_empty(){
		return empty($this->_list)?true:false;	
	}

	public function length(){
		return sizeof($this->_list);
	}

}


$stack=new Stack();

$stack->append(12);
$stack->append(13);
$stack->append(14);
$stack->append(15);


print_r($stack->list());

print_r($stack->append(19));

print_r($stack->list());
var_dump($stack->is_empty());
var_dump($stack->length());

var_dump($stack->pop());
var_dump($stack->pop());
var_dump($stack->pop());
var_dump($stack->pop());

队列

<?php


class Queue{
	private $_list;
	public function __construct(){

		$this->_list=[];
	}


	public function append($item){
		array_push($this->_list,$item);

		return sizeof($this->_list);
	}

	public function pop(){
		//return array_shift($this->_list);
		return array_splice($this->_list,0,1);
	}

	/**
	 * 在哪里插入一个数据
	 * [insert description]
	 * @param  [type] $index index 位置 
	 * @param  [type] $item  插入的元素 
	 * @return [type]        [description]
	 */
	public function insert($index,$item){
		array_splice($this->_list,$index,0,$item);
	}

	public function list(){
		return $this->_list;
	}

	public function is_empty(){
		return empty($this->_list)?true:false;	
	}

	public function length(){
		return sizeof($this->_list);
	}

}


$stack=new Queue();

$stack->append(12);
$stack->append(13);
$stack->append(14);
$stack->append(15);


print_r($stack->list());


print_r($stack->insert(1,19));

print_r($stack->list());


exit;

var_dump($stack->length());

var_dump($stack->pop());

print_r($stack->list());

var_dump($stack->pop());

print_r($stack->list());


var_dump($stack->pop());

print_r($stack->list());


 

 

 
var_dump($stack->is_empty());
var_dump($stack->length());


var_dump($stack->pop());
var_dump($stack->pop());
var_dump($stack->pop());

队列中核心方法：

list() 返回列表中元素的个数

append($item) 添加一个元素

pop() 抛出一个元素

insert($index,$item) 在指定位置添加一个元素

is_empty() 判断元素是否为空

length()  返回列表中元素的个数

核心道理：由于项目是php的，就使用php中提供的数组去实现。

队列：先进先出，后进后出，意思：一头进，另一头出。 array_push() , array_shift() 

栈：后进先出，意思：从一头进一头出，犹如接水，后来流进来的水，先被喝到。

array_push() 进  array_pop() 这样就实现了栈。

说：为什么当数组很大的时候，array_pop 很快  array_shift 很慢？ 这是时间复杂度的影响。

对，就是array_shift操作后，数组的键值变了。这就是array_shift为什么慢的原因了。因为array_shift操作数组会对数字键值，重新从0开始重建。

每次移出一个元素后，就得遍历数组中的所有元素。array_pop就不会了。一个是O(1)，一个是O(n)的复杂度，数组大了之后，效果就很明显了。