循环队列 订阅
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。 展开全文
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
信息
特    点
大小固定
实现方式
单链表
有关术语
队列
中文名
循环队列
外文名
Circular Queue
领    域
数据结构
循环队列简介
循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。 [1]  循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件是front=rear,而队列判满的条件是front=(rear+1)%MaxSize。 [2] 
收起全文
精华内容
参与话题
问答
  • 循环队列

    万次阅读 多人点赞 2018-10-31 18:25:58
    循环队列出现的原因 :顺序队列出队后 的空间不能再次利用,造成资源浪费。所以出现循环队列 这个代码是用tag标记的循环队列 思路:(rear+1)%m==front 则队列满,(front+1)%m == rear则队列空。队列开始为空,设...

    循环队列出现的原因

    :顺序队列出队后 的空间不能再次利用,造成资源浪费。所以出现循环队列

    这个代码是用tag标记的循环队列

    思路:(rear+1)%m==front 则队列满,(front+1)%m == rear则队列空。队列开始为空,设tag=0。

    简单的说就是front 追 rear 如果追上就是空队列

    然后rear如果追上front 就是满队列

    当 tag == 1且 front == rear 时队满

    当tag == 0 且front == rear 时队空

    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    typedef char QElemType;
    #define MAXQSIZE		10
    typedef struct {
    	QElemType *elem;
    	int tag;
    	int front;
    	int rear;
    }CircleQueue;
    int InitCircle(CircleQueue &Q)
    {
        Q.elem = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
        Q.front = 0;
        Q.rear = 0;
        Q.tag = 0;
        return 1;
    }
    int ClearCircleQueue(CircleQueue &Q) //清空
    {
        Q.front = 0;
        Q.rear = 0;
        Q.tag = 0;
        return 0;
    }
    int DestoryCircleQueue(CircleQueue &Q)//销毁
    {
        free(Q.elem);
        Q.elem = NULL;
        return 1;
    }
    int CircleQueueLength(CircleQueue Q)//判断长度
    {
        return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }
    
    int EmptyCircle(CircleQueue Q) //判空
    {
        if(Q.rear == Q.front && Q.tag == 0)
    	 return 1;
        return 0;
    }
    int EnQueue(CircleQueue &Q, QElemType e) //入队
    {
    	if(Q.tag == 1)
    	return 0;
    	Q.elem[Q.rear] = e;
    	Q.rear = (Q.rear + 1) % MAXQSIZE;
    	if(Q.rear == Q.front)
    	Q.tag = 1;
    	return 1;
    }
    int DeQueue(CircleQueue &Q, QElemType &e)//出队
    {
    	if(Q.rear == Q.front && Q.tag == 0)
    	 return 0;
    	 e = Q.elem[Q.front];
    	 Q.front = (Q.front + 1) % MAXQSIZE;
    	 if(Q.front == Q.rear)
    	 Q.tag = 0;
    	 return 1;
    }
    
    int ShowCircleQueue(CircleQueue Q)//显示
    {
        if(Q.rear == Q.front && Q.tag == 0)
        {
            return 0;
        }
        while(1)
        {
            printf("%c ", Q.elem[Q.front]);
            Q.front = (Q.front + 1) % MAXQSIZE;
            if(Q.front == Q.rear)
                break ;
        }
        return 1;
    }
    
    void help()
    {
    
        cout << "1~~~~~初始化循环队列" <<endl;
        cout << "2~~~~~清空循环队列" << endl;
        cout << "3~~~~~销毁循环队列" << endl;
        cout << "4~~~~~循环队列长度" << endl;
        cout << "5~~~~~循环队列是否为空" << endl;
        cout << "6~~~~~入队" << endl;
        cout << "7~~~~~出队" << endl;
        cout << "8~~~~~显示队列元素" << endl;
        cout << "      输入非正数退出" << endl;
    }
    
    int main ()
    {
        CircleQueue Q;
        help();
        int operate_code;
        char e;
        while(1)
        {
        	cin>>operate_code;
        	if(operate_code == 1)
        	{
        		InitCircle(Q);
    		}
    		if(operate_code == 2)
    		{
    			ClearCircleQueue(Q);
    		}
    		if(operate_code == 3)
    		{
    			DestoryCircleQueue(Q);
    		}
    		if(operate_code == 4)
    		{
    			int len = CircleQueueLength(Q);
    			cout<<"队列的长度为 = " << len;
    		}
    		if(operate_code == 5)
    		{
    			if( EmptyCircle(Q) )
    			printf("队列为空\n");
    			else
    			printf("队列非空\n"); 
    		}
    		
    		if(operate_code == 6)
    		{
    			cout << "请输入你要入队的元素: " << endl;
    			cin >> e; 
    			if(EnQueue(Q, e))
    			{
    				cout << "入队成功" << endl;
    			}
    			else
    			{
    				cout << "入队失败" << endl;
    			} 
    		}
    		if(operate_code == 7)
    		{
    			if(	DeQueue(Q, e))
    			{
    				cout << "出队成功,队首元素为 = " << e << endl; 
    			}
    			else
    			cout << "队列为空,队内无元素 "<<endl;
    		
    		} 
    		if(operate_code == 8)
    		{
    			ShowCircleQueue( Q);
    		}
        	if(operate_code <= 0)
        	break;
    	}
    	return 0;
    }
    

     

    展开全文
  • 数据结构——循环队列——2016_12_28

    万次阅读 多人点赞 2016-12-28 18:21:32
    ——————简单实现了插入,删除,长度,退出等功能——————
    循环队列源代码(C语言版)


    /*******简单实现了插入,删除,长度,退出等功能********/

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    //定义队列结构
    typedef struct Queue{
        int * base;
    	int front;
    	int rear;
    }SQueue;
    //初始化100个数字的队列
    void InitQueue(SQueue * Q){
        Q->base=(int *)malloc(MAXSIZE*sizeof(int));
    	Q->front=Q->rear=0;
    }
    //返回队列长度
    void QueueLength(SQueue * Q){
         printf("此队列的长度为:%d\n",(Q->rear-Q->front+MAXSIZE)%MAXSIZE);
    }
    
    //插入节点
    void InsertQueue(SQueue * Q,int e){
       if((Q->rear+1)%MAXSIZE==Q->front)
    	   printf("队列已满!\n");
       else
       {
    	   Q->base[Q->rear]=e;
    	   Q->rear=(Q->rear+1)%MAXSIZE;   
       }
    
    }
    //删除节点
     DeleteQueue(SQueue * Q){
    	if(Q->rear==Q->front)
    	   printf("队列已空!\n");
       else{ 
    	   Q->front=(Q->front+1)%MAXSIZE;
    	   printf("删除完成!\n");
    }
    }
    //打印队列
    void PrintQueue(SQueue Q){
    	printf("________________________________________________________\n");
    	while(Q.front!=Q.rear){    //此处留了一个标志位,所以不用再打印最后一个数。
    	printf("%d ",Q.base[Q.front]);
    	Q.front=(Q.front+1)%MAXSIZE;
    	}
    	printf("\n————————————————————————————\n");
    }
    //主函数
    int main(){
    
    	SQueue M;int i,x,v;
    	InitQueue(&M);
    	for(i=1;i<=12;i++){
    	InsertQueue(&M,i);
    	}
    	printf("十二个数字的队列已经建立完成!\n");
    	PrintQueue(M);
    	printf("请输入序号进行操作:1.插入  2.删除  3.长度  4.退出\n");
        scanf("%d",&x);
    	while(x!=0){
    		switch(x){
    		case 1:printf("请输入要插入的值:");
    			   scanf("%d",&v);
    			   InsertQueue(&M,v);
    			   PrintQueue(M);
    			   break;
    		case 2:DeleteQueue(&M);
    			   PrintQueue(M);
    			   break;
    		case 3:printf("正在计算长度......\n");
    			   QueueLength(&M);
    			   break;
    		case 4:exit(0);
    		default:printf("输入有误,请重新输入!\n");
    		}
    	printf("请输入序号进行操作:1.插入  2.删除  3.长度  4.退出\n");
        scanf("%d",&x);
    	}
    	return 0;
    }



    程序截图:









                联系邮箱:xhsgg12302@outlook.com

                                                                                             2016_12_28

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 18,190
精华内容 7,276
关键字:

循环队列