使用两个栈实现一个队列

时间：2020-12-16 17:39:51
1、题目要求 使用两个栈实现一个队列；
2、考查点定位
  • 栈的链式结构：
通常情况下，我们使用链表来实现栈结构，有利于插入删除操作的效率，而且不用关心栈的溢出情况。
  • 队列的链式结构：
通常情况下，我们使用链表来实现队列结构，有利于插入删除操作的效率，而且不用关心队列的溢出情况。
  • 栈的操作限定：
先进后出：由top指针单向遍历整个栈，所以链式栈形成的过程是单链表的“前插法”
  • 队列的操作限定：
先进先出：由front指针单向遍历整个队列，所以链式队列形成的过程是单链表的“后插法”
3、设计思想 在程序的实现过程中，我经常遵循的原则是“最原始的解决之道”，即 先不考虑“最优解”，最基本的方法实现后在考虑优化，那么下面我们就用这种方法用两个栈实现一个队列： 实现的原理：栈实现队列的要求其实就是使用两个栈实现“先进先出”的操作，当然我们不能用暴力的方法把栈的数据结构修改了（修改了那也就不是栈了，哈哈）已到达先进先出的效果，那么我们怎么使用两个先进后出的栈达到先进先出的效果呢？栈的操作只能在栈顶实现插入和弹出操作，要想把先插入的数据先取出来，得设法把先插入的数据放在栈顶就好了，即把栈里边的元素进行倒序，我们发现链式栈就是前插法建立的，每插一次就会翻转，那么我们可以利用第二个栈进行插入以达到翻转的效果，在第一个栈只进行插入操作，在第二栈只进行弹出操作，这样就实现了类似于队列的操作。 总结：进行两次插入栈（先进后出）的操作就可以达到队列（先进先出）的效果，插一次使原次序倒序，再插一次恢复原次序；过程如下图： 使用两个栈实现一个队列 那么我们要考虑的就是插入和弹出的时机，分下面几种方法： （1）基本方法：在S1中插，经过S2翻转，在S2中弹出，之后把S2倒回进行下一次插入，每次插入时要保证S2没有元素（考虑到把S2倒回S1时会打乱次序），每次弹出时后要把所有元素倒回以便下一次插入；这样就实现了最基本的队列功能。 （2）优化方法：我们发现S2中元素自顶向下就是正常的出队次序，且S2中只进行弹出操作，我们就不用把S2倒回S1，要插就在S1中插，要弹出就在S2中弹出（当S2中没有可弹出的元素时，再把S1中的元素倒过来），这样就减少了倒来倒去的操作；
4、代码实现这里使用第二种优化方法俩实现两个栈实现一个队列的操作，下面我将按照下面步奏实现上述操作；(1)利用前插法建立链式栈liststack：(2)建立likequeue类封装两个链式栈liststack，设置成员函数popqueue()pushqueue()来分别实现队列的压入操作和弹出操作,其中成员函数S1insertS2()是把插入栈S1中的元素倒入S2中的操作函数，代码如下：
#include<iostream>
#include <assert.h> 
using namespace std;

struct node
{
int data;
node* link;
node(const int &T, node* p = NULL){ data = T, link = p; };
};
//建立链式栈
class liststack
{
public:
liststack();
~liststack();
void push(int);
bool pop();
node* gettop();
bool isempty();
void MarkEmpty();
friend ostream& operator<<(ostream& os, liststack&TEST);
private:
node* top;
};

liststack::liststack()
{
//不需要附加头
top =NULL;
}

liststack::~liststack()
{
MarkEmpty();
}

void liststack::push(int temp)
{
if (!isempty())
{
node* newnode = new node(temp);
assert(newnode!=NULL);
newnode->link = top;
top = newnode;
} 
else
{
node* newnode = new node(temp);
assert(newnode != NULL);
newnode->link = NULL;
top = newnode;
}
}

bool liststack::pop()
{
if (isempty()) return false;

else
{
node* newnode = top;
top=top->link;
delete newnode;
return true;
}
}

void liststack::MarkEmpty()
{
   while (top!=NULL)
{
node* newnode = top;
top = top->link;
delete newnode;
}
}

bool liststack::isempty()
{
return top == NULL ? true: false;
}

node* liststack::gettop()
{
return top;
}

ostream& operator <<(ostream& os, liststack&TEST)
{
node *out = TEST.top;
while (out)
{
os << out->data << endl;
out = out->link;
}
return os;
};
//建立likequeue类封装两个链式栈liststack,实现队列的功能
class likequeue
{
public:
void pushqueue(int);
bool popqueue();
bool S1insertS2();
liststack S1, S2;

};

void likequeue::pushqueue(int test)
{
S1.push(test);
}

bool likequeue::popqueue()
{
if (S2.isempty())
{
S1insertS2();

}
S2.pop();
return true;
}

bool likequeue::S1insertS2()
{
if (S1.isempty()&&!S2.isempty()) return false;

node* S1top = S1.gettop();
while (S1top)
{
S2.push(S1top->data);
S1top = S1top->link;
S1.pop();
}
return true;
}


void main()
{
likequeue testqueue;
testqueue.pushqueue(1);//压入1
testqueue.pushqueue(2);//压入2
testqueue.popqueue();//弹出1
//第一次输出队列
liststack* test = &testqueue.S2;//-------------------------更改1处
operator<<(cout, *test);
system("pause");
}
标签：

相关文章