【C/C++练习题】用两个栈实现队列
【摘要】
《剑指Offer》面试题9
1 问题
题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。
template <typename T> class CQueue{public: CQueue...
《剑指Offer》面试题9
1 问题
题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。
template <typename T>
class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
2 分析
1.栈和队列都是线性表,但是栈只能从一端进行操作,队列从首尾两端进行操作。一个栈stack1作为队列尾部,另一个栈stack2作为队列头。
2.栈对数据的逻辑操作满足"先入后出",和队列相反。当经过stack1->stack2,原本栈底数据变成栈顶数据(两次反操作,等于一次正操作)
3.stack1 数据入队(队列尾部)、stack2 数据出队(队列头部)
3 代码
#include "iostream"
#include "stack"
#include <exception>
using namespace std;
template <typename T>
class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template <typename T>
CQueue<T> :: CQueue(void){
}
template <typename T>
CQueue<T> :: ~CQueue(void){
}
template <typename T>
void CQueue<T> :: appendTail(const T& node)
{// 在队列末尾添加一个结点
this->stack1.push(node); //数据压栈
}
template <typename T>
T CQueue<T> :: deleteHead()
{// 队列的头结点出队
if(stack2.size()<= 0)
{//1.stack2从stack1取数据
while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
//队列空了
if(stack2.size() == 0)
{
cout << "queue is empty" << endl;
exit(-1);
}
//数据出队
T head = stack2.top(); //栈顶元素弹出
stack2.pop(); //移除栈顶元素
return head;
}
void Test(char actual, char expected)
{
if(actual == expected)
printf("Test passed.\n");
else
printf("Test failed.\n");
}
int main(int argc, char* argv[])
{
CQueue<char> queue;
queue.appendTail('a');
queue.appendTail('b');
queue.appendTail('c'); //cba
char head = queue.deleteHead(); //a出队, cb
Test(head, 'a');
head = queue.deleteHead(); //b出队,c
Test(head, 'b');
queue.appendTail('d'); //d入队,dc
head = queue.deleteHead(); //c出队,d
Test(head, 'c');
queue.appendTail('e'); //e入队,ed
head = queue.deleteHead(); //d出队,e
Test(head, 'd');
head = queue.deleteHead(); //e出队,队空
Test(head, 'e');
return 0;
}
4 运行结果
文章来源: blog.csdn.net,作者:hinzer,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/feit2417/article/details/96834586
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)