使用两个栈实现一个队列
创新互联建站是一家以网络技术公司，为中小企业提供网站维护、网站建设、成都网站设计、网站备案、服务器租用、域名注册、软件开发、重庆小程序开发等企业互联网相关业务，是一家有着丰富的互联网运营推广经验的科技公司，有着多年的网站建站经验，致力于帮助中小企业在互联网让打出自已的品牌和口碑，让企业在互联网上打开一个面向全国乃至全球的业务窗口：建站咨询电话：028-86922220
思路一：
我们设定s1是入栈的，s2是出栈的。
入队列，直接压到s1即可
出队列，先把s1中的元素倒入到s2中，弹出s2中的栈顶元素；再把s2的剩余元素全部倒回s1中。
缺点：
每次只要出栈一个元素就要将元素倒来倒去，麻烦！！！
思路2：
入队列时：
如果s1为空，把s2中所有的元素倒出压到s1中。否则直接压入s1
出队列时：
如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素
思路1无条件地每次都要将元素倒来倒去，思路2出队时较思路1简单
思路3：
我们设定s1是入栈的，s2是出栈的
入队列：直接压入元素至s1即可
出队列：如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素
相比于方法2，入队直接压入即可~
那么，我们可以看出，思路三最简单，我们下面看下代码。
代码实现：
1）我们直接调用库里的stack来实现。（一般调用库里的就行了）
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
//两个栈实现一个队列
#include
template
class Queue
{
public:
void appendTail(const T& x)
{
s1.push(x);
}
void deleteHead()
{
if (s2.empty())
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
cout << s2.top() << " ";
s2.pop();
}
else
{
cout << s2.top() << " ";
s2.pop();
}
}
private:
stack s1;
stack s2;
};
void Test()
{
Queue q;
q.appendTail(1);
q.appendTail(2);
q.appendTail(3);
q.appendTail(4);
q.deleteHead();
q.deleteHead();
q.deleteHead();
q.deleteHead();
}
int main()
{
Test();
system("pause");
return 0;
}
2）自己实现栈实现。
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
#include
//直接实现Stack，也可以用适配器实现栈，或者用库。
//将Stack基本功能实现如下：
template
class Stack
{
public:
Stack()
:_array(NULL)
, _size(0)
, _capacity(0)
{}
Stack(const Stack& s)
: _array(new T[s._capacity])
{
swap(_array, s._array);
swap(_size, s._size);
swap(_capacity, s._capacity);
}
Stack& operator=(const Stack& s)
{
if (&s != this)
{
swap(_array, s._array);
swap(_size, s._size);
swap(_capacity, s._capacity);
}
return *this;
}
~Stack()
{
if (_array)
{
delete[] _array;
_array = NULL;
}
}
void _CheckCapacity()
{
if (_size == 0)
{
_capacity = 3;
_array = new T[_capacity];
}
if (_size >= _capacity)
{
_capacity *= 2;
T* tmp = new T[_capacity];
for (int index = 0; index < _size; index++)
{
tmp[index] = _array[index];
}
delete[] _array;
_array = tmp;
}
}
void Push(const T& x)
{
_CheckCapacity();
_array[_size++] = x;
}
void Pop()
{
if (_size == 0)
{
return;
}
--_size;
}
size_t Size()
{
return _size;
}
bool Empty()
{
return Size() == 0;
}
T& Top()
{
assert(_size > 0);
return _array[_size - 1];
}
private:
T* _array;
size_t _size;
size_t _capacity;
};
template
class Queue
{
public:
void InQueue(const T& x)
{
s1.Push(x);
}
void OutQueue()
{
//栈s2为空，则将栈s1的元素全部倒入s2中，再弹出最上面的那个元素
if (s2.Empty())
{
while (!s1.Empty())
{
s2.Push(s1.Top());
s1.Pop();
}
s2.Pop();
}
//栈s2不为空，直接弹出元素
else
{
s2.Pop();
}
}
void Print() //打印队列元素，分四种情况。
{
if (s1.Empty() && s2.Empty())
{
cout << "The Queue is Empty!";
}
else if (!s1.Empty() && s2.Empty())
{
while (!s1.Empty())
{
s2.Push(s1.Top());
s1.Pop();
}
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
}
else if (s1.Empty() && !s2.Empty())
{
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
}
else
{
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
while (!s1.Empty())
{
s2.Push(s1.Top());
s1.Pop();
}
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
}
cout << endl;
}
private:
Stack s1; //入队
Stack s2; //出队
};
//测试两个栈实现一个队列
void Test1()
{
Queue q1;
q1.InQueue(1);
q1.InQueue(2);
q1.InQueue(3);
q1.InQueue(4);
/*q1.Print();*/
q1.OutQueue();
/*q1.Print();*/
q1.InQueue(5);
q1.InQueue(6);
q1.InQueue(7);
q1.Print();
}
int main()
{
Test1();
system("pause");
return 0;
}
(1个细节)：
注意再将元素倒入另一个栈时，代码并不是先pop,再push。因为这样push后元素就找不到了。因此要先访问到栈顶元素top,再push,而后pop。
标题名称：【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)
文章源于：
http://njwzjz.com/article/isjijg.html
