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

2024-11-29 01:33:04

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

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

用两个栈实现一个队列。是一个比较经典的问题。

看到这个问题，我的第一个解题思路为：

定义两个栈，s1,s2。s1作为入队列栈，s2作为出队列栈；

入队列：每次入队列的时候，将数值压入s1栈中；

出队列：出队列时，将s1中的所有数据，压进s2栈中，然后删除s2的栈顶数据，然后再将s2中的剩余数据压入s1中。

在这其中s1是一个存储空间，s2是一个辅助空间。

进一步想一下上述办法，在出队列时，每一次都要将s1倒进s2，然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数；

入队列时：将数据压进s1;

出队列时：判断如果s2为空，那么将s1中的数据，压进s2中，然后删除s2栈顶，如果s2不为空那么再删除s2的栈顶即可；

并且还可以优化，优化如下：

出队列时，判断如果s2为空，那么将s1中n-1个数据，压进s2中，然后删除s1中的栈顶，如果s2不为空那么直接删除s2的栈顶即可；

优化版的c++实现如下：

#include<iostream>
using namespace std;
#include<stack>
//栈 后进先出 队列 先进先出
template<class T>
class Queue
{
public: 

  /*T Pop_back()
  {
    if (s2.size() <= 0)
    {
      while(s1.size() > 0)
      {
        T& temp = s1.top();
        s1.pop();
        s2.push(temp);
      }
    }
    if (s2.size() == 0)
      throw new exception("queue is empty "); 

    T tep = s2.top();
    s2.pop();
    return tep;
  }*/ 

  T Pop_back() //比上面少一次出栈
  {
    if (s2.size() <= 0)
    {
      while (s1.size() > 1)
      {
        T& temp = s1.top();
        s1.pop();
        s2.push(temp);
      }
      T tep = s1.top();
      s1.pop();
      return tep;
    }
    else{
      T tep = s2.top();
      s2.pop();
      return tep;
    }
  } 

    void Push_back(const T& value)
  {
    s1.push(value);
  } 

    bool Empty()
    {
      return (s1.empty() && s2.empty());
    }       

protected:
  stack<T> s1;
  stack<T> s2;
}; 

void TextQueue()
{
  Queue<int> q1;
  q1.Push_back(1);
  q1.Push_back(2);
  q1.Push_back(3);
  q1.Push_back(4); 

  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
}

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

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++无锁队列的实现代码

本文给出一种C++无锁队列的实现代码,主要用于一个线程读取数据另外一个线程写数据复制代码代码如下: #ifndef LOCK_FREE_QUEUE_H_#define LOCK_FREE_QUEUE_H_ //不加锁队列,适合一个线程读取,一个线程写#include <list>template <typename T>class LockFreeQueue{ public: LockFreeQueue() { list
C++ 数据结构之kmp算法中的求Next()函数的算法

C++ 数据结构之kmp算法中的求Next()函数的算法实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++
C++ 中消息队列函数实例详解

C++ 中消息队列函数实例详解 1.消息队列结构体的定义 typedef struct{ uid_t uid; /* owner`s user id */ gid_t gid; /* owner`s group id */ udi_t cuid; /* creator`s user id */ gid_t cgid; /* creator`s group id */ mode_t mode; /* read-write permissions 0400 MSG_R 0200 MSG_W*/ ul
C++循环队列实现模型

本文实例讲述了C++循环队列实现模型.分享给大家供大家参考.具体分析如下: 前段时间在知乎上看到这样一个小题目: 用基本类型实现一队列,队列要求size是预先定义好的的.而且要求不可以使用语言自带的api,如C++的STL.普通的实现很简单,但是现在要求要尽可能的时间和空间复杂度的优化,要和语言自带的api比较时间和空间.这个队列还要支持如下的操作: constructor: 初始化队列 enqueue:入队 dequeue:出队队列是一种基本的数据结构,在平常的应用中十分广泛,多数情况队列都
C++数据结构之实现循环顺序队列

数据结构–用C++实现循环顺序队列队列的操作特性:先进先出队列中元素具有相同类型相邻元素具有前驱和后继关系设置队头.队尾两个指针,以改进出队的时间性能约定:队头指针front指向队头元素的前一个位置,队尾指针rear指向队尾元素为了解决假溢出,我们将存储队列的数组头尾相接,从而产生了循环队列. 如何判断循环队列队空? 队空:front=rear 如何盘对循环队列堆满? 队满:front=rear 那么问题就来了,队空和队满的判断条件相同,为了避免队满时产生队空的判断或者相反,我们需要
C++数据结构与算法之双缓存队列实现方法详解

本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之
C++ STL入门教程(3) deque双向队列使用方法

一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&
C++中用两个标准容器stack,实现一个队列的方法详解

代码如下所示: 复制代码代码如下: // StackToQueue.cpp : 定义控制台应用程序的入口点.//用两个标准容器stack,实现一个队列#include "stdafx.h"#include <iostream>#include <stack>using namespace std;template <class T>class StackToQueue{public: StackToQueue() { stack1; stack
C++非递归队列实现二叉树的广度优先遍历

本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu
C++数据结构与算法之判断一个链表是否为回文结构的方法

本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构
C++中队列的建立与操作详细解析

什么是队列结构队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则.而从数据的逻辑结构来看,队列结构其实就是一种线性结构.如果从数据的存储结构来进一步划分,队列结构可以分成两类. 顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据.在程序中,可以定义一个指定大小的结构数组来作为队列. 链式队列结构:即使用链表形式保存队列中各元素的值. 在队列结构中允许对两端进行操作,但是两端的操作不同.在表的一端只能进行删除操作,称为队头:在表的另一端只能进行插入操作,称为队尾.如果队

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

相关推荐

随机推荐