一 : 循环队列操作

不是只有排序，二叉树才叫数据结构，面试栽在基本的数组和队列，链表，栈的有的是！！！本文对循环队列的重要操作作出总结。[www.61k.com]注：为了避免队列空和满两个状态混淆，
采用空闲一个位置的方式，即N个元素空间的循环队列最多只能存放N-1个有效元素。这也是大多数教材的做法。
1) 循环队列初始化：front=rear=0；
2）入队操作：rear=(rear+1)%size;
3）出队操作：front=(front+1)%size;
4）判断是否为空队列：front==rear；
5）判断队列是否已满：front=(rear+1)%size；
6）遍历队列各元素。

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <stdbool.h> //注意使用布尔类型时，需要引入此头文件 /******************************************************************************************************************* 定义循环队列的结构体。注：循环队列是在数组的基础上实现的，所以需要一个指向首元素的指针，另外头和尾用int来表示相对偏移量即可。 ********************************************************************************************************************/ typedef struct Queue { int * qBase; int front; int rear; }QUEUE; void initQueue(QUEUE *pq); void enQueue(QUEUE *pq , int value); bool isemptyQueue(QUEUE *pq); bool is_fullQueue(QUEUE *pq); void deQueue(QUEUE *pq , int *value); void traverseQueue( QUEUE *pq); /***************************************** 主函数测试入口 ********************************************/ int main(){ int val; QUEUE queue = {NULL,0,0} ; initQueue(&queue); enQueue(&queue,4); enQueue(&queue,5); enQueue(&queue,6); enQueue(&queue,7); enQueue(&queue,72); enQueue(&queue,42); traverseQueue(&queue); deQueue(&queue , &val); deQueue(&queue , &val); traverseQueue(&queue); enQueue(&queue,55); enQueue(&queue,65); traverseQueue(&queue); return 0; } /**************************************初始化一个空的循环队列 ******************************************/ void initQueue(QUEUE *pq){ pq->qBase = (int *)malloc(sizeof(int)*6); if(pq->qBase == NULL){ printf("内存分配失败！n"); exit(-1); } pq->front = pq->rear = 0; } /***************插入一个新元素 注：插入前需要先判断该队列是否已满，避免覆盖有效数据******************/ void enQueue(QUEUE *pq , int value){ if(is_fullQueue(pq)){ printf("循环队列已满，拒绝插入%d！n",value); }　　　　else{ pq->qBase[pq->rear] = value; pq->rear = (pq->rear + 1)%6 ; printf("n %d 入队 n" , value); } } /************** 删除一个元素,并通过指针返回该数 注:删除前要判断该队列是否为空。*******************/ void deQueue(QUEUE *pq , int *value){ if(isemptyQueue(pq)){　　 printf("循环队列已空！"); }　　　else{ *value = pq->qBase[pq->front]; printf("n %d 出队 n",*value); pq->front = (pq->front + 1)%6 ; } } /************************************ 判断循环队列是否为空 ************************************/ bool isemptyQueue(QUEUE *pq){ if(pq->front == pq->rear){ return true; } else return false; } /************************************ 判断循环队列是否已满 ************************************/ bool is_fullQueue(QUEUE *pq){ if((pq->rear +1)%6 == pq->front){ return true; }else return false; } /************************************* 遍历循环队列中的各元素 *************************************/ void traverseQueue( QUEUE *pq){ if(isemptyQueue(pq)){ printf("循环队列为空!n"); exit(0); } printf("当前循环队列 :n"); printf("front是%d,rear是%d :n",pq->front,pq->rear); int tail = pq->front ; while(tail != pq->rear){ printf(" %d ",pq->qBase[tail]); tail = (tail + 1)%6; } }

二 : 队列之顺序队列与循环队列

一、队列的概念 只能在表的一端进行插入操作，只能在表的另一端进行删除操作，这种数据结构称为队列。把允许插入的一端叫队尾(rear)，允许删除的一端叫对头(front)。
二、队列的分类 队列本身也是一种线性表，因而和线性表一样也有顺序和链式存储结构两种存储方式。 采用顺序存储结构实现的队列称为顺序队列； 采用链式存储结构实现的队列称为链队列。
三、顺序队列1、顺序队列的表示①顺序队列用一个向量空间（一般使用一维数组）来存放当前队列中的元素。
　　②由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。
2、 顺序队列的基本操作
　　①入队时：将新元素插入rear所指的位置，然后将rear加1。
　　②出队时：删去front所指的元素，然后将front加1并返回被删元素。








注意：
　①当头尾指针相等时，队列为空。
②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。3、顺序队列中的溢出现象　　① "下溢"现象
　当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
　　② "真上溢"现象
　当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
　　③ "假上溢"现象
　　由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

四、循环队列为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（CircularQueue）。
1、 循环队列的基本操作
　循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
① 方法一：
if(i+1==QueueSize) //i表示front或rear
i=0;
else
i++;

② 方法二--利用"模运算"
i=(i+1)%QueueSize；

2、 循环队列边界条件处理
　循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
　解决这个问题的方法至少有三种：
　　① 另设一布尔变量以区别队列的空和满；
　　② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
　　③使用一个计数器记录队列中元素的总数（即队列长度）。

3、程序#define DataType int#define MAXSIZE 100
using namespace std;
typedef struct_CirQueue{DataType data[MAXSIZE];int front; //头指针，队非空时指向队头元素int rear; //尾指针，队非空时指向队尾元素的下一位置}CirQueue, *pCirQueue;
void InitQueue(pCirQueue pQueue);bool Empty(pCirQueuepQueue);bool InsertQueue(pCirQueue pQueue, DataType x);DataType OutQueue(pCirQueue pQueue);DataType GetHead(pCirQueuepQueue);int GetLength(pCirQueue pQueue);
int _tmain(int argc, _TCHAR* argv[]){int len = 0, data;CirQueue myQueue;InitQueue(&myQueue);if (!Empty(&myQueue)){printf("Queue is Empty");}InsertQueue(&myQueue, 1);InsertQueue(&myQueue, 2);InsertQueue(&myQueue, 3);InsertQueue(&myQueue, 4);len = GetLength(&myQueue);data = GetHead(&myQueue);while (Empty(&myQueue)){data = OutQueue(&myQueue);cout<<endl<<data;}return 0;}
//初始化：初始化一个新的队列void InitQueue(pCirQueue pQueue){memset(pQueue, 0, sizeof(CirQueue));}
//队列非空判断：若队列不为空，则返回true；否则返回false。bool Empty(pCirQueuepQueue){if (pQueue->front !=pQueue->rear){return true;}else return false;}
//入队列：在队列的尾部插入元素x，使元素x成为新的队尾。若 队列满，则返回false；否则，返回true。bool InsertQueue(pCirQueue pQueue, DataType x){if ((pQueue->rear+1)%MAXSIZE !=pQueue->front) //判断队列是否已满{pQueue->data[pQueue->rear] =x;pQueue->rear = (pQueue->rear +1)%MAXSIZE;return true;}elsereturn false;}
//出队列：若队列不为空，则返回对头元素，并从对头删除该元素，对头指针指向原对头的后记元素；否则，返回元素NULLDataType OutQueue(pCirQueue pQueue){DataType data;if (pQueue->front ==pQueue->rear){return NULL;}else{data =pQueue->data[pQueue->front];pQueue->front = (pQueue->front +1)%MAXSIZE;return data;}}
//取对头元素：若队列不空，则返回对头元素；否则，返回空元素NULLDataType GetHead(pCirQueue pQueue){if (pQueue->front ==pQueue->rear){return NULL;}else{returnpQueue->data[pQueue->front];}}
//求队列长度int GetLength(pCirQueue pQueue){int length = 0, number = 0;for (number = pQueue->front; number%MAXSIZE< pQueue->rear; number =(number+1)%MAXSIZE){length++;}return length;}
运行结果：

三 : 循环队列的基本操作

实验目的及要求：

了解和掌握循环队列的特点；

掌握循环队列基本操作的实现；

要求完成循环队列的初始化、入队、出队、求队列长度、显示操作的实现。 实验设备环境及要求：

PC机一台，内存要求128M以上，VC++6.0集成开发环境。

实验内容与步骤：

1、在VC++6.0环境中新建一个工程和C++文件；

2、实现循环队列初始化、入队、出队、求队列长度算法，代码如下：

#include <stdio.h>

#include <malloc.h>

#define MAXQSIZE 5

typedef char QElemType;

typedef struct {

QElemType *base;

int front;

int rear;

}SqQueue;

int InitQueue(SqQueue &Q){

Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base) return 0;

Q.front = Q.rear =0;

return 1;

}

int QueueLength(SqQueue Q){

return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;

}

int EnQueue(SqQueue &Q,QElemType e){

if((Q.rear+1) % MAXQSIZE == Q.front) {

printf("队列为满队列！！n");

return 0;}

Q.base[Q.rear] = e;

Q.rear = (Q.rear+1) % MAXQSIZE;

return 1;

}

int DeQueue(SqQueue &Q,QElemType &e){ if(Q.front == Q.rear) return 0;

e = Q.base[Q.front];

Q.front = (Q.front+1) %MAXQSIZE; return 1;

}

void DispQueue(SqQueue Q){

int m,i;

m = QueueLength(Q);

if(m ==0) printf("该队列为空队列！！n"); for(i = Q.front; i%MAXQSIZE!=Q.rear; i++) printf("%c",Q.base[i]);

printf("n");

}

void main(){

SqQueue Q;

QElemType e;

InitQueue(Q);

DispQueue(Q);

EnQueue(Q,'A');

EnQueue(Q,'B');

EnQueue(Q,'C');

EnQueue(Q,'D');

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

DeQueue(Q,e);

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

EnQueue(Q,'E');

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

EnQueue(Q,'F');

printf("队列为:");

DispQueue(Q);

}

实验指导与数据处理：

实验结果：该队列为空队列！！

队列长度为：4

队列为:ABCD

队列长度为：3

队列为: BCD

队列长度为：4

队列为: BCDE

队列为满队列！！

队列为: BCDE

分析讨论：

本次实验通过对循环队列基本操作的实现，加深了对循环队列特点的理解，并且熟悉了VC++6.0集成环境，虽然在调试过程中遇到一些问题，但经分析后达到了预期的结果。

四 : 循环队列的基本操作

实验目的及要求：

了解和掌握循环队列的特点；

掌握循环队列基本操作的实现；

要求完成循环队列的初始化、入队、出队、求队列长度、显示操作的实现。(www.61k.com） 实验设备环境及要求：

PC机一台，内存要求128M以上，VC++6.0集成开发环境。

实验内容与步骤：

1、在VC++6.0环境中新建一个工程和C++文件；

2、实现循环队列初始化、入队、出队、求队列长度算法，代码如下：

#include <stdio.h>

#include <malloc.h>

#define MAXQSIZE 5

typedef char QElemType;

typedef struct {

QElemType *base;

int front;

int rear;

}SqQueue;

int InitQueue(SqQueue &Q){

Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base) return 0;

Q.front = Q.rear =0;

return 1;

}

int QueueLength(SqQueue Q){

return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;

}

int EnQueue(SqQueue &Q,QElemType e){

if((Q.rear+1) % MAXQSIZE == Q.front) {

printf("队列为满队列！！n");

return 0;}

Q.base[Q.rear] = e;

Q.rear = (Q.rear+1) % MAXQSIZE;

循环队列 循环队列的基本操作

return 1;

}

int DeQueue(SqQueue &Q,QElemType &e){ if(Q.front == Q.rear) return 0;

e = Q.base[Q.front];

Q.front = (Q.front+1) %MAXQSIZE; return 1;

}

void DispQueue(SqQueue Q){

int m,i;

m = QueueLength(Q);

if(m ==0) printf("该队列为空队列！！n"); for(i = Q.front; i%MAXQSIZE!=Q.rear; i++) printf("%c",Q.base[i]);

printf("n");

}

void main(){

SqQueue Q;

QElemType e;

InitQueue(Q);

DispQueue(Q);

EnQueue(Q,'A');

EnQueue(Q,'B');

EnQueue(Q,'C');

EnQueue(Q,'D');

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

DeQueue(Q,e);

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

EnQueue(Q,'E');

printf("队列长度为：");

printf("%dn",QueueLength(Q));

printf("队列为:");

DispQueue(Q);

EnQueue(Q,'F');

printf("队列为:");

循环队列 循环队列的基本操作

DispQueue(Q);

}

实验指导与数据处理：

实验结果：该队列为空队列！！

队列长度为：4

队列为:ABCD

队列长度为：3

队列为: BCD

队列长度为：4

队列为: BCDE

队列为满队列！！

队列为: BCDE

分析讨论：

本次实验通过对循环队列基本操作的实现，加深了对循环队列特点的理解，并且熟悉了VC++6.0集成环境，虽然在调试过程中遇到一些问题，但经分析后达到了预期的结果。（www.61k.com]

五 : C++类模板实现循环队列

以下是本人用C++类模板实现的一种数据结构——循环队列。希望对人们有所帮助，也希望人们提出宝贵的意见！

//循环队列

#ifndef _QUEUE_H_INCLUDED
#define _QUEUE_H_INCLUDED

template<typename T>
class _queue
{
  public:
    _queue(size_t _capacity = 1):capacity(_capacity), length(0), pBase(new T[_capacity]),
                pHead(pBase), pLast(pBase){}
    ~_queue(){delete []pBase;}
    void ClearQueue()
    {
      pHead = pBase;
      pLast = pBase;
      length = 0;
    }
    bool IsEmpty()const {return !length;}
    size_t GetLength()const {return length;}
    T& GetHead()const {return *pHead;}
    void Push(T &e);
    T Pop();
    void vist();
  private:
    void NewMenory();
    void Insert(T &e);
    size_t capacity;
    size_t length;
    T *pBase;
    T *pHead;
    T *pLast;
};
template<typename T>
void _queue<T>::NewMenory()
{
  T *ptmpNew(new T[2*capacity]);
  T *ptmpNewCopy(ptmpNew);
  T *ptmpheadCopy(pHead);
  T *ptmplimit(pBase + capacity -1);

  for(int i = 0; i <capacity; ++i)
  {
    *ptmpNewCopy = *ptmpheadCopy;
    if(ptmpheadCopy == ptmplimit)
    {
      ptmpheadCopy = pBase;
      continue;
    }
    ++ptmpNewCopy;
    ++ptmpheadCopy;
  }
  delete []pBase;
  pBase = ptmpNew;
  pHead = pBase;
  pLast = pBase + capacity;
  capacity *= 2;
}

template<typename T>
void _queue<T>::Insert(T &e)
{
  if(pLast != (pBase + capacity))
  {
    *pLast = e;
    ++pLast;
  }
  else
  {
    *pBase = e;
    pLast = pBase + 1;
  }
}

template<typename T>
void _queue<T>::Push(T &e)
{
  ++length;

  if(length > capacity)
    NewMenory();

  Insert(e);
}

template<typename T>
T _queue<T>::Pop()
{
  if(length > 0)
  {
    --length;
    if(pHead == pBase + capacity -1)
    {
      T tmp(*pHead);
      pHead = pBase;
      return tmp;
    }
    return *(pHead++);

  }
  return *pBase;
}

template<typename T>
void _queue<T>::vist()
{
  T *ptmphead(pHead);
  T * const ptmplimit(pBase + capacity);
  for(int i = 0; i<length; ++i)
  {
    if(ptmphead == ptmplimit)
      ptmphead = pBase;

    std::cout<<" '"<<*ptmphead<<"' ";
    ++ptmphead;
  }
}

#endif // _QUEUE_H_INCLUDED

本文标题：循环队列-循环队列操作
本文地址： http://www.61k.com/1112856.html