栈的特点:FILO(FirstInLastOut)
仅能从栈顶插入,删除元素。
最基本的接口包括push()——从栈顶压入元素,pop()——从栈顶弹出元素
队列的特点:FIFO(FirstInFirstOut)
仅能从队头删除元素,从队尾插入元素。
最基本的接口包括enque()——从队尾插入元素,deque()——从队头删除元素
1.用两个栈实现队列
思路:
新入队列的元素压入stack1中,当元素出队列时,若stack2为空,则将stack1的全部元素依次弹出,压入stack2中,这样stack2的栈顶元素即为队头元素。
template<typename T>
class MyQueue
{
public:
T front();
T back();
void enque(const T& ele);
void deque();
private:
void move(std::stack<T>& from, std::stack<T>& to);
private:
std::stack<T> stack1;
std::stack<T> stack2;
};
template<typename T>
void MyQueue<T>::move(std::stack<T>& from, std::stack<T>& to)
{
if (to.empty()) {
while (!from.empty()) {
to.push(from.top());
from.pop();
}
}
}
template<typename T>
T MyQueue<T>::front()
{
T ele;
move(stack1, stack2);
if (!stack2.empty()) {
ele = stack2.top();
}
return ele;
}
template<typename T>
T MyQueue<T>::back()
{
T ele;
move(stack2, stack1);
if (!stack1.empty()) {
ele = stack1.top();
}
return ele;
}
template<typename T>
void MyQueue<T>::enque(const T& ele)
{
stack1.push(ele);
}
template<typename T>
void MyQueue<T>::deque()
{
move(stack1, stack2);
if (!stack2.empty()) {
stack2.pop();
}
}
2.用两个队列实现栈
思路:
新元素入栈时,若两个队列都为空,向任意一个队列队尾插入元素,否则向其中一个非空队列插入元素。栈弹出元素时,将非空队列的元素依次删除,
插入另一个空队列,只留下队尾元素(此即栈顶元素),弹出栈顶即从队列中删除此元素。
template<typename T>
class MyStack
{
public:
T top();
void push(const T& ele);
void pop();
private:
std::queue<T> queue1;
std::queue<T> queue2;
};
template<typename T>
T MyStack<T>::top()
{
T ele;
if (queue1.empty() && !queue2.empty()) {
ele = queue2.back();
}
else if (!queue1.empty() && queue2.empty()) {
ele = queue1.back();
}
return ele;
}
template<typename T>
void MyStack<T>::push(const T& ele)
{
if (queue1.empty())
{
queue2.push(ele);
}
else if (queue2.empty())
{
queue1.push(ele);
}
}
template<typename T>
void MyStack<T>::pop()
{
if (queue1.empty())
{
while(queue2.size() > 1)
{
queue1.push(queue2.front());
queue2.pop();
}
if (!queue2.empty())
{
queue2.pop();
}
}
else if (queue2.empty())
{
while(queue1.size() > 1)
{
queue2.push(queue1.front());
queue1.pop();
}
if (!queue1.empty())
{
queue1.pop();
}
}
}
分享到:
相关推荐
Java-用数组实现栈-队列-线性列表(最详细) 有注释 适合java新生 进行数组的练习 3个数据结构的数组实现练习
java java_leetcode面试题解Stack之第232题用栈实现队列_题解
数据结构-栈和队列-PPT
《数据结构》习题汇编03-第三章-栈与队列-试题.pdf
编写程序,建立容量为n(建议n=8)的循环队列,完成以下程序功能。输入字符#,执行一次出队操作,...要求采用队头/队尾间隔至少一个空闲元素的方法来实现循环队列;空队执行出队操作及队满执行入队操作需显示提示信息。
3、栈与队列的应用举例 本章重点难点: 1、栈的存储结构、特点、基本操作算法实现、 以 及栈在递归算法实现中的应用。 2、队列存储结构、特点、基本操作、 算法实现、 循环队列及其应用。
栈实现 队列实现 双栈实现队列 双队列实现栈 栈实现O(n)求当前栈最大值 http://blog.csdn.net/ssuchange/article/details/17398007
C++实现用栈实现队列的功能
python用栈实现队列,简单明了易于进一步思考和总结发散思维。
数据结构课件、代码第3章栈和队列-81-3.ppt
题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104055970
数据结构实验(4)栈和队列(二)目录• 栈与队列• 栈与队列的扩展• 使用栈模拟队列• 深度优先搜索• 栈与队列的扩展• 栈与队列的扩展原始问题(N)子问题(N
数据结构-C语言版-第二版(严蔚敏)-第3章-栈和队列-答案.doc
数据结构实验(3)栈和队列目录• 栈与队列• 栈与队列的定义与实现• 栈与队列的应用• 函数栈与括号匹配问题• 队列与轮训调度• 深度优先与广度优先遍历算法•
数据结构与算法第四章线性表-栈和队列-习题答案 定义线性表节点的结构.doc
用C实现的栈与队列,可以加载使用。详见博文http://blog.csdn.net/pirateleo/article/details/7574598 共包含5个文件
1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容 题目:试写一个算法,判断依次读入的一个以@为结束符的字符序列,是否为回文。所谓“回文“是指正向读...
用栈实现队列逆序输出,C语言代码,VC++编译器!
用链表实现栈和队列的操作,使链表操作更加成熟,熟练栈和队列的机制
基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为0至9。 提高要求:实现+, -, *, /四个二元运算符以及(); 实现+, -两个一元运算符(即正、负号); 操作数可为任意整型值(程序假定整数及运算...