php数组实现队列、栈等数据结构

jokerchu

　　数据结构从宏观的概念层次讲呢，就是一组数据元素及之间的关系。编程的世界里，最简单也最经典的数据结构就是栈和队列。
　　栈，体现的是后进先出，即LIFO。
　　队列，体现的是先进先出，即FIFO。
　　php为数组定义了太多的操作函数，可能phper们常用的也就那么几个，list、each、count、next、prev、reset、end、sort、rsort、in_array、array_shift、array_unshift、array_pop、array_push等等。
　　现在，咱就用几个常用函数来实现栈、队列。
　　栈
　　array_pop() //尾出
　　array_push() //尾进
　　或
　　array_shift()//头进
　　array_unshift()//头出
　　以上两组操作都能实现FIFO的算法，拿一个经典的例子测试下。
　　用例：验证一个数学算式是否正确，比如{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}。
　　分析：对于一个算式的正确与否，就是体现在，各种括号的匹配上，括号完全匹配，算式就没问题，那怎么来检验一个算式里的括号匹配呢，碰到过很多人想着用正则。我是想不通这正则怎么写，怎么实现嵌套关系。这个时候栈就派上用场了。看下边代码。

<?php
function check($arg)
{
$arr = str_split($arg);
$leftBracket = array('{','[','(');//左括号
$rightBracket = array('}',']',')');//右括号
$stack = array();
reset($arr);
while (list($key,$value)=each($arr))
{
if (in_array($value, $leftBracket,TRUE))
{//左括号入栈
array_push($stack, $value);
}
elseif (in_array($value, $rightBracket))
{//右括号跟栈顶比较
$stackTop = end($stack);//取栈顶
if(isset($stackTop) && !empty($stackTop))
{
if(array_search($value, $rightBracket) === array_search($stackTop, $leftBracket))
{//已匹配成功的出栈
array_pop($stack);
}
else
{//匹配失败
return  false;
}
}
else
{//右括号多余左括号
return  false;
}
}
}
if(!empty($stack))
{//左括号多余右括号
return  false;
}
else
{
return  true;
}
}
$test = '{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}';
print check($test);
?>
　　上述代码中的栈，是由array_pop和array_push实现的；同理，也可以用array_shift和array_unshift实现。
　　队列
　　array_shift() //头出
　　array_push() //尾进
　　或
　　array_unshift //头进
　　array_pop //尾出
　　未完待续……