棧
定義
棧是一種操作受限的線性表，只支持在棧頂入棧（push）和出棧（pop）操作，有后進(jìn)先出的特性。可用數(shù)組或鏈表實(shí)現(xiàn)。
時(shí)間復(fù)雜度
入棧：O(1)
出棧：O(1)
隊(duì)列
定義
隊(duì)列是一種操作受限的線性表，只支持在隊(duì)頭出隊(duì)（dequeue）、隊(duì)尾入隊(duì)（enqueue）操作，有先進(jìn)先出的特性?？捎脭?shù)組或鏈表實(shí)現(xiàn)。
時(shí)間復(fù)雜度
入隊(duì)：O(1)
出隊(duì)：O(1)
各種隊(duì)列介紹
-
循環(huán)隊(duì)列
長(zhǎng)的像個(gè)環(huán)，比如插入操作，當(dāng)前狀態(tài)：n=8，head=3，tail=7。插入新元素后，tail后移，變?yōu)?。
在實(shí)現(xiàn)上和非循環(huán)隊(duì)列相比如下：類型 隊(duì)空 隊(duì)滿 非循環(huán)隊(duì)列 head==tail tail==n 循環(huán)隊(duì)列 head==tail (tail+1)%n==head 實(shí)現(xiàn)：
/**
* 循環(huán)隊(duì)列
* Class CircularQueue
*/
class CircularQueue
{
private $items = [];
private $n = 0;
private $head = 0;
private $tail = 0;
public function __construct($n)
{
$this->n = $n;
}
/**
* 入隊(duì)
* @param $v
* @return bool
*/
public function enqueue($v)
{
// 隊(duì)列滿了
if (($this->tail + 1) % $this->n == $this->head) {
return false;
}
$this->items[$this->tail] = $v;
$this->tail = ($this->tail + 1) % $this->n;
return true;
}
/**
* 出隊(duì)
* @return mixed|null
*/
public function dequeue()
{
// 隊(duì)列空了
if ($this->head == $this->tail) {
return null;
}
$v = $this->items[$this->head];
$this->head = ($this->head + 1) % $this->n;
return $v;
}
}
-
阻塞隊(duì)列
入隊(duì)、出隊(duì)操作可以阻塞。隊(duì)列為空時(shí)，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞，直到隊(duì)列中有數(shù)據(jù)了才返回；
隊(duì)列已滿，插入數(shù)據(jù)會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，再返回。 -
并發(fā)隊(duì)列
隊(duì)列的操作多線程安全。最簡(jiǎn)單的實(shí)現(xiàn)方法就是在入隊(duì)、出隊(duì)的方法上加鎖，同一時(shí)刻僅允許一個(gè)存或取操作，但是這樣鎖的粒度大，并發(fā)度比較低。
基于數(shù)組的循環(huán)隊(duì)列（避免數(shù)據(jù)搬移），利用 CAS（Compare And Swap 避免真正的去OS底層申請(qǐng)鎖資源）原子操作，可實(shí)現(xiàn)高效的無(wú)鎖并發(fā)隊(duì)列。
算法編程
-
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）。
- 思路：第一個(gè)棧接收push數(shù)據(jù)，需要pop時(shí)，把所有數(shù)據(jù)依次彈出到第二個(gè)棧，這樣第二個(gè)棧里的元素就是倒序的了，只要第二個(gè)棧不空，則可對(duì)第二個(gè)棧進(jìn)行pop、peek操作，如果第二個(gè)棧為空，則再將第一個(gè)棧的數(shù)據(jù)依次彈出到第二個(gè)棧。判空則是兩個(gè)棧都為空才為空。
答：
class MyQueue {
private $s1;
private $s2;
/**
* Initialize your data structure here.
*/
function __construct() {
$this->s1 = [];
$this->s2 = [];
}
/**
* Push element x to the back of queue.
* @param Integer $x
* @return NULL
*/
function push($x) {
array_push($this->s1, $x);
}
/**
* Removes the element from in front of queue and returns that element.
* @return Integer
*/
function pop() {
if (!empty($this->s2)) {
return array_pop($this->s2);
}
while (!empty($this->s1)) {
$x = array_pop($this->s1);
array_push($this->s2, $x);
}
return array_pop($this->s2);
}
/**
* Get the front element.
* @return Integer
*/
function peek() {
if (!empty($this->s2)) {
return end($this->s2);
}
while (!empty($this->s1)) {
$x = array_pop($this->s1);
array_push($this->s2, $x);
}
return end($this->s2);
}
/**
* Returns whether the queue is empty.
* @return Boolean
*/
function empty() {
return empty($this->s1) && empty($this->s2);
}
}
-
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
- 思路：push數(shù)據(jù)時(shí)，push到不為空的那個(gè)隊(duì)列，pop時(shí)將不為空的隊(duì)列數(shù)據(jù)依次彈出到另一個(gè)為空的隊(duì)列，直到不為空的隊(duì)列數(shù)據(jù)剩下一個(gè)，然后彈出即可。
答：
class MyStack {
private $q1;
private $q2;
/**
* Initialize your data structure here.
*/
function __construct() {
$this->q1 = [];
$this->q2 = [];
}
/**
* Push element x onto stack.
* @param Integer $x
* @return NULL
*/
function push($x) {
if (empty($this->q1)) {
array_unshift($this->q2, $x);
} else {
array_unshift($this->q1, $x);
}
}
/**
* Removes the element on top of the stack and returns that element.
* @return Integer
*/
function pop() {
if (empty($this->q2)) {
while (count($this->q1) > 1) {
$x = array_pop($this->q1);
array_unshift($this->q2, $x);
}
return array_pop($this->q1);
}
if (empty($this->q1)) {
while (count($this->q2) > 1) {
$x = array_pop($this->q2);
array_unshift($this->q1, $x);
}
return array_pop($this->q2);
}
}
/**
* Get the top element.
* @return Integer
*/
function top() {
if (empty($this->q2)) {
while (count($this->q1) > 0) {
if (count($this->q1) == 1) {
$top = $this->q1[0];
}
$x = array_pop($this->q1);
array_unshift($this->q2, $x);
}
return $top;
}
if (empty($this->q1)) {
while (count($this->q2) > 0) {
if (count($this->q2) == 1) {
$top = $this->q2[0];
}
$x = array_pop($this->q2);
array_unshift($this->q1, $x);
}
return $top;
}
}
/**
* Returns whether the stack is empty.
* @return Boolean
*/
function empty() {
return empty($this->q1) && empty($this->q2);
}
}
- 給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。返回滑動(dòng)窗口中的最大值。
答：
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer[]
*/
function maxSlidingWindow($nums, $k) {
if (empty($nums) || count($nums) < 2 || $k == 0) {
return $nums;
}
$window = new spldoublylinkedlist();
$res = [];
foreach ($nums as $i => $v) {
while (!$window->isEmpty() && $nums[$window->top()] <= $v) {
$window->pop();
}
$window->push($i);
if ($window->bottom() <= $i - $k) {
$window->shift();
}
if ($i >= $k - 1) {
$res[] = $nums[$window->bottom()];
}
}
return $res;
}
}
- 給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：- 左括號(hào)必須用相同類型的右括號(hào)閉合。
- 左括號(hào)必須以正確的順序閉合。
class Solution {
/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
$stack = [];
$map = [')' => '(', ']' => '[', '}' => '{'];
$i = 0;
while (!empty($s[$i])) {
if (in_array($s[$i], $map)) {
array_push($stack, $s[$i]);
} else if (array_pop($stack) != $map[$s[$i]]) {
return false;
}
$i++;
}
return empty($stack);
}
}
