C++实现循环队列和链式队列的示例

循环队列:

1.循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%maxSize。(我曾经想过为什么不用一个length表示队长,当length==maxSize时队满)原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算。

2.用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况。

template<class T>
class SeqQueue{
 protected:
  T *element;
  int front,rear;
  int maxSize;
 public:
  SeqQueue(int sz=10){
   front=rear=0;
   maxSize=sz;
   element=new T[maxSize];
  }
  ~SeqQueue(){
   delete[] element;
  }
  bool EnQueue(const T& x){//入队
   if(isFull()) return false;
   element[rear]=x;
   rear=(rear+1)%maxSize;
   return true;
  }
  bool DeQueue(T& x){//出队
   if(isEmpty()) return false;
   x=element[front];
   front=(front+1)%maxSize;
   return true;
  }
  bool getFront(T& x){//获取队首元素
   if(isEmpty()) return false;
   x=element[front];
   return true;
  }
  void makeEmpty(){//队列置空
   front=rear=0;
  }
  bool isEmpty()const{//判断队列是否为空
   return (rear==front)?true:false;
  }
  bool isFull()const{//队列是否为满
    return ((rear+1)%maxSize==front)?true:false;
  }
  int getSize()const{
   return (rear-front+maxSize)%maxSize;
  }
};

测试代码如下:

void menu(){
 cout<<"1.入队"<<endl;
 cout<<"2.获取队首元素"<<endl;
 cout<<"3.出队"<<endl;
 cout<<"4.队列置空"<<endl;
 cout<<"5.获取队中元素数量"<<endl;
 cout<<"6.退出"<<endl;
}
void function(int num,SeqQueue<int> *sq){
 switch(num){
  int x;
  case 1:
   cin>>x;
   sq->EnQueue(x);
   break;
  case 2:
   sq->getFront(x);
   cout<<x<<endl;
   break;
  case 3:
   sq->DeQueue(x);
   break;
  case 4:
   sq->makeEmpty();
   break;
  case 5:
   x=sq->getSize();
   cout<<x<<endl;
   break;
  default:
   exit(1);
 }
}
int main(int argc, char** argv) {
 SeqQueue<int> *sq=new SeqQueue<int>;
 int num;
 while(true){
  menu();
  cin>>num;
  function(num,sq);
 }
 delete sq;
 return 0;
}

之后是链式队列,实现类代码和测试代码如下:

#include <iostream>
using namespace std;
template<class T>
struct LinkNode{
 T data;
 LinkNode<T> *link;
 LinkNode(T& x,LinkNode<T> *l=NULL){
  data=x;
  link=l;
 }
};
template<class T>
class LinkedQueue{
 protected:
  LinkNode<T> *front,*rear;
 public:
  LinkedQueue(){
   front=rear=NULL;
  }
  ~LinkedQueue(){
   makeEmpty();
  }
  bool enQueue(T& x){
   if(front==NULL)
    front=rear=new LinkNode<T>(x);
   else{
    rear=rear->link=new LinkNode<T>(x);
   }
   return true;
  }
  bool deQueue(T& x){
   if(isEmpty()) return false;
   LinkNode<T> *p=front;
   x=front->data;
   front=front->link;
   delete p;
   return true;
  }
  bool getFront(T& x)const{
   if(isEmpty()) return false;
   x=front->data;
   return true;
  }
  void makeEmpty(){
   LinkNode<T> *p;
   while(front!=NULL){
    p=front;
    front=front->link;
    delete p;
   }
  }
  bool isEmpty()const{
   return (front==NULL)?true:false;
  }
  int getSize()const{
   LinkNode<T> *p;
   int count=0;
   p=front;
   while(p!=NULL){
    count++;
    p=p->link;
   }
  return count;
  }
};
void menu(){
 cout<<"1.入队"<<endl;
 cout<<"2.获取队首元素"<<endl;
 cout<<"3.出队"<<endl;
 cout<<"4.队列置空"<<endl;
 cout<<"5.获取队中元素数量"<<endl;
 cout<<"6.退出"<<endl;
}
void function(int num,LinkedQueue<int> *lq){
 switch(num){
  int x;
  case 1:
   cin>>x;
   lq->enQueue(x);
   break;
  case 2:
   lq->getFront(x);
   cout<<x<<endl;
   break;
  case 3:
   lq->deQueue(x);
   break;
  case 4:
   lq->makeEmpty();
   break;
  case 5:
   x=lq->getSize();
   cout<<x<<endl;
   break;
  default:
   exit(1);
 }
}
int main(int argc, char** argv) {
 LinkedQueue<int> *lq=new LinkedQueue<int>;
 int num;
 while(true){
  menu();
  cin>>num;
  function(num,lq);
 }
 delete lq;
 return 0;
}

以上这篇C++实现循环队列和链式队列的示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 详解数据结构C语言实现之循环队列

    本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize

  • C语言循环队列的表示与实现实例详解

    1.概述: C语言的队列(queue),是先进先出(FIFO, First-In-First-Out)的线性表数据结构.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 循环队列可以更简单的防止伪溢出的发生,但是队列大小是固定的. 2.实例代码: /* 队列的顺序存储结构(循环队列) */ #define MAX_QSIZE 5 /* 最大队列长度+1 */ typedef struct { QElemType *base

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

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

  • 循环队列详解及队列的顺序表示和实现

    循环队列--队列的顺序表示和实现 前面分析顺序队的时候,我们知道,顺序队存在"假溢出"的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在: 相同点: 在顺序队列和循环队列中,进行出队.入队操作时,队首.队尾指针都要加 1 ,朝前移动. 不同点: 1. 在循环队列中当队首.队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结

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

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

  • C++实现循环队列和链式队列的示例

    循环队列: 1.循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%maxSize.(我曾经想过为什么不用一个length表示队长,当length==maxSize时队满)原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算. 2.用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况. template<class T> class SeqQueue{ protected: T

  • java队列实现方法(顺序队列,链式队列,循环队列)

    双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略.ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列.ArrayDeque和LinkedList都是线程不安全的.PriorityQueue优先队列也在JDK. 1.顺序队列的实现 package lang; import java.io.Serializable; import java.util.Arrays; /** * @ClassName: ArrayQueue *

  • PHP实现的链式队列结构示例

    本文实例讲述了PHP实现的链式队列结构.分享给大家供大家参考,具体如下: <?php header("Content-Type:text/html;charset=utf-8"); /** * 链式队列 */ class node{ public $nickname; public $next; } class queue { public $front;//头部 public $tail;//尾部 public $maxSize;//容量 public $next;//指针 p

  • 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. 二叉树的遍历 2.1 前序遍历 2.2 中序遍历 2.3 后序遍历 2.4 层序遍历 3. 常见功能 3.1 二叉树结点个数 3.2 二叉树叶子结点个数 3.3 第K层结点的个数 3.4 二叉树的深度 3.5 判断是不是树是不是完全二叉树 3.6 在二叉树中查找值为x的结点 3.7 拿到每一层的数据 4. 二叉树的创建和销毁 4.1 二叉树的创建 4.2 二叉树的销毁 前言 前面我们已经对堆进行学习,堆就是一个顺序结构的二叉树,把数组看成二叉树,下面一起学

  • JS实现线性表的链式表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的链式表示方法.分享给大家供大家参考,具体如下: 从上一节可以,顺序存储结构的弱点就是在插入或删除操作时,需要移动大量元素.所以这里需要介绍一下链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构的弱点,但是也没有顺序表可随机存取的优点. 下面介绍一下什么是链表. 线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素.所以,每一个数据元素除了存储自身的信息之外,还需要存储一个指向其后继的存储位置的信息.这两部分信息组成了元素的存

  • php数据结构之顺序链表与链式线性表示例

    本文实例讲述了php数据结构之顺序链表与链式线性表.分享给大家供大家参考,具体如下: 链表操作 1.     InitList(L):初始化链表 2.     DestroyList(L):删除连接 3.     ClearList(L):清空链表 4.     ListEmpty(L):判断是否为空 5.     ListLength(L):链表长度 6.     getElem(L,i):取出元素 7.     LocateElem(L,e):判断e是否在链表中 8.     PriorEl

  • C语言详解链式队列与循环队列的实现

    目录 队列的实现 链式队列 链式队列的定义 链式队列的实现 循环队列 循环队列的定义 循环队列的实现 队列的实现 队列是一种先进先出(First in First Out)的线性表,简称FIFO.与栈不同,栈是一种后进先出(先进后出)的线性表.在队列中,允许插入的一端称为队尾,允许删除的一端称为队头.假设队列是q=(a1,a2,…,an),那么a1就是队头元素,而an是队尾元素.这样我们就可以删除时,总是从a1开始,而插入时,列在最后.这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后

  • 队列的动态链式存储实现代码分享

    复制代码 代码如下: #include <stdlib.h>#include <malloc.h>#include <memory.h>#include <assert.h>#include "DynaLnkQueue.h" /*------------------------------------------------------------操作目的: 初始化队列初始条件: 无操作结果: 构造一个空的队列函数参数:  LinkQue

  • C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

随机推荐