循环队列的顺序存储结构基本实现（C++）-白红宇

循环队列的顺序存储结构基本实现（C++）

阅读量：4049 次

发布时间：2019-05-25

本文共 2493 字，大约阅读时间需要 8 分钟。

队列的顺序存储结构和链表的顺序存储结构非常的相近。为了降低队列的输出时间复杂度，将队列设置为循环队列，基本原理“大话数据结构”讲的很清楚，这里列出接个关键点：

1、判断队列为空的条件	front==rear   //其中front为指向头元素的下标，rear为指向尾元素的下标的下一位置2、判断队列为满的条件	(rear+1)%MAXSIZE   //其中MAXSIZE为允许队列的最大长度	值得注意的是为了区分空和满，定义比队列预设长度小1为满3、计算队列长度的关系式	(rear-front+MAXSIZE)%MAXSIZE	这样做的目的是在情况rear小于front时

函数说明

template
   
    class Queue{
   private:	T data[MAXSIZE];   //定义队列最大长度	int front;    //指向队列首元素	int rear;    //指向队列尾元素的下一位置public:	Queue();   //构造函数	bool isEmpty() const;   //判断队列是否为空	bool isFull() const;   //判断队列是否为满	bool EnQueue(T &e);   //将元素e插入队列	T DeQueue();   //删除头元素并返回	int Length() const;   //返回队列的长度};

使用示例结果

Enter the arrival customer name:bndrbsdfThere have 1 customers.Enter the arrival customer name:bsrtmndtyThere have 2 customers.Enter the arrival customer name:bwsnetyThere have 3 customers.Enter the arrival customer name:gbwerbtedThere have 4 customers.bndrbsdf leave, and 3 people remain.bsrtmndty leave, and 2 people remain.bwsnety leave, and 1 people remain.gbwerbted leave, and 0 people remain.

头文件

#	pragma once#ifndef QUEUEV2_H_#define QUEUEV2_H_#define MAXSIZE 5template
   
    class Queue{
   private:	T data[MAXSIZE];	int front;	int rear;public:	Queue();	bool isEmpty() const;	bool isFull() const;	bool EnQueue(T &e);	T DeQueue();	int Length() const;};template
    
     Queue
     
      ::Queue(){
   	front = 0;	rear = 0;}template
      
       bool Queue
       
        ::isEmpty() const{
   	return(front == rear);}template
        
         bool Queue
         
          ::isFull() const{ return((rear + 1) % MAXSIZE == front);}template
          
           bool Queue
           
            ::EnQueue(T &e){ if (isFull()) { cout << "The queue is full!!!\n"; return false; } else { data[rear] = e; rear = (rear + 1) % MAXSIZE; return true; }}template
            
             T Queue
             
              ::DeQueue(){ if (isEmpty()) { cout << "The queue is empty!!!\n"; exit(EXIT_FAILURE); } else { T e = data[front]; front = (front + 1) % MAXSIZE; return e; }}template
              
               int Queue
               
                ::Length() const{ return(rear - front + MAXSIZE) % MAXSIZE;}#endif // !QUEUEV2_H_

使用示例

#include
   
    #include
    
     #include
     
      #include
      
       #include"queuev2.h"using namespace std;void main(){
   	Queue
       
         test;	srand(time(0));	while (!test.isFull()) {
   		cout << "Enter the arrival customer name: \n";		string name;		getline(cin, name);		test.EnQueue(name);		cout << "There have " << test.Length() << " customers.\n\n";	}	while (!test.isEmpty()) {
   		cout << test.DeQueue() << " leave, and ";		cout << test.Length() << " people remain.\n";	}}