《剑指offer》面试题7—用两个栈实现队列
2024-09-04 23:16:02
题目：给出队列声明，要求实现AppendTail和DeleteHead函数。
template <typename T>
class CQueue
{
public:
void AppendTail(const T& element);
T DeleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
思路：要用两个先进后出的栈实现先进先出的队列。压栈总是压入stack1，要获得队列头时：如果stack2为空，则把stack1依次弹出栈并压入stack2，取stack2栈顶元素；如果stack2不为空，则直接取stack2栈顶元素。
#include <iostream>
#include <stack>
using namespace std; template <typename T>
class CQueue
{
public:
void AppendTail(const T& element);
T DeleteHead();
private:
stack<T> stack1;
stack<T> stack2;
}; template<typename T> void CQueue<T>::AppendTail(const T& element)
{
stack1.push(element);
} template<typename T> T CQueue<T>::DeleteHead()
{
T temp;
if(!stack2.empty())
{
temp = stack2.top();
stack2.pop();
}
else
{
if(stack1.empty())
{
cout<<"No element left!"<<endl;
//return;
}
else
{
while(!stack1.empty())
{
temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
temp = stack2.top();
stack2.pop();
}
}
return temp;
} int main()
{
CQueue<int> my_queue;
int n,val;
cout<<"1 for Append"<<endl<<"2 for DeleteHead"<<endl;
while(scanf("%d",&n)!=)
{
if(n == )
{
scanf("%d",&val);
my_queue.AppendTail(val);
}
else if(n == )
{
val = my_queue.DeleteHead();
cout<<"The head of Queue:"<<val<<endl;
}
else
cout<<"Illegal n!"<<endl;
}
return ;
}
最新文章
- OneThink-nav标签
- escape(), encodeURI()和encodeURIComponent()(转)
- HTML页面优化
- word 多级列表设置
- MySQL更新优化
- 【转】Java魔法堂：String.format详解
- Oracle Exadata体系笔记
- 用PYTHON硬写SOCKET
- Android的Manifest配置文件介绍
- 【动态规划】XMU 1029 矩阵链乘法
- 内核对象kobject和sysfs（4）——kset分析
- ASP.NET Core开发期间部署到IIS自定义主机域名并附加进程调试
- sizeof(extern类型数组)
- Python 函数参数传递机制.
- about-php
- 刪除nodejs
- ReactNative系列组件用法(一)
- HDU 1403 Longest Common Substring（最长公共子串）
- 洛谷P3389 高斯消元 / 高斯消元+线性基学习笔记
- VS2015编译CURL7.54.0源码