下面我們將探討棧在 PHP 中的實(shí)現(xiàn)與應(yīng)用.
理解棧
棧是線性數(shù)據(jù)結(jié)構(gòu),遵循著后進(jìn)先出的原則.這意味著棧只有一個端口可以提供添加和移除元素.棧的插入操作叫做進(jìn)棧,刪除操作叫做出棧.
- 入棧
- 出棧
- 彈出頂端元素
- 是否為空
下面用 PHP 用不同的方法來實(shí)現(xiàn)棧.首先先用 PHP 內(nèi)建數(shù)組函數(shù),然后用其他數(shù)據(jù)結(jié)構(gòu)例如鏈表
使用 PHP 數(shù)組實(shí)現(xiàn)棧
interface IStack {
public function push(string $item);
public function pop();
public function top();
public function isEmpty();
}
class Stack implements IStack
{
private $limit;
private $stack;
public function __construct(int $limit = 20)
{
$this->limit = $limit;
$this->stack = [];
}
public function pop(): string
{
if ($this->isEmpty()) {
throw new UnderflowException('Stack is empty');
} else {
return array_pop($this->stack);
}
}
public function push(string $newItem)
{
if (count($this->stack) < $this->limit) {
array_push($this->stack, $newItem);
} else {
throw new OverflowException('Stack is full');
}
}
public function top(): string
{
return end($this->stack);
}
public function isEmpty(): bool
{
return empty($this->stack);
}
}
使用鏈表實(shí)現(xiàn)棧
use LinkedList;
class BookList implements Stack
{
private $stack;
public function __construct()
{
$this->stack = new LinkedList();
}
public function pop(): string
{
if ($this->isEmpty()) {
throw new UnderflowException('Stack is empty');
} else {
$lastItem = $this->top();
$this->stack->deleteLast();
return $lastItem;
}
}
public function push(string $newItem)
{
$this->stack->insert($newItem);
}
public function top(): string
{
return $this->stack->getNthNode($this->stack->getSize())->data;
}
public function isEmpty(): bool
{
return $this->stack->getSize() == 0;
}
}
使用 SplStack 類 實(shí)現(xiàn)棧
如果我們不想自己實(shí)現(xiàn)棧,可以使用已經(jīng)存在 SPL 來實(shí)現(xiàn).SplStack通過 SplDoublyLinkedList 來實(shí)現(xiàn).
$books = new SplStack();
$books->push("Introduction to PHP7");
$books->push("Mastering JavaScript");
$books->push("MySQL Workbench tutorial");
echo $books->pop() . "\n";
echo $books->top() . "\n";”
棧的使用
棧在實(shí)際應(yīng)用的開發(fā)中有很多使用,如:瀏覽器歷時等.下面看一下實(shí)際的問題
括號嵌套匹配
當(dāng)我們在解決數(shù)學(xué)計算表達(dá)式的問題,首先應(yīng)該考慮括號的正確嵌套.如:
8*(9-2) + {(4*5) / (2*2)}
5*8*9 / (3*2))
[{(2*7) + (15-3)]
上面的表達(dá)式只有一個是正確的,為了檢測是正確,我們可以使用棧來實(shí)現(xiàn).下面是實(shí)現(xiàn)的算法:
function expressionChecker(string $expression): bool
{
$valid = TRUE;
$stack = new SplStack();
for ($i = 0; $i < strlen($expression); $i++) {
$char = substr($expression, $i, 1);
switch ($char) {
case '(':
case '{':
case '[':
$stack->push($char);
break;
case ')':
case '}':
case ']':
if ($stack->isEmpty()) {
$valid = FALSE;
} else {
$last = $stack->pop();
if (($char == ")" && $last != "(")
|| ($char == "}" && $last != "{")
|| ($char == "]" && $last != "[")
) {
$valid = FALSE;
}
}
break;
}
if (!$valid)
break;
}
if (!$stack->isEmpty()) {
$valid = FALSE;
}
return $valid;
}
$expressions = [];
$expressions[] = "8 * (9 -2) + { (4 * 5) / ( 2 * 2) }";
$expressions[] = "5 * 8 * 9 / ( 3 * 2 ) )";
$expressions[] = "[{ (2 * 7) + ( 15 - 3) ]";
foreach ($expressions as $expression) {
$valid = expressionChecker($expression);
if ($valid) {
echo "Expression is valid \n";
echo "<br>";
} else {
echo "Expression is not valid \n";
echo "<br>";
}
}
返回
Expression is valid
Expression is not valid
Expression is not valid
