循环队列中的delete

循环队列

2018-10-18 15:57:05

文章目录循环队列1，循环队列2，C语言实现循环队列3，OOP实现循环队列 1，循环队列 队列的操作特点是“先进先出”。为充分利用向量空间，克服&quot;假溢出&quot;现象的方法是：将向量空间想象为一...

循环队列
文章目录
循环队列
1，循环队列
2，C语言实现循环队列
3，OOP实现循环队列

1，循环队列
队列的操作特点是“先进先出”。为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
在循环队列中，front和rear都是可以移动的。

当队列为空或满时，front = rear都成立，所以不能用这个条件来判断队列是空的还是满的。

为了解决这个问题，在循环队列中有一个约定：

少用一个元素空间，当队尾标识rear在队头标识front的上一个位置时，队列为满。此时，判断队列空和满的条件为：

队空：front== rear；

队满:   (rear+1)%MAXNUM== front  (MAXNUM为队列容量的大小)
循环队列中front和rear的移动不再是简单的加1，因为原本是循环的，所以可能原本指在末尾，前进一个单位就是又一个循环的开始，故每次移动都要对MAXNUM取模：

front = (front+1)%MAXNUM

rear = (rear+1)%MAXNUM
求队列长度也不是简单的front和rear相减，因为rear的值有可能比front小。

循环队列求队列长度的方法：（rear-front+MAXNUM）%MAXNUM


2，C语言实现循环队列
#include<stdio.h>
#include<assert.h>
#define SIZE 8
typedef struct Queue
{
	int elem[SIZE];//数组
	int front;//头
	int rear;//尾
}Queue,*QueueS;

void InitQueueS(QueueS queue)           //初始化
{
    asesrt(queue!=NULL);
    queue->front=0;
    queue->rear=0;
}
bool Push(QueueS queue,int val)         //入队
{
    assert(queue!=NULL);
    if(IsFull(queue))
    {
     return false;
    }
    queue->elem[queu->rear]=val;
    queue->rear=(queue->rear+1)%SIZE;
    return true;
}
bool Pop(QueueS queue,int *rtv)       //出队
{
    assert(queue!=NULL)
    if(IsEmpty(queue))
    {
        return false;
    }
    if(rtv!=NULL)
    {
        *rtv=queue->elem[queue->front];
    }
    queue->front=(queue->front+1)%SIZE;
    return true;
}
void Show(QueueS queue)
{
    for(int i=queue->front;i!=queue->rear;i=(i+1)%SIZE)
    {
        printf("%d ",queue->elem[i]);
    }
    printf("\n");
}
int GetLength(QueueS queue)      //获取长度
{
    return (queue->rear-queu->front+SIZE)%SIZE;
}
bool IsFull(QueueS queue)        //判满
{
    return (queue->rear+1)%SIZE==queue->front;
}
bool IsEmpty(QueueS queue)         //判空
{
    return queue->front==queue->rear;
}
void Clear(QueueS queue)
{
    queue->front=queue->rear;
}
void Destroy(QueueS queue)
{
    Clear(queue);
}

3，OOP实现循环队列
#include<iostream>
using namespace std;
class CQueue
{
public:
    CQueue(int size=10)
    {
        mfront=mrear=0;
        msize=size;
        mqueue=new int[msize];
    }
   /* CQueue(int size=10):mfront(0),mrear(0),msize(size)
    {
        mqueue=new int [msize];
    }
    */
    ~CQueue()
    {
        delete[]mqueue;
        mqueue=NULL;
    }
    CQueue(const CQueue&src)
    {
        mfront=src.mfront;
        mrear=src.mrear;
       mszie=src.msize;
        mqueue=new int [msize];
        for(int i=mfront;i!=mrear;i=(i+1)%msize)
        {
            mqueue[i]=src.mqueue[i];
        }
    }
    void operator=(const CQueue&src)
    {
        if(this==&src)
        {
            return ;
        }
        delete[]mqueue;
        mqueue=NULL;
        mfront=src.mfront;
        mrear=src.mrear;
        mszie=src.msize;
        mqueue=new int [msize];
        for(int i=mfront;i!=mrear;i=(i+1)%msize)
        {
            mqueue[i]=src.mqueue[i];
        }
    }
    void push(int val)
    {
        if(full())
        {
            return;
        }
        mqueue[mrear]=val;
        mrear=(mrear+1)%msize;
    }
    void pop()
    {
        if(empty())
        {
            return;
        }
        mfront=(mfront+1)%msize;
    }
    int front()
    {
        return mqueue[mfront];
    }
    int back()
    {
        if(mrear==0)
        {
            return mqueue[msize-1];
        }
        else
        {
            return mqueue[mrear-1];
        }
    }
    bool full()
    {
        return (mrear+1)%msize==mfront;
    }
    bool empty()
    {
        treturn mrear==mfront;
    }
    void show()
    {
        for(int i=mfront;i!=mrear;i=(i+1)%msize)
        {
            cout<<mqueue[i]<<" ";
        }
    }
 private:
    int*mqueue;
    int mfront;
    int mrear;
    int msize;
    void resize()
    {
        int *mtmp=new int[msize*2];
        for(int i=mfront,j=0;i!=mrear;i=（i+1）%msize,j++)
        {
            mtmp[j]=mqueue[i]
        }
        delete[]mqueue;
        mqueue=mtmp;
        mfront=0;
        mrear=msize-1;
        msize*=2;
    }
};

收起

展开全文

循环队列–C语言实现–数据结构

万次阅读 多人点赞 2017-06-22 16:36:45

循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录一要求二 循环队列 三 循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队四程序 1 程序的结构 2 程序源码五程序测试 1 ...

循环队列–C语言实现–数据结构

目录


循环队列C语言实现数据结构目录

一 要求
二 循环队列
三 循环队列的算法设计1 建立循环队列
2 置空队列
3 入队
4 出队
5 打印队

四 程序1 程序的结构
2 程序源码

五 程序测试1 入队列
2 出队列
3 打印队列

六 源程序及封装软件下载下载地址格格是一枚智能专业的本科在校生很愿意和各位大佬交流如果大家有愿意交朋友的可以加格格的QQ446019725声明是CSDN即可






（一） 要求


  假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。


（二） 循环队列


  定义：为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现, 当然也可以利用顺序表来实现。顺序表就是我们熟悉的数组 eg. sun[] 。 
回顾：我们再来回顾一下关于顺序队列的重要知识点。队列通常与栈对应，栈是一种后进先出的单端（尾端）处理的数据结构；那么与之对应的队列是一种先进先出的双端（头尾两端）的数据结构。队列的特点就是在一段进行入队（存储数据）操作，在另一端进行出队（删除数据）操作。 
为什么设计循环队列：大家在处理队列的时候，会遇到如下情况。例如说：我们的队列空间能够容纳1000个元素。首先，格格入队1000个元素，队列上溢，此时为“真溢出”。那么现在我们进行出队操作，我们一直出队，一直出队， 知道1000个元素全部被删除，此时我们发现队列仍然处于“上溢”状态，why？ 其实原因很简单，在非循环队列当中，无论我们的front指（偏移）到哪里，只要我们的rear指（偏移）向上阙，那么队列就是“满溢”的。这就造成了空间明明还被占据着，但是队列却已经无用武之地的窘境。对于空间有限的计算机来说，这无疑是一种浪费。也不是一个优秀的程序猿想要看到的。所以在这种情况下，循环队列诞生了。循环队列当中的“满溢”只有一种情况，那就是所有数据空降都被占领了。而不会存在非循环队列当中的“假溢出”现象。



  我们所常见的顺序循环队列通常有两种数据结构。


结构一



typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  front,rear;
    //front表示队列头的偏移量，rear表示队列的尾的偏移量
}qu;//qu是队列（queue）的缩写



结构二



typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  rear, quelen;
    //rear表示队列的尾的偏移量，quelen表示的是队列中元素的个数
}qu;//qu是队列（queue）的缩写


  那通过观察这两种机构我们能够很容易的发现，数据结构并不是固定的。我们觉得那种算法比较更合理，我们觉得哪种数据结构方便我们设计算法，那么我们就建立哪种数据结构。在本文当中，我们采用第二种数据结构。显而易见的是，当我们采用第二种数据结构时，我们建立的一个队列指针（qu*sq）队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。


（三） 循环队列的算法设计

在上面我们了解了循环队列的数据机构，但是仅仅学会了数据结构还远远不够。我们设计数据结构的目的是为了更好的存储数据，并利用数据。下面我们来看一看关于循环队列我们要掌握哪些最基本的算法（利用数据机构）。

3.1 建立循环队列



//建立队
qu* creatqueue();//函数声明
qu* creatqueue()//函数实现
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}

3.2 置空队列



//置空队
void setnull(qu*);//函数声明
void setnull(qu *sq)//函数实现
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

3.3 入队



//入队
void enqueue(qu*, datatype);//函数声明
void enqueue(qu*sq, datatype x)//函数实现
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}



3.4 出队



//出队
datatype *dequeue(qu*);//函数声明
datatype *dequeue(qu*sq)//函数实现
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}




3.5 打印队



//打印队
void print(qu*);//函数声明
void print(qu*sq)//函数定义
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}

（四） 程序

下面我们来设计一个程序测试我们的数据机构与算法

4.1 程序的结构



4.2 程序源码

注意：该程序由Microsoft Visual Studio Enterprise 2015编译器进行调试。受制于编译器品牌及版本不同等不可抗因素造成的编译失败，请自行调整。



#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define m 5

//循环队列的结构类型定义
typedef int datatype;
typedef struct
{
    datatype sequ[m];
    int  rear, quelen;
}qu;

//函数声明
qu* creatqueue();
void setnull(qu*);
void enqueue(qu*, datatype);
datatype *dequeue(qu*);
void print(qu*);

//主函数
void main()
{
    qu *sq= creatqueue();

    datatype x, *p;
    int key;

    setnull(sq);
    do
    {
        printf("1.Enter Queue   2.Delete Queue   3.clc display   4.print queue   -1.Quit:");
        scanf_s("%d", &key);
        switch (key)
        {
        case 1:  printf("Enter the Data:"); scanf_s("%d", &x);
            enqueue(sq, x);  break;
        case 2:  p = dequeue(sq);
            if (p != NULL) printf("%d\n", *p);
            break;
        case 3:system("cls"); break;
        case 4:print(sq); break;
        case -1: exit(0);
        }
    } while (1);
}

//建立队
qu* creatqueue()
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}
//置空队
void setnull(qu *sq)
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

//入队
void enqueue(qu*sq, datatype x)
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}


//出队
datatype *dequeue(qu*sq)
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}

//打印队列
void print(qu*sq)
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}



（五） 程序测试

5.1 入队列



5.2 出队列



5.3 打印队列


  前面已经用到了打印队列，所以格格不再赘述，大家由5.2&5.3可知打印队列是成功的。


(六) 源程序及封装软件下载


  下载地址



  格格是一枚智能专业的本科在校生，很愿意和各位大佬交流。如果大家有愿意交朋友的，可以加格格的QQ：446019725，声明是CSDN即可。

收起

展开全文

c语言数据结构算法

循环队列操作之一：循环队列的表示和实现（C语言版本）

千次阅读 2017-06-12 13:23:02

循环队列是对队列的一种改进，它比队列适用的范围更广，例如Linux内核当中的环形缓冲区就是基于循环队列来设计的。本文主要任务是通过C语言来实现一个循环队列的数据结构，以及对循环队列的基本操作。 1、循

队列（Queue）是一种操作受限的线性表，队列（Queue）只能在表的一端进行插入操作，在另一端进行删除操作。其中，允许插入的一端叫着队尾（tail），允许删除的一端叫做队头（front）。循环队列是对队列的一种改进，它比队列适用的范围更广，例如Linux内核当中的环形缓冲区就是基于循环队列来设计的。本文主要任务是通过C语言来实现一个循环队列的数据结构，以及对循环队列的基本操作。


1、循环队列数据结构的实现
在进行循环队列基本操作实现之前，先要实现一个数据结构来表示循环队列，这个结构的定义如下：

/* 定义循环队列的缓冲区的大小 */
#define	MAX_ITEMS		256

/* 定义循环队列的数据结构体 */
typedef enum {FALSE, TRUE} boolean;
typedef struct
{
	int base[MAX_ITEMS];	// 循环队列的缓冲区
	int front;		// 循环队列的头指针
	int rear;		// 循环队列的尾指针
} Queue;
 用这个Queue的结构体来表示循环队列，在这个结构体当中有三个成员变量：base用来表示这个循环队列的数据缓冲区，用它来存储插入到队列中的数据；front和rear是循环队列操作数据缓冲区的指针，通过它们不仅可以操作数据而且也可以来判断队列是否为满或者为空。


2、循环队列的创建和销毁
通过malloc来动态创建一个循环队列，通过free来释放前面动态分配的空间。具体的创建函数实现如下：

/* 创建一个循环队列
 *		返回值 : 返回创建的循环队列的结构体指针
 */
Queue *queue_create(void)
{
	Queue *q = malloc(sizeof(Queue));	// 分配一个队列空间
	if(NULL == q)	// 分配失败
	{
		return NULL;
	}
	else	// 分配成功
	{
		q->front = 0;
		q->rear = 0;
		return q;
	}
}
 具体的销毁函数实现如下：


/*	销毁一个循环队列
 *		q : 表示要销毁的循环队列
 */
void queue_destroy(Queue *q)
{
	if(NULL != q)
	{
		free(q);	// 执行销毁操作
	}
}



3、判断循环队列是否为空、是否为满
3.1 判断循环队列为空，如果front=rear则循环队列为空，具体实现如下

/*	判断循环队列是否为空
 *		q : 表示要判断的循环队列
 *		返回值: TRUE为空，FALSE为非空
 */
boolean queue_empty(Queue *q)
{
	if(q->front == q->rear) return TRUE;
	else return FALSE;
}
 3.2 判断循环队列为满，如果(rear + 1)%maxsize = front 则循环队列为满，具体实现如下：
/*	判断循环队列是否为满
 *		q : 表示要判断的循环队列
 *		返回值: TRUE表示满，FALSE表示非满
 */
boolean queue_full(Queue *q)
{
	if((q->rear + 1)%MAX_ITEMS == q->front) return TRUE;
	else return FALSE;
}

4、向循环队列中插入、取出元素

向循环队列中插入元素，先将元素插入到循环队列的尾部，然后将循环队列尾部的指针加一，具体实现如下：

/*	向队列尾部插入一个元素
 *		q : 要插入的循环队列
 *		item : 要掺入的元素
 *		返回值: TRUE成功，FALSE失败
 */
boolean queue_rear_insert(Queue *q, int item)
{
	if(queue_full(q)) return FALSE;
	else	// 如果循环队列未满
	{
		// 先将元素插入到循环队列的尾部，然后循环队列尾部的rear指针加一
		q->base[q->rear] = item;
		q->rear = (q->rear + 1)%MAX_ITEMS;
		return TRUE;
	}
}
 从循环队列中取出元素，先将循环队列头部的元素取出，然后将头部指针加一，具体的实现如下：


/*	将循环队列头部元素删除
 *		q : 要操作的堆栈
 *		返回值: 成功返回要删除的元素值，为0表示删除失败
 */
int queue_front_delete(Queue *q)
{
	int temp_item;
	
	if(queue_empty(q)) return 0;
	else	// 如果堆栈不为空
	{
		// 先将循环队列头部的元素取出，然后将头部指针加一
		temp_item = q->base[q->front];
		q->front = (q->front + 1)%MAX_ITEMS;
		return temp_item;
	}
}

5、循环队列的其他操作

获取循环队列头部元素，具体实现如下：

/*	获取循环队列头部元素
 *		q : 要操作的循环队列
 *		返回值 : 成功返回元素值，失败则返回0
 */
int queue_get_front(Queue *q)
{
	if(queue_empty(q)) return 0;
	else	// 如果不为空，返回堆栈的值
	{
		return q->base[q->front];
	}
}
 将整个循环队列所有元素按照先进先出顺序给打印出来：


/*	打印循环队列的元素
 *		q : 要打印的循环队列
 */
void queue_items_print(Queue *q)
{
	int front = q->front;
	int rear = q->rear;
	
	printf("Queue : ");
	while(!(front == rear))		// 判断是否读取完循环队列中所有元素
	{
		printf("%d ", q->base[front]);
		front = (front + 1)%MAX_ITEMS;
	}
	printf("\n");
}



6、测试
在main函数中编写测试程序，来测试前面实现的循环队列的基本操作：包括创建、销毁循环队列，向循环队列中插入元素，从循环队列中取出元素等，具体的测试代码实现如下：

/* 程序的入口 */
int main(int argc, char *argv[])
{
	Queue *q;
	int a[10];
	int i;

	/* 通过控制台输入10个整形元素 */
	printf("Input 10 numbers :\n");
	for(i = 0; i < 10; i++)
	{
		scanf("%d", &a[i]);
	}

	/* 创建一个循环队列 */
	q = queue_create();
	if(NULL == q)
	{
		printf("queue_create error!\n");
		return -1;
	}

	/* 把这个数组中的元素插入到队列当中 */
	for(i = 0; i < 10; i++)
	{
		queue_rear_insert(q, a[i]);
	}

	printf("*******************************************************\n");

	/* 把循环队列中所有元素都打印出来 */
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 向队列中尾部再插入两个元素 */
	queue_rear_insert(q, 200);
	queue_rear_insert(q, 300);
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 从队列头部删除三个元素 */
	queue_front_delete(q);
	queue_front_delete(q);
	queue_front_delete(q);
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 销毁一个循环队列 */
	queue_destroy(q);
	
	return 0;
}
 编译并运行结果如下所示：



附录：所实现的完整的程序代码如下所示

#include <stdio.h>
#include <stdlib.h>

/* 定义循环队列的缓冲区的大小 */
#define	MAX_ITEMS		256

/* 定义循环队列的数据结构体 */
typedef enum {FALSE, TRUE} boolean;
typedef struct
{
	int base[MAX_ITEMS];	// 循环队列的缓冲区
	int front;				// 循环队列的头指针
	int rear;				// 循环队列的尾指针
} Queue;

/* 创建一个循环队列
 *		返回值 : 返回创建的循环队列的结构体指针
 */
Queue *queue_create(void)
{
	Queue *q = malloc(sizeof(Queue));	// 分配一个队列空间
	if(NULL == q)	// 分配失败
	{
		return NULL;
	}
	else	// 分配成功
	{
		q->front = 0;
		q->rear = 0;
		return q;
	}
}

/*	销毁一个循环队列
 *		q : 表示要销毁的循环队列
 */
void queue_destroy(Queue *q)
{
	if(NULL != q)
	{
		free(q);	// 执行销毁操作
	}
}

/* 初始化循环队列
 *		q : 要初始化的循环队列
 */
void queue_init(Queue *q)
{
	q->front = 0;
	q->rear = 0;
}

/*	判断循环队列是否为空
 *		q : 表示要判断的循环队列
 *		返回值: TRUE为空，FALSE为非空
 */
boolean queue_empty(Queue *q)
{
	if(q->front == q->rear) return TRUE;
	else return FALSE;
}

/*	判断循环队列是否为满
 *		q : 表示要判断的循环队列
 *		返回值: TRUE表示满，FALSE表示非满
 */
boolean queue_full(Queue *q)
{
	if((q->rear + 1)%MAX_ITEMS == q->front) return TRUE;
	else return FALSE;
}

/*	向队列尾部插入一个元素
 *		q : 要插入的循环队列
 *		item : 要掺入的元素
 *		返回值: TRUE成功，FALSE失败
 */
boolean queue_rear_insert(Queue *q, int item)
{
	if(queue_full(q)) return FALSE;
	else	// 如果循环队列未满
	{
		// 先将元素插入到循环队列的尾部，然后循环队列尾部的rear指针加一
		q->base[q->rear] = item;
		q->rear = (q->rear + 1)%MAX_ITEMS;
		return TRUE;
	}
}

/*	将循环队列头部元素删除
 *		q : 要操作的堆栈
 *		返回值: 成功返回要删除的元素值，为0表示删除失败
 */
int queue_front_delete(Queue *q)
{
	int temp_item;
	
	if(queue_empty(q)) return 0;
	else	// 如果堆栈不为空
	{
		// 先将循环队列头部的元素取出，然后将头部指针加一
		temp_item = q->base[q->front];
		q->front = (q->front + 1)%MAX_ITEMS;
		return temp_item;
	}
}

/*	获取循环队列头部元素
 *		q : 要操作的循环队列
 *		返回值 : 成功返回元素值，失败则返回0
 */
int queue_get_front(Queue *q)
{
	if(queue_empty(q)) return 0;
	else	// 如果不为空，返回堆栈的值
	{
		return q->base[q->front];
	}
}

/*	打印循环队列的元素
 *		q : 要打印的循环队列
 */
void queue_items_print(Queue *q)
{
	int front = q->front;
	int rear = q->rear;
	
	printf("Queue : ");
	while(!(front == rear))		// 判断是否读取完循环队列中所有元素
	{
		printf("%d ", q->base[front]);
		front = (front + 1)%MAX_ITEMS;
	}
	printf("\n");
}


/* 程序的入口 */
int main(int argc, char *argv[])
{
	Queue *q;
	int a[10];
	int i;

	/* 通过控制台输入10个整形元素 */
	printf("Input 10 numbers :\n");
	for(i = 0; i < 10; i++)
	{
		scanf("%d", &a[i]);
	}

	/* 创建一个循环队列 */
	q = queue_create();
	if(NULL == q)
	{
		printf("queue_create error!\n");
		return -1;
	}

	/* 把这个数组中的元素插入到队列当中 */
	for(i = 0; i < 10; i++)
	{
		queue_rear_insert(q, a[i]);
	}

	printf("*******************************************************\n");

	/* 把循环队列中所有元素都打印出来 */
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 向队列中尾部再插入两个元素 */
	queue_rear_insert(q, 200);
	queue_rear_insert(q, 300);
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 从队列头部删除三个元素 */
	queue_front_delete(q);
	queue_front_delete(q);
	queue_front_delete(q);
	queue_items_print(q);

	printf("*******************************************************\n");

	/* 销毁一个循环队列 */
	queue_destroy(q);
	
	return 0;
}

收起

展开全文

c语言数据结构 Queue

循环队列和链式结构队列

千次阅读 2017-02-27 13:22:04

一、循环队列的基础知识 1，循环队列有几个参数需要确定：有两个参数，front和rear 2，循环队列各个参数的含义（1）队列初始化时，front和rear值都为零；（2）当队列不为空时，front指向队列的第一...

一、循环队列的基础知识
1，循环队列有几个参数需要确定：
      有两个参数，front和rear
2，循环队列各个参数的含义


（1）队列初始化时，front和rear值都为零；

（2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；

（3）当队列为空时，front与rear的值相等，但不一定为零；

3.循环队列入队的伪算法

（1）把值存在rear所在的位置；

（2）rear=（rear+1）%maxsize ，其中maxsize代表数组的长度；



4.循环队列出队的伪算法



（1）先保存出队的值；

（2）front=（front+1）%maxsize ，其中maxsize代表数组的长度；



5.如何判断循环队列是否为空



if（front==rear）

队列空；

else

队列不空

6.如何判断循环队列是否为满






 这个问题比较复杂，假设数组的存数空间为7，此时已经存放1，a，5,7,22,90六个元素了，如果在往数组中添加一个元素，则rear=front；此时，队列满与队列空的判断条件front=rear相同，这样的话我们就不能判断队列到底是空还是满了；

解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；
参考代码：#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
typedef struct Queue {
	int * PBase;//指向数组第一个元素的指针
	int front;//队列头部元素下标
	int rear;//队列尾部元素下标
}QUEUE;
/**
*初始化队列，实现队列的数组长度为6。
**/
void initQueue(QUEUE * pQ)
{
	pQ->PBase = malloc(sizeof(int) * 6);
	pQ->front = 0;
	pQ->rear = 0;
}
/**
判断队列是否已满
*/
bool isFull(QUEUE * pQ)
{
	if ((pQ->rear + 1) % 6 == pQ->front)
	{
		printf("队列已满，无法插入");
		return true;
	}

	return false;
}

/**
判断队列是否为空
*/

bool isEmpty(QUEUE * pQ)
{
	if (pQ->front == pQ->rear)
	{
		printf("队列为空");
		return true;
	}
	return false;
}
/**
入队
*/
bool insert(QUEUE * pQ, int val)
{
	if (isFull(pQ))
		return false;
	pQ->PBase[pQ->rear] = val;
	pQ->rear = (pQ->rear + 1) % 6;
	return true;
}

/**
遍历队列
*/

void traverse(QUEUE * pQ)
{
	int i = pQ->front;
	while (i != pQ->rear)
	{
		printf("%d  ", pQ->PBase[i]);
		i++;
	}
	printf("\n");
}

/**
出队
*/

bool  out_queue(QUEUE * pQ)
{
	if (isEmpty(pQ))
		return false;
	pQ->front = (pQ->front + 1) % 6;

}

int main()
{

	QUEUE Q;
	initQueue(&Q);
	insert(&Q, 1);
	insert(&Q, 2);
	insert(&Q, 3);
	insert(&Q, 4);
	insert(&Q, 5);
	insert(&Q, 6);
	traverse(&Q);
	out_queue(&Q);
	traverse(&Q);
	return 0;
}



二、链式队列
#include<stdio.h>  
#include<stdlib.h>  
#include<malloc.h>  
typedef int Item;
typedef struct node *PNode;
#define num 5  
typedef struct node
{
	Item data;
	PNode next;
}Node;

typedef struct queue *PQueue;

typedef struct queue
{
	PNode front;
	PNode rear;
	Item size;
}Queue;

/***创建空队列***/
PQueue Creat_Queue();

/***判断队列是否为空***/
int Is_Empty(PQueue);

PQueue CreateQueue(PQueue); //创建队列    


							/***数据项入队，在队尾入队***/
PQueue Add_Queue(PQueue, Item);

/***计算队列大小***/
int Size_Queue(PQueue);

/***数据项出队，在队首出队***/
Item Delete_Queue(PQueue);

/***清空队列***/
void Clear_Queue(PQueue);

/***遍历队列***/
void Traverse_Queue(PQueue);

/***创建空队列***/
PQueue Creat_Queue()
{
	PQueue P = (PQueue)malloc(sizeof(Queue));
	P->rear = P->front = (PNode)malloc(sizeof(Node));
	if (NULL == P || NULL == P->front)
	{
		printf("The queue is failed.\n");
		exit(1);
	}
	//P->front=P->rear;  
	P->front->next = NULL;
	P->size = 0;
	return P;
}

/***判断队列是否为空***/
int Is_Empty(PQueue P)
{
	if (P->front == P->rear)
		return 1;
	else
		return 0;
}

PQueue CreateQueue(PQueue P) //创建队列    
{
	P = Creat_Queue();
	printf("Enter the data:");
	int k;
	while ((scanf_s("%d", &k)) == 1)
	{
		Add_Queue(P, k);
		printf("Enter the next data:");
	}
	return P;
}

/***数据项入队,在队尾入队***/
PQueue Add_Queue(PQueue P, Item data)
{
	PNode temp = (PNode)malloc(sizeof(Node));
	if (NULL == temp)
	{
		printf("The temp is failed.\n");
		exit(1);
	}
	temp->data = data;
	temp->next = NULL;
	if (Is_Empty(P))
		P->front->next = temp;
	else
		P->rear->next = temp;
	P->rear = temp;
	P->size++;
	printf("Add the data of %d to queue is success: %d\n ", data, data);
	return P;
}

/***计算队列大小***/
int Size_Queue(PQueue P)
{
	return P->size;
}

/***数据项出队，在队首出队***/
Item Delete_Queue(PQueue P)
{
	Item data;
	if (Is_Empty(P))
		return NULL;
	PNode temp = P->front->next;
	data = temp->data;
	P->front->next = temp->next;
	if (0 == P->size)
		P->rear = P->front;
	P->size--;
	free(temp);
	return data;
}

/***清空队列***/
void Clear_Queue(PQueue P)
{
	PNode temp = P->front->next;
	while (temp)
	{
		PNode tp = temp;
		temp = temp->next;
		free(tp);
	}
	temp = P->front;
	P->front = P->rear = NULL;
	free(temp);
}

/***遍历队列***/
void Traverse_Queue(PQueue P)
{
	if (Is_Empty(P))
		printf("there is no data in the queue!\n");
	else
	{
		PNode pCurrent = P->front->next;
		printf("Now datas int the queue are:\n");
		while (pCurrent)
		{
			printf("%d ", pCurrent->data);
			pCurrent = pCurrent->next;
		}
		printf("\n");
	}
	return;
}

int main()
{

	/***创建空队列***/
	PQueue PQ;
	int size = 0;
	int data;
	PQ = Creat_Queue();
	printf("The queue is created.\n");

	/***判断队列是否为空***/
	if (Is_Empty(PQ))
		printf("The queue is empty.\n");

	PQ = CreateQueue(PQ); //创建队列  
						  /***遍历队列***/
	Traverse_Queue(PQ);

	/***数据项入队，在队尾入队***/
	PQ = Add_Queue(PQ, num);
	/***遍历队列***/
	Traverse_Queue(PQ);

	/***计算队列大小***/
	size = Size_Queue(PQ);
	printf("The size of queue are: %d\n", size);

	/***数据项出队，在队首出队***/
	data = Delete_Queue(PQ);
	printf("The deleted data is: %d\n", data);
	/***遍历队列***/
	Traverse_Queue(PQ);

	/***清空队列***/
	Clear_Queue(PQ);
	if (Is_Empty(PQ))
		printf("The queue is empty.\n");
	/***遍历队列***/
	Traverse_Queue(PQ);

	return 0;
}

收起

展开全文

链式队列数据结构

循环队列 作为消息队列
2016-06-12 20:21:43
为了避免消息队列频繁的申请和释放内存，采用循环队列作为消息队列。 queue.h: #ifndef INC_QUEUE_H_ #define INC_QUEUE_H_ #include #include using namespace std; #define MAX_QUEUE_SIZE 500000 #...
收起
消息队列 c++
C++循环队列与FFmpeg队列
千次阅读 2018-01-29 17:30:41
如果不使用循环队列，那么队列中删除队头剩下的空间将不会被使用。也就导致数组队列使用的不便性。所以，如果用数组实现队列，最好的方法就是循环队列。这样可以循环利用有限而固定的数组空间。考虑细节总结如何...
收起
JavaScript - 实现循环队列
2019-11-29 01:17:22
实现循环队列：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用...
收起
JavaScript leetcode 算法
C++数据结构：普通队列与循环队列
2020-06-14 22:32:24
普通队列与循环队列，普通队列可以看做是一列数据，环形队列可以看做是一个圆，当普通队列的数据索引可以循环设置时，普通队列就成了循环队列。这两种都可以用数组来实现。 循环队列的C++实现下面说明用数组...
收起
循环队列及C语言实现<一>
千次阅读 2016-09-21 22:34:11
循环队列是为了充分利用内存，进行数据操作的一种基本算法。具体实现方式可划分为：链式队列和静态队列，这里所谓的静态是指在一片连续的内存区域进行数据操作。本文只讲述静态队列，也是最简单的实现方式，静态队列...
收起
c语言算法队列数据结构
【数据结构-队列】循环队列
2015-05-08 21:21:25
关于循环队列循环队列就是像一个圈一样，可以一直不停的入队和出队，例如：队列已经满了，如果执行一次出队操作，队列头部就空出来了，这时候就可以把元素继续插入空出来的那里，头指针向后移第二个元素就变成的队列...
收起
循环队列(Circular Queue)
千次阅读 2016-05-28 18:09:41
循环队列(Circular Queue) 1. 循环队列的概念 1.1 循环队列的定义为了能够充分地使用数组中的...1.2 循环队列中各元素的逻辑及存储关系 循环队列的首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前
收起
数据结构队列一维数组
循环与循环双端队列
千次阅读 2020-01-20 23:12:12
循环队列 是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里...
收起
数据结构——14 循环队列
2016-08-18 17:17:22
循环队列
收起
LeetCode 622——设计循环队列
千次阅读 2018-10-15 15:40:28
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用...
收起
循环队列的实现
2014-07-16 01:31:09
循环队列的实现：
收起
队列及其简介以及：使用int[] 设计一个循环队列 【leetcode 622. 设计循环队列】【622. Design Circular ...
千次阅读 2019-05-18 21:15:50
在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队...
收起
leetcode 数据结构队列 Java
LeetCode 设计循环队列
2019-04-16 08:52:58
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用...
收起
循环队列及循环队列实现数值转换
2012-10-12 20:41:26
delete [] item; } void ClearXU_DL() //清空队列 { front=rear=0; } int Getlength() //获得长度 { if(rear==front) return ERROR; return ((rear-front)+maxlength)%...
收起
output null

循环队列

循环队列

文章目录

1，循环队列

2，C语言实现循环队列

3，OOP实现循环队列

循环队列–C语言实现–数据结构

循环队列–C语言实现–数据结构

目录

（一） 要求

（二） 循环队列

（三） 循环队列的算法设计

3.1 建立循环队列

3.2 置空队列

3.3 入队

3.4 出队

3.5 打印队

（四） 程序

4.1 程序的结构

4.2 程序源码

（五） 程序测试

5.1 入队列

5.2 出队列

5.3 打印队列

(六) 源程序及封装软件下载

下载地址

格格是一枚智能专业的本科在校生，很愿意和各位大佬交流。如果大家有愿意交朋友的，可以加格格的QQ：446019725，声明是CSDN即可。

循环队列操作之一：循环队列的表示和实现（C语言版本）

循环队列和链式结构队列

一、循环队列的基础知识

二、链式队列

循环队列 作为消息队列

C++循环队列与FFmpeg队列

JavaScript - 实现循环队列

C++数据结构：普通队列与循环队列

循环队列及C语言实现<一>

【数据结构-队列】循环队列

循环队列(Circular Queue)

循环与循环双端队列

数据结构——14 循环队列

LeetCode 622——设计循环队列

循环队列的实现

队列及其简介以及 ： 使用int[] 设计一个循环队列 【leetcode 622. 设计循环队列】【622. Design Circular ...

LeetCode 设计循环队列

循环队列及循环队列实现数值转换

循环队列中的delete

（一）要求

（二）循环队列

（三）循环队列的算法设计

（四）程序

（五）程序测试

循环队列作为消息队列

队列及其简介以及：使用int[] 设计一个循环队列【leetcode 622. 设计循环队列】【622. Design Circular ...