C++数据结构之实现循环顺序队列

数据结构–用C++实现循环顺序队列

  • 队列的操作特性：先进先出
  • 队列中元素具有相同类型
  • 相邻元素具有前驱和后继关系
  • 设置队头、队尾两个指针，以改进出队的时间性能

约定：队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素

为了解决假溢出，我们将存储队列的数组头尾相接，从而产生了循环队列。

如何判断循环队列队空？

队空：front=rear

如何盘对循环队列堆满？

队满：front=rear

那么问题就来了，队空和队满的判断条件相同，为了避免队满时产生队空的判断或者相反，我们需要修改队满条件使得队空和堆满的判定条件分开。
方法：浪费一个元素空间，队满时数组只有一个空闲单元。队满条件：(rear+1)%QueueSize==front

下面是实现代码：

文件CirQueue.h

#ifndef CirQueue_byNim
#define CirQueue_byNim

#include<iostream>
using namespace std;

const int QueueSize=100;  //循环队列的最大存储空间
template <class T>
class CirQueue
{
  private:
    T *data;  //存储数据的数组
    int front,rear; //队头队尾指针
  public:
    CirQueue()
    {
      data=new T[QueueSize];
      front=rear=0;
    }
    ~CirQueue()
    {
      delete []data;
      front=rear=0;
    }
    void EnQueue(T e)
    {
      if((rear+1)%QueueSize==front)  //队满条件
        throw "上溢";
      rear=(rear+1)%QueueSize;
      data[rear]=e;
    }
    T DeQueue()
    {
      if(rear==front)//队空条件
        throw "下溢";
      front=(front+1)%QueueSize;
      return data[front];
    }
    T GetQueue()
    {
      if(rear==front)//队空条件
        throw "下溢";
      return data[(front+1)%QueueSize];
    }
    bool empty()
    {
      if(front==rear) //队空条件：front==rear
        return true;
      return false;
    }
};

#endif

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

赞 (0)

相关推荐

  • C++循环队列实现模型

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

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

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

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    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++数据结构与算法之双缓存队列实现方法详解

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

  • 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++中队列的建立与操作详细解析

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

  • 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++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • 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++ STL入门教程(3) deque双向队列使用方法

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

  • 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++无锁队列的实现代码,主要用于一个线程读取数据另外一个线程写数据 复制代码 代码如下: #ifndef LOCK_FREE_QUEUE_H_#define LOCK_FREE_QUEUE_H_ //不加锁队列,适合一个线程读取,一个线程写#include <list>template <typename T>class LockFreeQueue{    public:        LockFreeQueue()        {             list

随机推荐