用两个栈实现一个队列的功能
数据结构的说明:
栈 :先入后出 FILO
队列:先入先出 FIFO
实现方式一,具体:
队列入列:栈A入栈;
举例:将A.B.C.D入列,从栈顶到栈底依次为:D C B A;
队列出列:判断栈元素个数是否为1,如为真,弹出;
如为假,栈A所有元素出栈POP,压入栈B;栈B栈顶元素POP;栈B所有元素压入栈A。
举例:栈A弹栈,栈B压栈,栈B从栈顶到栈底依次为: A B C D; 将栈顶元素A弹栈,将剩余元素压回栈A;栈A从栈顶到栈底依次为: B C D;
实现方式二,具体:
队列入列:判断栈元素个数是否为1,如为真,弹出;
如为假,栈A所有元素出栈POP,压入栈B;压入新元素到栈A;栈B所有元素压栈入栈A。
队列出列:栈A出栈;;
结束,总结:实现了队列的入队和出对操作。
用两个队列实现一个栈的功能
实现方式一,具体:
入栈:所有元素依次入队列A;
举例:将A.B.C.D入栈,从队列尾部到队列首部依次为:D C B A;
出栈:判断栈元素个数是否为1,如为真,队列A出列;
如为假,队列A所有元素出队列,入队列B,最后一个元素不入队列B,输出该元素;队列B所有元素入队列A;
举例:将D C B A出列,D输出来,C B A入队列B,最后返回到队列A。实现了后进先出。
实现方式二,具体:
入栈:和方式一出栈类似
出栈:和方式一入栈类似
结束,总结:实现了栈的入栈和出栈操作。
代码实例
//用两个栈实现队列的功能
template<class T>
class deque_from_stack
{
public:
deque_from_stack(){size = 0;}
void push(T& element)
{
stack_one.push(element);
size = stack_one.size();
}
T pop()
{
assert(this->size > 0);
T result = 0 ;
if(1 == this->size)
{
result = stack_one.top();
stack_one.pop();
this->size = 0;
return result;
}
if(this->size > 1)
{
while(stack_one.size())
{
stack_two.push(stack_one.top());
stack_one.pop();
}
result = stack_two.top();
stack_two.pop();
while(stack_two.size())
{
stack_one.push(stack_two.top());
stack_two.pop();
}
this->size--;
return result;
}
}
public:
stack<T> stack_one;//栈1
stack<T> stack_two;//栈2
size_t size;//元素的个数计数器
};
int main(int argc, char* argv[])
{
int i = 0;
//测试一
cout << "deque_from_stack :" <<endl;
deque_from_stack<int>d_s_s;
for (i = 1; i < 5; i++)
{
cout << i << " come in " << endl;
d_s_s.push(i);
}
for (i = 1; i < 5; i++)
{
cout << d_s_s.pop() << " go out " << endl;
}
cout << endl;
}
分享到:
相关推荐
主要介绍了C++语言数据结构用两个栈实现一个队列的实例的相关资料,需要的朋友可以参考下
本文实例讲述了JS实现利用两个队列表示一个栈的方法。分享给大家供大家参考,具体如下: 先看原理图: 理清楚思路,再动笔写: <!DOCTYPE html> <html> <head> <title>2 Queue</title>...
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解决思路 两个栈。出栈的时候,如果栈2不为空,就出栈2。如果栈2为空,就把栈1的出栈再入栈2。 实现代码 <?php $arr1 = array(); $...
有一个魔王总是使用自己的一种非常精练面抽象的语言讲话,没有人能听得慌,... 设计一个魔王语言转换系统,利用栈、队列实现相应的语言转换功能,程序可实现相应效果,同时可以进一步学习数据结构中的栈和队列操作过程。
1、实现一个栈数据结构。 2、利用栈实现中缀表达式与前缀表达式的转换。 三、相关内容介绍 标准的表达式如"A+B",在数学上学名叫中缀表达式(Infix Notation),原因是运算符号在两个运算对象的中间。相对应的还有...
适合新手做MQ的入实验,有助于对MQ的理解!
主要介绍了C#队列Queue多线程用法,实例分析了队列的相关使用技巧,需要的朋友可以参考下
数据结构 栈和队列 包括中缀转后缀表达式 运动会赛程安排两个实例
在实际使用中,还可以有输出受限的双向队列(即一个端点允许插入和删除,另一个端点只允许插入的双向队列)和输入受限的双向队列(即一个端点允许插入和删除,另一个端点只允许删除的双向队列)。而如果限定双向队列...
银行有两个服务窗口,相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时,如果居于第一种,且申请额超出银行现存资金总额顺得不到满足,则立刻排入第二个队等候,直至满足时才离开银行;否则业务...
Tcp服务端与客户端的JAVA实例源代码,一个简单的Java TCP服务器端程序,别外还有一个客户端的程序,两者互相配合可以开发出超多的网络程序,这是最基础的部分。 递归遍历矩阵 1个目标文件,简单! 多人聊天室 3...
本文实例讲述了Python实现栈和队列的简单操作方法。分享给大家供大家参考,具体如下: 先简单的了解一下数据结构里面的栈和堆: 栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于: stack:后进先出 ...
linux 下的消息队列详解,实例为聊天实现
实例077 使用正则表达式验证一个月的31天 93 实例078 使用正则表达式验证数字输入 94 实例079 使用正则表达式验证密码长度 95 实例080 使用正则表达式验证非零的正整数 96 实例081 使用正则表达式验证非零的负整数 ...
本文实例讲述了PHP基于数组实现的堆栈和队列功能。分享给大家供大家参考,具体如下: 堆栈和队列是数据结构的两种实现形式,是使用非常广泛的存储数据的容器。下面呢,就分别讲下这两种容器在PHP中的应用: 一、使用...
本文实例讲述了python双端队列原理、实现与使用方法。分享给大家供大家参考,具体如下: 双端队列 双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹...