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

1. 基础

队列:先进先出,即插入数据在队尾进行,删除数据在队头进行;

栈:后进先出,即插入与删除数据均在栈顶进行。

2. 思路

两个栈实现一个队列的思想:用pushStack栈作为push数据的栈,用popStack栈作为pop数据的栈。

  1. 只要是对队列进行push操作,就将数据push入pushStack栈中。
  2. 要实现队列的pop操作,有二点原则,如果popStack为空的话那么我们就将pushStack所有的元素放到popStack中,然后取popStack栈顶元素就是队列的队头;如果popStack不为空的话,我们就直接获取popStack的栈顶元素。
  3. 对于top操作来说和pop操作类似,只是最后一步不用pop了。

3. 代码

#include <iostream>
#include <stack>
#include <exception>

template<class T> class MyQueue {
 public:
 void push(const T& num); // 入队列
 T pop(); // 出队列
 T top();
 private:
 std::stack<T> pushStack;
 std::stack<T> popStack;
};
template<typename T>
void MyQueue<T>::push(const T& num) {
 pushStack.push(num);
}
template<typename T>
T MyQueue<T>::pop() {
 if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 获取pushStack栈顶元素
 pushStack.pop(); // 出栈
 popStack.push(data);
 }
 }
 T data = popStack.top();
 popStack.pop();
 return data;
}
template<typename T>
T MyQueue<T>::top() {
 if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 获取pushStack栈顶元素
 pushStack.pop(); // 出栈
 popStack.push(data);
 }
 } else { // 如果popStack不为空的话直接返回popStack栈顶
 T data = popStack.top();
 return data;
 }
}
int main() {
 MyQueue<int> myQueue1;
 myQueue1.push(1);
 myQueue1.push(2);
 myQueue1.push(3);
 myQueue1.push(4);
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;

 return 0;
}

4. 参考文献

  • 用两个栈实现一个队列——我作为面试官的小结
  • C++之用两个栈实现一个队列

总结

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

(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++ 数据结构实现两个栈实现一个队列

    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

  • 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

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • PHP使用两个栈实现队列功能的方法

    本文实例讲述了PHP使用两个栈实现队列功能的方法.分享给大家供大家参考,具体如下: 问题 用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 解决思路 两个栈.出栈的时候,如果栈2不为空,就出栈2.如果栈2为空,就把栈1的出栈再入栈2. 实现代码 <?php $arr1 = array(); $arr2 = array(); function mypush($node) { array_push($arr1,$node); } function mypop()

  • 如何使用两个栈实现队列Java

    这篇文章主要介绍了如何使用两个栈实现队列Java,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目 用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 题解 描述 栈的特性是先进后出,队列的特点是先进先出,当数字依次入栈1后,依次出栈1并且压入栈2后,然后再出栈的顺序与进入栈1的顺序是一致的. 因此,进入队列通过压入栈1实现,弹出队列通过弹出栈2的栈顶元素实现,在弹出元素时需要保证当前栈弹出元素的顺序和队列弹

  • Python利用heapq实现一个优先级队列的方法

    实现一个优先级队列,每次pop的元素要是优先级高的元素,由于heapq.heapify(list)默认构建一个小顶堆,因此要将priority变为相反数再push,代码如下: import heapq class PriorityQueue(object): """实现一个优先级队列,每次pop优先级最高的元素""" def __init__(self): self._queue = [] self._index = 0 def push(sel

  • C语言栈与队列相互实现详解

    目录 一.本章重点 二.队列实现栈 三.栈实现队列 四.解题思路总结 一.本章重点 用两个队列实现栈 用两个栈实现队列 解题思路总结 二.队列实现栈 我们有两个队列: 入栈数据1. 2. 3 可以将数据入队列至队列一或者队列二. 如何出栈? 但出栈要先出1,怎么办? 第一步: 将队列一出队n-1个至队列二. 第二步: pop队列一的最后一个元素. 接下来怎么入栈呢? 将元素入队至不为空的队列. 怎么判断栈空? 队列一和队列二都为空的情况下,栈就是空的. 如何取栈顶元素? 取不为空的队列尾部元素.

  • JS实现利用两个队列表示一个栈的方法

    本文实例讲述了JS实现利用两个队列表示一个栈的方法.分享给大家供大家参考,具体如下: 先看原理图: 理清楚思路,再动笔写: <!DOCTYPE html> <html> <head> <title>2 Queue</title> <meta charset="utf-8"/> <script type="text/javascript"> var arr1 = []; var arr

  • python 利用栈和队列模拟递归的过程

    一.递归 递归调用:一个函数,调用的自身,称为递归调用 递归函数:一个可以调用自身的函数称为递归函数 凡是循环能干的事,递归都能干 方法: 1.写出临界条件 2.找这一次和上一次的关系 3.假设当前函数已经能用,调用自身计算上一次的结果再求出本次的结果 下面我们通过两段代码简单看一下递归和非递归的区别: 输入一个大于等于1的数,求1到n的和! # 普通函数方法 def hanshu(n): sum = 0 # 循环遍历每一个数字,将他们加到一个事先定义好的变量上,直到加完 for x in ra

  • C/C++利用栈和队列实现停车场管理系统

    目录 纯c语言版 包含的功能 运行效果 源码 c++版 包含的功能 运行效果 源码 纯c语言版 包含的功能 1.停车功能 如果停车场满,能够暂时存放到便道内 2.开走车功能 将指定车开走后打印收据,便道内的车自动停到停车场 3.退出程序功能 运行效果 停车功能测试: 离开停车场并打印收据测试: 源码 #define _CRT_SECURE_NO_WARNINGS//visual stduio添加对scanf的信任 #include<stdio.h> #include <stdlib.h&

随机推荐