| 数据结构 | 入栈/入队 | 出栈/出队 | PHP 函数组合 |
| 栈 | 压入栈顶 | 弹出栈顶 | array_push / array_pop |
| 栈(另一种视角) | 压入栈底 | 弹出栈底 | array_unshift / array_shift |
| 队列 | 入队尾 | 出队头 | array_push / array_shift |
代码演示:四种组合
1. 栈顶操作(标准栈:LIFO)
<?php
$stack = ['Simon', 'Elaine'];
array_push($stack, 'Helen', 'Peter'); // 入栈
print_r($stack); // ['Simon','Elaine','Helen','Peter']
echo array_pop($stack) . "\n"; // 出栈 -> Peter
print_r($stack); // ['Simon','Elaine','Helen']
2. 栈底操作(逆向栈)
<?php
$stack = ['Simon', 'Elaine'];
array_unshift($stack, 'Helen', 'Peter'); // 入栈底
print_r($stack); // ['Helen','Peter','Simon','Elaine']
echo array_shift($stack) . "\n"; // 出栈底 -> Helen
print_r($stack); // ['Peter','Simon','Elaine']
3. 队列操作(FIFO)
<?php
$queue = ['A', 'B'];
array_push($queue, 'C', 'D'); // 入队尾
echo array_shift($queue) . "\n"; // 出队头 -> A
echo array_shift($queue) . "\n"; // -> B
// 剩余 ['C','D']
4. 双端队列
<?php
$deque = [];
array_push($deque, 'right1'); // 右入
array_unshift($deque, 'left1'); // 左入
echo array_pop($deque) . "\n"; // 右出 -> right1
echo array_shift($deque) . "\n"; // 左出 -> left1
性能对比(百万级元素)
| 操作 | 时间复杂度 | 相对耗时 | 备注 |
| array_push / array_pop | O(1) 均摊 | 基准 1x | 栈顶操作,内存连续,最快 |
| array_unshift / array_shift | O(n) | ~10-50x | 需整体平移元素,大数组慎用 |
结论:高性能栈/队列请始终使用 array_push + array_pop(栈)或 array_push + array_shift(队列)。仅在元素数 < 1000 或非热点路径时考虑 unshift/shift。
进阶:SplStack / SplQueue / SplDoublyLinkedList
PHP SPL 提供专业数据结构类,封装了指针操作,性能更稳定:
<?php
// 栈
$stack = new SplStack();
$stack->push('A');
$stack->push('B');
echo $stack->pop(); // B
// 队列
$queue = new SplQueue();
$queue->enqueue('A');
$queue->enqueue('B');
echo $queue->dequeue(); // A
// 双端队列
$dll = new SplDoublyLinkedList();
$dll->push('right');
$dll->unshift('left');
echo $dll->pop(); // right
echo $dll->shift(); // left
实战场景建议
- 递归替代:深度优先遍历(DFS)用栈显式模拟,避免栈溢出
- 表达式求值:后缀表达式计算器(逆波兰表达式)
- 浏览器历史:后退/前进栈
- 任务调度:队列实现异步任务分发
- 限流窗口:滑动窗口用双端队列维护时间戳
选择合适的函数组合或 SPL 类,让数据结构操作更清晰、高效。
copyright ©
萬盛學電腦網 all rights reserved