C++基础学习之利用两个栈实现一个队列

1 .给出类类型如下:有两个成员变量,分别是两个stack容器,存放的元素类型是 int;stack的特点是:先进后出;而队列queue的特点是先进先出;现在用两个 stack容器来实现队列:

实现代码:

-------------------------------------
------------- queue.h ---------------
#pragma once
#include <iostream>
#include <stdlib.h>
#include <stack>
using namespace std;

class Queue
{
private:
 stack<int> s1;
 stack<int> s2;
public:
 //入队
 void Push(const int& val);
 //出队
 void Pop();
 //返回队首元素
 int& Front();
 //返回队尾元素
 int& Back();
 //判断队列是否为空
 bool Empty();
 //返回队列大小
 int Size();
};

----------------------------------------
------------- queue.cpp ----------------

#include "queue.h"

//入队
void Queue::Push(const int& val)
{
 //栈s1作队列的队尾,s2作为队列的队头
 s1.push(val);
 cout<<val<<" ";
}

//出队
void Queue::Pop()
{
 while (!s1.empty())
 {
 int val = s1.top();
 s2.push(val);
 s1.pop();
 }
 s2.pop();
}

//返回队首元素
int& Queue::Front()
{
 while (!s1.empty())
 {
 s2.push(s1.top());
 s1.pop();
 }

 int temp = s2.top();
 while (!s2.empty())
 {
 int var = s2.top();
 s1.push(var);
 s2.pop();
 }
 return temp;
}

//返回队尾元素
int& Queue::Back()
{
 return s1.top();
}

//判断队列是否为空
bool Queue::Empty()
{
 if (s1.empty()&&s2.empty())
 {
 return true;
 }
 else
 return false;
}

//返回队列大小
int Queue::Size()
{
 return s1.size()+s2.size();
}

--------------------------------------
--------------- test.cpp -------------
#include "queue.h"
void test()
{
 Queue q1;
 cout<<"入队列操作:"<<endl;
 cout<<"插入的队列元素分别是:"<<endl;
 q1.Push(1);
 q1.Push(2);
 q1.Push(3);
 q1.Push(4);
 q1.Push(5);
 q1.Push(6);
 cout<<"判断队列是否为空!"<<endl;
 if (q1.Empty())
 {
 cout<<"empty."<<endl;
 }
 else
 {
 cout<<"not empty."<<endl;
 }
 cout<<"获取队头元素:"<<endl;
 cout<<q1.Front()<<endl;
 cout<<"获取队尾元素:"<<endl;
 cout<<q1.Back()<<endl;
 cout<<"获取队列的大小操作:"<<endl;
 cout<<q1.Size()<<endl;
 printf("出队列操作:\n");
 q1.Pop();
}
int main()
{
 test();
 system("pause");
 return 0;
}

分析过程:

让s1作为存储空间,而s2作为临时缓冲区。

进行入队操作时,将元素压入s1。

进行出队操作时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

(0)

相关推荐

  • C++用两个栈实现一个队列(面试官的小结)

    前言 两年前从网上看到一道面试题:用两个栈(Stack)实现一个队列(Queue).觉得不错,就经常拿来面试,几年下来,做此题的应该有几十人了.通过对面试者的表现和反应,有一些统计和感受,在此做个小结. 用C++描述,题目大致是这样的: 已知下面Stack类及其3个方法Push.Pop和 Count,请用2个Stack实现Queue类的入队(Enqueue)出队(Dequeue)方法. class Stack { - public: void Push(int x); // Push an el

  • C++中实现队列类链式存储与栈类链式存储的代码示例

    队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

  • C++利用两个栈实现队列的方法

    1. 基础 队列:先进先出,即插入数据在队尾进行,删除数据在队头进行: 栈:后进先出,即插入与删除数据均在栈顶进行. 2. 思路 两个栈实现一个队列的思想:用pushStack栈作为push数据的栈,用popStack栈作为pop数据的栈. 只要是对队列进行push操作,就将数据push入pushStack栈中. 要实现队列的pop操作,有二点原则,如果popStack为空的话那么我们就将pushStack所有的元素放到popStack中,然后取popStack栈顶元素就是队列的队头:如果pop

  • C++ 数据结构实现两个栈实现一个队列

    C++ 数据结构实现两个栈实现一个队列 栈为后进先出,队列为先进先出 用两个栈实现一个队列.是一个比较经典的问题. 看到这个问题,我的第一个解题思路为: 定义两个栈,s1,s2.s1作为入队列栈,s2作为出队列栈: 入队列:每次入队列的时候,将数值压入s1栈中: 出队列:出队列时,将s1中的所有数据,压进s2栈中,然后删除s2的栈顶数据,然后再将s2中的剩余数据压入s1中. 在这其中s1是一个存储空间,s2是一个辅助空间. 进一步想一下上述办法,在出队列时,每一次都要将s1倒进s2,然后删除s2

  • C++基础学习之利用两个栈实现一个队列

    1 .给出类类型如下:有两个成员变量,分别是两个stack容器,存放的元素类型是 int:stack的特点是:先进后出:而队列queue的特点是先进先出:现在用两个 stack容器来实现队列: 实现代码: ------------------------------------- ------------- queue.h --------------- #pragma once #include <iostream> #include <stdlib.h> #include &l

  • 数据结构用两个栈实现一个队列的实例

    数据结构用两个栈实现一个队列的实例 栈是先进后出,队列是先进先出 每次元素都push在st1中,pop的时候如果st2为空,将st1的栈顶元素放在st2的栈底,这样st1的所有元素都放在st2中,st1的栈底就是st2的栈顶,pop st2的栈顶,这样就满足了队列的先进先出. #include <iostream> using namespace std; #include <stack> #include <stdlib.h> template <class T

  • 探讨:用两个栈实现一个队列(我作为面试官的小结)

    两年前从网上看到一道面试题:用两个栈(Stack)实现一个队列(Queue).觉得不错,就经常拿来面试,几年下来,做此题的应该有几十人了.通过对面试者的表现和反应,有一些统计和感受,在此做个小结. 用C++描述,题目大致是这样的: 已知下面Stack类及其3个方法Push.Pop和 Count,请用2个Stack实现Queue类的入队(Enqueue)出队(Dequeue)方法. 复制代码 代码如下: class Stack{-public:         void Push(int x);

  • 解析如何用两个栈来实现队列的方法

    题目:如何用两个栈来实现队列,即实现队列的两个方法--appendTail(插入)和deleteHead(删除).分析:核心思想是一个栈正向存储,另外一个栈逆向存储.正向存储的栈用来插入,逆向存储的栈用来删除.实现的Java代码如下: 复制代码 代码如下: import java.util.Stack;public class QueneWithTwoStacks<E> { private Stack<E> stack1; private Stack<E> stack2

  • Linux基础学习之利用tcpdump抓包实例代码

    简介 很多时候我们的系统部署在Linux系统上面,在一些情况下定位问题就需要查看各个系统之间发送数据报文是否正常,下面我就简单讲解一下如何使用tcpdump抓包 网络数据包截获分析工具.支持针对网络层.协议.主机.网络或端口的过滤.并提供and.or.not等逻辑语句帮助去除无用的信息. tcpdump - dump traffic on a network tcpdump的命令格式 tcpdump的参数众多,通过man tcpdump可以查看tcpdump的详细说明,这边只列一些自己常用的参数

  • C++利用链表模板类实现简易队列

    本文实例为大家分享了C++利用链表模板类实现一个队列的具体代码,供大家参考,具体内容如下 设计思想:MyQueue.h中对模板类进行声明和实现.首先定义结点的结构体,包含数据和指针域两部分.队列类定义中声明和实现了元素入队,出队,打印队首元素和队列等方法. 注意: 1)模板类的声明和定义不能分开(即不能分别放在.h和.cpp文件里). 2)声明新节点时,如果声明的节点是辅助操作的,可以不用new关键字,例如在析构函数中,直接用:Node<T>* temp:定义即可.如果声明一个新节点加入队列,

  • C语言用栈模拟实现队列问题详解

    目录 题目描述 题目链接 思路分析 代码实现 题目描述 请你仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作(push.pop.peek.empty). 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的. 题目链接 用栈实现队列 思路分析 题目的意思是要用两个栈来模拟实现一个队列.仅可以用栈的基本功能实现队列的基本功能.所以需要创建两个栈.所以这两个栈st1,st2可用一个结构

随机推荐