代码随想录算法训练营第八天 | leetcode：用栈实现队列,用队列实现栈
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 232. 用栈实现队列
#需要注意的地方
出栈时，需要把入栈的数据全部装进出栈，否则会导致数据错误。
解题方法
使用两个栈，一个入栈对应队列进数据，一个出栈对应队列出数据。
复杂度
时间复杂度:
push和empty为O(1), pop和peek为O(n)
空间复杂度:
O(n)
code
class MyQueue {
/**
*/
private $stackIn;
private $stackOut;
function __construct() {
$this->stackIn = new SplStack();
$this->stackOut = new SplStack();
}
/**
* @param Integer $x
* @return NULL
*/
function push($x) {
$this->stackIn->push($x);
}
/**
* @return Integer
*/
function pop() {
$res = [];
//判断出栈是否为空，为空查询入栈是否有数据，有数据则全部转入到出栈。
//这里处理的是栈的top与pop不是队列的。
if($this->stackOut->isEmpty()){
while(!$this->stackIn->isEmpty()){
// $this->stackOut->push($this->stackIn->top());
// $this->stackIn->pop();
$this->stackOut->push($this->stackIn->pop());
}
}
$res = $this->stackOut->pop();
// $this->stackOut->pop();
return $res;
}
/**
* @return Integer
*/
function peek() {
$res = $this->pop();
$this->stackOut->push($res);
return $res;
}
/**
* @return Boolean
*/
function empty() {
//判断队列是否为空需要把入栈和出栈一起判断
return $this->stackIn->isEmpty() && $this->stackOut->isEmpty();
}
}Problem: 225. 用队列实现栈
需要注意的地方
SplQueue继承自SplDoublyLinkedList。因此，SplQueue的对象支持方法push（）和pop（）。但请注意，如果您在SplQueue对象上使用push（）和pop（）方法，它的行为就像堆栈而不是队列。因此，请确保在SplQueue对象上只使用入队列enqueue()和出队列dequeue()方法，而不是push（）和pop（）方法
另外出队列方向是头部，栈顶是栈的头部，所以当入队列后，队列的尾部对应栈顶，但这里因为SplQueue继承自SplDoublyLinkedList。它的行为就像堆栈而不是队列。top()与bottom()指向也符合堆栈而不是队列。因此当需要指向栈头部时，直接使用top()即可。
解题方法
关键点：把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈顶所需要弹出的数据。如此循环，即弹出顺序与栈相同。
复杂度
时间复杂度:
pop为O(n)，其他为O(1)
空间复杂度:
O(n)
code
class MyStack {
private $queue;
/**
* SplQueue继承自SplDoublyLinkedList。因此，SplQueue的对象支持方法push（）和pop（）。
* 但请注意，如果您在SplQueue对象上使用push（）和pop（）方法，它的行为就像堆栈而不是队列。
* top()与bottom()指向也符合堆栈而不是队列
* 因此，请确保在SplQueue对象上只使用入队列enqueue()和出队列dequeue()方法，而不是push（）和pop（）方法。
*/
function __construct() {
$this->queue = new SplQueue();
}
/**
* @param Integer $x
* @return NULL
*/
function push($x) {
$this->queue->enqueue($x);
}
/**
* @return Integer
*/
function pop() {
$result = [];
$size = $this->queue->count();
//需要保留末尾元素 先减减
$size--;
//把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈所需要弹出的数据
while($size--){
$this->queue->enqueue($this->queue->dequeue());
}
$result = $this->queue->dequeue();
return $result;
}
/**
* @return Integer
*/
function top() {
return $this->queue->top();
}
/**
* @return Boolean
*/
function empty() {
return $this->queue->isEmpty();
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号