面试题:用两个栈(Stack)实现一个队列(Queue)
思路:
1、入队时,将元素压入s1。
2、出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。
具体实现如下:
#include<iostream>
using namespace std;
#include<stack>
#include<string>
#include<assert.h>//assert必须为.h库文件
template<class T>
class Queue
{
public:
void Push(const T& x);
void Pop();
void PrintQueue();
bool Empty();
size_t Size();
T& Front();
T& Back();
public:
stack<T> s1;//栈s1进行入队
stack<T> s2;//栈s2进行出队
};
template<class T>
void Queue<T>::Push(const T& x)
{
s1.push(x);//s1栈入队
}
template<class T>
void Queue<T>::Pop()
{
if (s1.empty() && s2.empty())//两个队列为空
{
return;
}
if (!s2.empty())//s2栈非空元素出栈
{
s2.pop();
}
else
{
while (!s1.empty()) //s2栈为空,s1中所有元素导入s2中进行s2的出栈,s1进行pop()
{
s2.push(s1.top());
s1.pop();
}
s2.pop();//pop掉s2的栈顶元素
}
}
template<class T>
void Queue<T>::PrintQueue()
{
stack<T> sk1 = s1;
stack<T> sk2 = s2;
if (s1.empty() && s2.empty())
{
cout << "queue is empty!" << endl;
return;
}
while (!sk2.empty())//先输出sk2中的元素,进行sk2的出栈
{
cout << sk2.top() << " ";
sk2.pop();
}
while (!sk1.empty())//再进行sk1中元素导入到sk2中,进行sk1的出栈
{
sk2.push(sk1.top());
sk1.pop();
}
while (!sk2.empty())//最后在sk2中输出sk1中元素,达到队列出队的效果
{
cout << sk2.top() << " ";
sk2.pop();
}
cout << endl;
}
template<class T>
bool Queue<T>::Empty()//判空
{
return s1.size() == 0 && s2.size() == 0;
}
template<class T>
size_t Queue<T>::Size()//队列元素个数
{
return s1.size() + s2.size();
}
template<class T>
T& Queue<T>::Front()//队头
{
assert(s1.empty() && s2.empty());//断言队列是否为空
if (!s2.empty())//s2不为空,则s2栈顶为队头
{
return s2.top();
}
else//s2为空,则将s1中所有元素导入s2中,新s2栈顶为队头
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
}
template<class T>
T& Queue<T>::Back()//队尾
{
assert(!s1.empty() || !s2.empty());//s1和s2中至少有一个不为空
if (!s1.empty())//s1不为空,则s1栈顶为队尾
{
return s1.top();
}
else//s1为空,则将s2中所有元素导入s1中,新s1栈顶为队尾
{
while (!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
return s1.top();
}
}
测试用例如下:
void Test2()
{
//Queue<int> q1;
//q1.s1.push(3);
//q1.s2.push(4);
//q1.s2.push(5);
//q1.Push(2);
//q1.Push(1);
//q1.PrintQueue();
////q1.Pop();
////q1.Pop();
////q1.Pop();
////q1.Pop();
////q1.Pop();
////q1.Pop();
////q1.PrintQueue();
Queue<string> q1;
q1.s1.push("lllll");
q1.s2.push("yyyyy");
q1.s2.push("fffff");
q1.Push("xxxxx");
q1.Push("yyyyy");
q1.PrintQueue();
cout << "empty: " << q1.Empty() << endl;
cout << "size: " << q1.Size() << endl;
cout << "front: " << q1.Front() << endl;
cout << "back: " << q1.Back() << endl;
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。