最容易想到的办法是申请一个额外的队列,先把栈中的元素依次出栈放到队列里,然后把队列里的元素按照出队列顺序入栈,这样就可以实现栈的翻转,这种方法的缺点是需要申请额外的空间存储队列,因此,空间复杂度较高。下面介绍一种空间复杂度较低的递归的方法。
递归程序有两个关键因素需要注意:递归定义和递归终止条件。经过分析后,很容易得到该问题的递归定义和递归终止条件。递归定义:将当前栈的最底元素移到栈顶,其他元素顺次下移一位,然后对不包含栈顶元素的子栈进行同样的操作。终止条件:递归下去,直到栈为空。递归的调用过程如下图所示。
在上图中,对于栈(1,2,3,4,5)进行翻转的操作:首先把栈底元素移动到栈顶得到栈(5,1,2,3,4),然后对不包含栈顶元素的子栈进行递归调用(对子栈元素进行翻转),子栈(1,2,3,4)翻转的结果为(4,3,2,1),因此,最终得到翻转后的栈为(5,4,3,2,1)。
此外,由于栈的后进先出的特点,使得只能取栈顶的元素,因此,要把栈底的元素移动到栈顶也需要递归调用才能完成,主要思路:把不包含该栈顶元素的子栈栈底的元素移动到子栈的栈顶,然后把栈顶的元素与子栈栈顶的元素(其实就是与栈顶相邻的元素)进行交换,如下图所示。
为了容易理解递归调用,可以认为在进行递归调用的时候,子栈已经实现了把栈底元素移动到了栈项,在上图中为了把栈(1,2,3,4,5)的栈底元素5移动到栈顶,首先对子栈(2,3,4,5)进行递归调用,调用的结果为(5,2,3,4),然后对子栈顶元素5,与栈顶元素1进行交换,得到栈(5,1,2,3,4),实现了把栈底元素移动到了栈顶。
示例代码如下:
<?php
header("content-type:text/html;charset=utf-8");
class LNode{
public $mElem;
public $mNext;
public function__construct(){
$this->mElem=NULL;
$this->mNext=NULL;
}
}
class StackLinked{
//头“指针”,指向栈顶元素
public $mNext;
public static $mLength;
/**
*初始化栈
*
*@return void
*/
public function__construct(){
$this->mNext=NULL;
self::$mLength=0;
}
/**
*判断栈是否空栈
*
*@return boolean如果为空栈返回true,否则返回false
*/
public function getIsEmpty(){
if($this->mNext==NULL){
return true;
}else{
return false;
}
}
/**
*将所有元素出栈
*
*@return array返回所有栈内元素
*/
public function getAllPopStack(){
$e=array();
if(!$this->getIsEmpty()){
while($this->mNext!=NULL){
$e[]=$this->mNext->mElem;
$this->mNext=$this->mNext->mNext;
}
}
self::$mLength=0;
return $e;
}
/**
*返回栈内元素个数
*
*@return int
*/
public static function getLength(){
return self::$mLength;
}
/**
*元素进栈
*
*@param mixed $e进栈元素值
*@return boolean进栈成功返回true
**/
public function push($e){
$newLn=new LNode();
$newLn->mElem=$e;
$newLn->mNext=$this->mNext;
$this->mNext=&$newLn;
self:;$mLength++;
return true;
}
/**
*元素出栈
*
*@return boolean出栈成功返回true,否则返回false
**/
public function pop(){
if($this->getIsEmpty()){
return false;
}
$p=$this->mNext;
$e=$p->mElem;
$this->mNext=$p->mNext;
self::$mLength--;
return true;
}
/**
*返回栈内所有元素
*
*@return array栈内所有元素组成的一个数组
*/
public function getAllElem(){
$sldata=array();
if(!$this->getIsEmpty()){
$p=$this->mNext;
while($p!=NULL){
$sldata[]=$p->mElem;
$p=$p->mNext;
}
return $sldata;
}
}
/*
*返回栈顶元素
*@return $element返回栈顶元素
*/
public function top()
{
if($this->getIsEmpty()){
return false;
}
$list=$this->getAllElem();
$element=$list[0];
return $element;
}
/*
**函数功能:把栈底元素移动到栈顶
*/
public function move_bottom_to_top()
{
if($this->getIsEmpty())
return;
$topl=$this->top();
$this->pop();//弹出栈顶元素
if(!$this->getIsEmpty()){
//递归处理不包含栈顶元素的子栈
$this->move_bottom_to_top();
$top2=$this->top();
$this->pop();
//交换栈顶元素与子栈栈顶元素
$this->push($top1);
$this->push($top2);
}else{
$this->push($top1);
}
}
public function reverse_stack()
{
if($this->getIsEmpty())
return;
//把栈底元素移动到栈顶
$this->move_bottom_to_top();
$top=$this->top();
$this->pop();
//递归处理子栈
$this->reverse_stack();
$this->push($top);
}
}
$stack=new StackLinked();
$stack->push('5');
$stack->push('4');
$stack->push('3');
$stack->push('2');
$stack->push('1');
$stack->reverse_stack();
echo"翻转后的出栈顺序为:";
while(!$stack->getIsEmpty())
{
echo $stack->top()." ";
$stack->pop();
}
?>
程序的运行结果为
翻转后的出栈顺序为:5 4 3 2 1
算法性能分析:把栈底元素移动到栈顶操作的时间复杂度为O(n),在翻转操作中对每个子栈都进行了把栈底元素移动到栈顶的操作,因此,翻转算法的时间复杂度为O(N^2)。