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

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

栈是先进后出，队列是先进先出

每次元素都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>
class SQueue {
public:
  void Push(const T& value);
  T Pop();
private:
  stack<T> st1;
  stack<T> st2;
};

template <class T>
T SQueue<T>::Pop()
{
  if (st2.size() <= 0)
  {
    if (st1.size() == 0)
    {
      exit(1);
    }
    while ((st1.size() > 0))
    {
      T& top = st1.top();
      st2.push(top);
      st1.pop();
    }
  }

  T head = st2.top();
  st2.pop();
  return head;

}

template <class T>
void SQueue<T>::Push(const T& value)
{
  st1.push(value);
}

int main()
{
  SQueue<int> sq;
  for (int i = 0; i < 10; ++i)
  {
    sq.Push(i);
  }
  for (int i = 0; i < 5; ++i)
  {
    cout << sq.Pop() << " ";
  }

  for (int i = 0; i < 5; ++i) //分两次验证
  {
    cout << sq.Pop() << " ";
  }
  cout << endl;

  system("pause");
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数组实现数据结构中的队列与堆栈

    JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • C#数据结构与算法揭秘五 栈和队列

    C#数据结构与算法揭秘五 栈和队列

    这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

  • 栈和队列数据结构的基本概念及其相关的Python实现

    先来回顾一下栈和队列的基本概念: 相同点:从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同. 不同点:栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表. 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表.它们是完全不同的数据类型.除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定". 栈必须按"后进先出"的规则进行操作:比如说,小学老师批改学生的作业,如果不打乱作业本的顺

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

  • LinkedList学习示例模拟堆栈与队列数据结构

    堆栈:先进后出First in Last Out FILO 如同一个杯子队列:先进先出 First in First out FIFO  如同一个水管 复制代码 代码如下: class Duilie{    private LinkedList link;    Duilie(){        link = new LinkedList();    }    public void myAdd(Object obj){        link.addFirst(obj);    }    pu

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

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

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

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

    数据结构用两个栈实现一个队列的实例 栈是先进后出,队列是先进先出 每次元素都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);

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

    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++基础学习之利用两个栈实现一个队列

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

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

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

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

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

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

  • Java数据结构专题解析之栈和队列的实现

    Java数据结构专题解析之栈和队列的实现

    目录 1. 栈 1.1 概念 1.2 助解图题 1.3 栈的数组实现 1.4 问题 1.5 栈的单链表实现 2. 队列 2.1 概念 2.2 问题 2.3 队列的单链表实现 2.4 数组实现队列 2.5 循环队列 2.6 双端队列 3. 栈和队列练习题 3.1 有效的括号 3.2 用队列实现栈 3.3 用栈实现队列 3.4 实现一个最小栈 3.5 设计循环队列 1. 栈 1.1 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

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

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

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

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

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

随机推荐