精华内容
下载资源
问答
  • 数据结构-队列之循环队列

    千次阅读 2018-10-22 10:44:06
    将顺序队列臆造为个环状的空间,即把存储队列元素的表从逻辑上看成个环,称为循环队列。 当队首指针q.front=MaxSize-1后,再前进个位置就自动归0,可以通过除法取余运算(%)来实现。 初始时:q.front = q....

    将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。
    当队首指针q.front=MaxSize-1后,再前进一个位置就自动归0,可以通过除法取余运算(%)来实现。

    初始时:q.front = q.rear=0
    队首指针+1:q.front = (q.front + 1) % MaxSize;
    队尾指针+1:q.rear = (q.rear + 1) % MaxSize;
    队列长度:(q.rear+MaxSize-q.front)%MaxSize
    

    循环队列的入队和出队示意图(摘抄):

    那么,循环队列空和队满的条件是什么呢?显然,队空和队满时都存在q.front=q.rear,所以为了区分队空还是对满有三种处理方式:
    1.牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的做法,约定“队头指针在队尾指针的下一位置作为队满的标志”,如图3-7(d2).

    队满条件:(q.rear+1)%MaxSize == q.front.
    队空条件仍为:q.front==q.rear.
    队中元素个数:(q.rear-q.front+MaxSize)%MaxSize

    2.类型中增设表示元素个数的数据成员,这样,则队空的条件为q.size==0;队满的条件为q.size==MaxSize,这两种情况都有q.front=q.rear

    (个人感觉这种做法的弊端就是需要多引用一个成员,优点就是操作瞬间变得简单了很多有木有)

    以下为代码的简单示例:

    //队列之循环队列
    #include "stdafx.h"
    
    #define ElementType int
    #define MaxSize 10
    typedef struct {
    	ElementType data[MaxSize];
    	int front, rear;//队头指针和队尾指针
    	int size;//数据成员数量
    }SeqQueue;
    
    /*
    初始化空队列
    */
    void InitQueue(SeqQueue &q) {
    	q.front = q.rear = 0;
    	q.size = 0;
    }
    /*
    判断队列是否为空
    */
    bool QueueEmpty(SeqQueue q) {
    	if (q.size == 0) {
    		return true;
    	}
    	return false;
    }
    /*
    入队操作
    1.判断队列是否已满
    2.队尾指针+1,因为是循环队列,所以通过除以MaxSize取模的方式处理,当队尾指针=MaxSize-1后,再前进一个位置自动归0
    */
    bool EnQueue(SeqQueue &q,ElementType e) {
    	//判断队列是否已满
    	if (q.size == MaxSize) {
    		return false;
    	}
    	q.rear = (q.rear + 1) % MaxSize;
    	q.data[q.rear] = e;
    	q.size++;
    	return true;
    }
    /*
    出队操作
    1.判断队列是否为空
    2.队首指针+1,因为是循环队列,所以通过除以MaxSize取模的方式处理,当队首指针=MaxSize-1后,再前进一个位置自动归0
    */
    ElementType DeQueue(SeqQueue &q) {
    	//判断队列是否为空
    	if (q.size == 0) {
    		return NULL;
    	}
    	ElementType e = q.data[q.front];
    	q.front = (q.front + 1) % MaxSize;
    	q.size--;
    	return e;
    }

     

    展开全文
  • 数据结构——循环队列PTA习题

    千次阅读 2020-12-17 23:39:58
    文章目录单选题题解函数题6-1 另类循环队列 (20分)输入样例:输出样例:代码6-2 双端队列 (25分)输入样例:输出样例:代码编程题7-1 堆栈模拟队列 (25分)输入格式:输出格式:输入样例:输出样例:代码模拟队列直接用...

    单选题

    题号题目答案
    1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
    2在用数组表示的循环队列中,front值一定小于等于rear值。
    3为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是? 队列
    4若已知一队列用单向链表表示,该单向链表的当前状态(含3个对象)是:1->2->3,其中x->y表示x的下一节点是y。此时,如果将对象4入队,然后队列头的对象出队,则单向链表的状态是: 2->3->4
    5某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到的出队序列是: d b c a e
    6若用大小为6的数组来实现循环队列,且当前front和rear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,front和rear的值分别为多少? 2和0
    7如果循环队列用大小为m的数组表示,且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围,那么这样的循环队列可以容纳的元素个数最多为: m
    8在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。 r->next=s; r=s;
    9循环顺序队列中是否可以插入下一个元素() 与队头指针和队尾指针的值有关
    10现有队列 Q 与栈 S,初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }(1在队头),S 为空。若允许下列3种操作:(1)出队并输出出队元素;(2)出队并将出队元素入栈;(3)出栈并输出出栈元素,则不能得到的输出序列是: 3, 4, 5, 6, 1, 2

    题解

    1. 初始化创建空队列时,令front=rear=0,每当插入新的队列尾元素时,rear增1,每当删除一个队列首元素时,front增1。因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置。
      front :0+2=2,
      rear 4+2=6——>0.

    函数题

    6-1 另类循环队列 (20分)

    如果用一个循环数组表示队列,并且只设队列头指针Front,不设尾指针Rear,而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。

    函数接口定义:

    bool AddQ( Queue Q, ElementType X );
    ElementType DeleteQ( Queue Q );
    

    其中Queue结构定义如下:

    typedef int Position;
    typedef struct QNode *PtrToQNode;
    struct QNode {
        ElementType *Data;  /* 存储元素的数组   */
        Position Front;     /* 队列的头指针     */
        int Count;          /* 队列中元素个数   */
        int MaxSize;        /* 队列最大容量     */
    };
    typedef PtrToQNode Queue; 
    

    注意:如果队列已满,AddQ函数必须输出“Queue Full”并且返回false;如果队列是空的,则DeleteQ函数必须输出“Queue Empty”,并且返回ERROR。

    输入样例:

    4
    Del
    Add 5
    Add 4
    Add 3
    Del
    Del
    Add 2
    Add 1
    Add 0
    Add 10
    End
    

    输出样例:

    Queue Empty
    5 is out
    4 is out
    Queue Full
    3 2 1 0 
    

    代码

    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR -1
    typedef int ElementType;
    typedef enum { addq, delq, end } Operation;
    typedef enum { false, true } bool;
    typedef int Position;
    typedef struct QNode *PtrToQNode;
    struct QNode {
        ElementType *Data;  /* 存储元素的数组   */
        Position Front;     /* 队列的头、尾指针 */
        int Count;          /* 队列中元素个数   */
        int MaxSize;        /* 队列最大容量     */
    };
    typedef PtrToQNode Queue; 
    
    Queue CreateQueue( int MaxSize )
    {
        Queue Q = (Queue)malloc(sizeof(struct QNode));
        Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
        Q->Front = 0;
        Q->Count = 0;
        Q->MaxSize = MaxSize;
        return Q;
    }
    
    bool AddQ( Queue Q, ElementType X );
    ElementType DeleteQ( Queue Q );
    
    Operation GetOp();  /* 裁判实现,细节不表 */
    
    int main()
    {
        ElementType X;
        Queue Q;
        int N, done = 0;
    
        scanf("%d", &N);
        Q = CreateQueue(N);
        while ( !done ) {
            switch( GetOp() ) {
            case addq: 
                scanf("%d", &X);
                AddQ(Q, X);
                break;
            case delq:
                X = DeleteQ(Q);
                if ( X!=ERROR ) printf("%d is out\n", X);
                break;
            case end:
                while (Q->Count) printf("%d ", DeleteQ(Q));
                done = 1;
                break;
            }
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    bool AddQ(Queue Q, ElementType X)
    {
    	if (Q->MaxSize==Q->Count)
    	{
    		printf("Queue Full\n");
    		return ERROR;
    	}
    	++Q->Count;
    	Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X;
    	return true;
    
    }
    ElementType DeleteQ(Queue Q)
    {
    	if (Q->Count==0)
    	{
    		printf("Queue Empty\n");
    		return ERROR;
    	}
    	--Q->Count;
    	Q->Front = (Q->Front + 1) % Q->MaxSize;
    	return Q->Data[Q->Front];
    
    }
    

    6-2 双端队列 (25分)

    双端队列(deque,即double-ended queue的缩写)是一种具有队列和栈性质的数据结构,即可以(也只能)在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列,请编写例程实现下列操作:

    Push(X,D):将元素X插入到双端队列D的头;
    Pop(D):删除双端队列D的头元素,并返回;
    Inject(X,D):将元素X插入到双端队列D的尾部;
    Eject(D):删除双端队列D的尾部元素,并返回。

    函数接口定义:

    bool Push( ElementType X, Deque D );
    ElementType Pop( Deque D );
    bool Inject( ElementType X, Deque D );
    ElementType Eject( Deque D );
    

    其中Deque结构定义如下:

    typedef int Position;
    typedef struct QNode *PtrToQNode;
    struct QNode {
        ElementType *Data;      /* 存储元素的数组   */
        Position Front, Rear;   /* 队列的头、尾指针 */
        int MaxSize;            /* 队列最大容量     */
    };
    typedef PtrToQNode Deque; 
    

    注意:Push和Inject应该在正常执行完操作后返回true,或者在出现非正常情况时返回false。当Front和Rear相等时队列为空,Pop和Eject必须返回由裁判程序定义的ERROR。

    输入样例:

    3
    Pop
    Inject 1
    Pop
    Eject
    Push 2
    Push 3
    Eject
    Inject 4
    Inject 5
    Inject 6
    Push 7
    Pop
    End
    

    输出样例:

    Deque is Empty!
    1 is out
    Deque is Empty!
    2 is out
    Deque is Full!
    Deque is Full!
    3 is out
    Inside Deque: 4 5
    

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR -1
    typedef int ElementType;
    typedef enum { push, pop, inject, eject, end } Operation;
    typedef enum { false, true } bool;
    typedef int Position;
    typedef struct QNode *PtrToQNode;
    struct QNode {
        ElementType *Data;      /* 存储元素的数组   */
        Position Front, Rear;   /* 队列的头、尾指针 */
        int MaxSize;            /* 队列最大容量     */
    };
    typedef PtrToQNode Deque; 
    
    Deque CreateDeque( int MaxSize )
    {   /* 注意:为区分空队列和满队列,需要多开辟一个空间 */
        Deque D = (Deque)malloc(sizeof(struct QNode));
        MaxSize++;
        D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
        D->Front = D->Rear = 0;
        D->MaxSize = MaxSize;
        return D;
    }
    
    bool Push( ElementType X, Deque D );
    ElementType Pop( Deque D );
    bool Inject( ElementType X, Deque D );
    ElementType Eject( Deque D );
    
    Operation GetOp();          /* 裁判实现,细节不表 */
    void PrintDeque( Deque D ); /* 裁判实现,细节不表 */
    
    int main()
    {
        ElementType X;
        Deque D;
        int N, done = 0;
    
        scanf("%d", &N);
        D = CreateDeque(N);
        while (!done) {
            switch(GetOp()) {
            case push: 
                scanf("%d", &X);
                if (!Push(X, D)) printf("Deque is Full!\n");
                break;
            case pop:
                X = Pop(D);
                if ( X==ERROR ) printf("Deque is Empty!\n");
                else printf("%d is out\n", X);
                break;
            case inject: 
                scanf("%d", &X);
                if (!Inject(X, D)) printf("Deque is Full!\n");
                break;
            case eject:
                X = Eject(D);
                if ( X==ERROR ) printf("Deque is Empty!\n");
                else printf("%d is out\n", X);
                break;
            case end:
                PrintDeque(D);
                done = 1;
                break;
            }
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    // 头插
    bool Push(ElementType X, Deque D)
    {
    	// 算尾部位置,如果满了返回false
    	if ((D->Rear + 1) % (D->MaxSize) == D->Front)
    		return false;
    	// 减完了才能用公式
    	D->Front--;
    	D->Front = (D->MaxSize + D->Front) % (D->MaxSize);
    	D->Data[D->Front] = X;
    	return true;
    }
    
    // 头删
    ElementType Pop(Deque D)
    {
    	if (D->Front == D->Rear)
    		return ERROR;
    	ElementType d = D->Data[D->Front];
    	D->Front++;
    	D->Front = D->Front % (D->MaxSize);
    	return d;
    }
    
    // 尾插
    bool Inject(ElementType X, Deque D)
    {
        // 算尾部位置,如果满了返回false
    	if ((D->Rear + 1) % (D->MaxSize) == D->Front)
    		return false;
    	D->Data[D->Rear] = X;
    	D->Rear = (D->Rear + 1) % D->MaxSize;
    	return true;
    }
    
    // 尾删
    ElementType Eject(Deque D)
    {
    	if (D->Front == D->Rear)
    		return ERROR;
    	if (!D->Rear)
    		D->Rear = D->MaxSize;
    	D->Rear--;
    	ElementType d = D->Data[D->Rear];
    	return d;
    }
    
    

    编程题

    7-1 堆栈模拟队列 (25分)

    设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。

    所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数:

    • int IsFull(Stack S):判断堆栈S是否已满,返回1或0;
    • int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0;
    • void Push(Stack S, ElementType item ):将元素item压入堆栈S;
    • ElementType Pop(Stack S ):删除并返回S的栈顶元素。

    实现队列的操作,即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。

    输入格式:

    输入首先给出两个正整数N1和N2,表示堆栈S1和S2的最大容量。随后给出一系列的队列操作:A item表示将item入列(这里假设item为整型数字);D表示出队操作;T表示输入结束。

    输出格式:

    对输入中的每个D操作,输出相应出队的数字,或者错误信息ERROR:Empty。如果入队操作无法执行,也需要输出ERROR:Full。每个输出占1行。

    输入样例:

    3 2
    A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T
    

    输出样例:

    ERROR:Full
    1
    ERROR:Full
    2
    3
    4
    7
    8
    ERROR:Empty
    

    代码

    模拟队列

    #include<stdio.h>
    #include<iostream>
    #include<stack>
    #include<string>
    
    using namespace std;
    stack<int>s1, s2;   //定义两个栈
    int n1, n2;         //两个栈的容量
    
    int main()
    {
    	char c;
    	int m, p, q;
    	cin >> n1 >> n2;
    	if (n1 > n2) 
    		swap(n1, n2);  // 保证更大的容量的S2作为输出栈
    	getchar();
    	while (1) 
    	{     
    		// 无限循环输入
    		cin >> c;
    		if (c == 'T') 
    			break;     // 输入字符为T时结束
    		if (c == 'A') 
    		{
    			cin >> m;
    			if (s1.size() == n1 && s2.size() != 0)   // 只有当s1为满,s2不为空时才是满的情况
    				printf("ERROR:Full\n");
    			else if (s1.size() == n1 && s2.size() == 0) 
    			{   
    				// 当s1为满,s2为空时,先将s1里面所有的元素转移到s2,再将新加入的元素放置s1
    				q = n1;
    				while (q--) 
    				{
    					p = s1.top();
    					s1.pop();
    					s2.push(p);
    				}
    				s1.push(m);
    			}
    			else if (s1.size() != n1)  // 若s1不满,可直接将新入的元素放置s1里面
    				s1.push(m);;
    		}
    		if (c == 'D') 
    		{   
    			//输入字符为D时要出队
    			if (s1.size() == 0 && s2.size() == 0)    //只有当s1,s2均为空时才为队空的情况
    				printf("ERROR:Empty\n");
    			else if (s1.size() != 0 && s2.size() == 0)
    			{  
    				//若s2为空,s1不空,则先把s1里面所有元素转移至s2,再输出s2的栈顶元素
    				q = s1.size();
    				while (q--) {
    					p = s1.top();
    					s1.pop();
    					s2.push(p);
    				}
    				cout << s2.top() << endl;
    				s2.pop();
    			}
    			else if (s2.size() != 0) 
    			{ 
    				//如果s2不为空,可直接输出s2栈顶元素
    				cout << s2.top() << endl;
    				s2.pop();
    			}
    		}
    	}
    	return 0;
    }
    
    
    

    直接用queue

    #include<bits/stdc++.h> 
    using namespace std;
    queue<int> q; 
      
    int main()
    {  
        int m,n,i,a;  
        char c;  
        cin>>m>>n;  
        n+=m;	
        for(i=0;;i++)
    	{  
            cin>>c;  
            if(c=='T')  
                return 0;
            if(c=='A')
    		{  
                cin>>a;  
                if(q.size()==n)
    			{
                    cout<<"ERROR:Full"<<endl;  
                }  
                else
    			{  
                    q.push(a);  
                }  
            }  
            else if(c=='D')
    		{  
                if(q.size()==0)
    			{  
                    cout<<"ERROR:Empty"<<endl;  
                }  
                else
    			{  
                    cout<<q.front()<<endl;  
                    q.pop();   
                }  
            }  
        }  
        return 0;  
    }
    
    展开全文
  • 数据结构笔记3.3 顺序队列是用顺序表实现的(即依托于数组),这里实现的是循环队列... 为了能够充分利空间,所以用循环队列,即在逻辑上把数组的队结构看成个环。具体实现:实现的方式还是十分巧妙地,运用两个指

    数据结构笔记3.3
    顺序队列是用顺序表实现的(即依托于数组),这里实现的是循环队列,其实也可以不用循环,但是那样的话,空间的利用效率就太低了,这就是”假溢出”问题,因为在数组的前端可能还有空闲的位置(因为队列中的数据是在动态变化的,可能出队也可能入对)。
    为了能够充分利空间,所以用循环队列,即在逻辑上把数组的队结构看成一个环。具体实现:实现的方式还是十分巧妙地,运用两个指针和钟运算(就是取模或是取余运算)。
    队头指针进1:front = (front + 1) % maxSize;
    队尾指针进1 : rear = (rear + 1) % maxSize;
    上面两个式子就是钟运算在队列数据操作时候的实现原理。
    另外,在判断队列NULL与队列FULL的时候会遇到混淆的问题,NULL的时候,在即rear == front ,但是由于是循环表,当表FULL的时候,两者也是相等的,一种区分方式就是当rear检测到其下一个就是front的时候作为队列满的依据,这样就相当于队列满的时候也会有一个节点是空闲的。
    好了,在编写这个类的过程中,需要强调的就这几个地方,下面贴出代码:
    虚基类代码(此代码段放入queue.h当中,并在模板类代码中包含)

    template<class T>
    class Queue {
    public:
        Queue(){}                               //构造函数
        ~Queue(){}                             //析构函数
        virtual bool EnQueue(const T & x) = 0;  //新元素x进入队列
        virtual bool DelQueue(T & x) = 0;       //队头元素出队列
        virtual bool getFront(T & x) = 0;       //读取队头元素的值
        virtual bool IsEmpty()const = 0;        //判断队列是否为NULL
        virtual bool IsFull() const = 0;        //判断队列是否已满
        virtual int getSize() const = 0;            //求队列元素的个数
    };
    模板class代码:
    
    #include <iostream>
    #include <cassert>
    #include <cmath>
    #include "queue.h"
    using namespace std;
    //顺序队列模板类定义(循环队列)
    template<class T>
    class SeqQueue : public Queue<T> {
    public:
        SeqQueue(int sz = 10);              //构造函数
        ~SeqQueue();                       //析构函数
        //若队列不满则将x进入队列,否则溢出处理
        bool EnQueue(const T & x);
        //若队列不空则删除队头元素x,并返回true,否则返回false
        bool DelQueue(T & x);
        //若队列不空则函数返回队头元素并返回true,否则返回false
        bool getFront(T & x);
        //置空操作,队头指针与队尾指针置0
        void makeEmpty();
        //判断队列是否为空,是则返回true否则返回false
        bool IsEmpty() const;
        //判断队列是否已满,是返回true否则返回false
        bool IsFull() const;
        //求队列元素的个数
        int getSize() const;
        //输出队列元素,运算符重载函数调用
        void output(ostream & out);
    protected:
        int rear, front;                    //队尾与队头指针
        T *elements;                        //存放队列元素的数组
        int maxSize;                        //队列最大可容纳的元素个数
    };
    //函数定义
    template<class T>
    SeqQueue<T>::SeqQueue(int sz) {
        //建立一个最大就有maxSzie个元素的空队列
        maxSize = sz;
        elements = new T[sz];               //开辟内存
        assert(elements != NULL);           //内存分配不成功的中断处理
        rear = front = 0;                   //初始化队头与队尾指
    }
    
    template<class T>
    SeqQueue<T>::~SeqQueue() {
        //析构函数,释放程序中相应的资源
        delete[] elements;
    }
    
    template<class T>
    bool SeqQueue<T>::EnQueue(const T & x) {
        //若队列不满则将x进入队列,否则溢出处理
        if (IsFull()) {
            //如果队列已经满,则返回false
            return false;
        }
        elements[rear] = x;
        rear = (rear + 1) % maxSize;    //通过钟运算实现元素的循环填充
        return true;
    }
    
    template<class T>
    bool SeqQueue<T>::DelQueue(T & x) {
        //若队列不空则删除队头元素x,并返回true,否则返回false
        if (IsEmpty()) {
            return false;
        }
        x = elements[front];
        front = (front + 1) % maxSize;
        return true;
    }
    
    template<class T>
    bool SeqQueue<T>::getFront(T & x)  {
        //若队列不空则函数返回队头元素并返回true,否则返回false
        if (IsEmpty()) {
            return false;
        }
        x = elements[front];
        return true;
    }
    
    template<class T>
    bool SeqQueue<T>::IsEmpty() const {
        if (rear == front) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    bool SeqQueue<T>::IsFull() const {
        if (fmod((rear + 1), maxSize) == front) {
            //如果rear的下一个节点与front相同则定义为队列已满
            //从而区分队列为NULL,即rear==front的情况
            return true;
            //注意这个时候队列中会有一个NULL的节点
        }
        else {
            return false;
        }
    }
    
    template<class T>
    void SeqQueue<T>::makeEmpty() {
        //置NULL操作
        rear = front = 0;
    }
    
    template<class T>
    int SeqQueue<T>::getSize() const {
        //求队列元素的个数
        return (rear - front + maxSize) % maxSize;
    }
    
    template<class T>
    void SeqQueue<T>::output(ostream & out) {
        for (int i = front; i != rear; i = (i + 1) % maxSize) {
            out << elements[i] << ' ';
        }
        cout << endl;
    }
    
    template<class T>
    ostream & operator << (ostream & out, SeqQueue<T> & SQ) {
        //重载插入运算符
        SQ.output(out);
        return out;
    }

    Main测试代码:

    int main()
    {
        SeqQueue<int> squeue;               //定义循环队列对象
        squeue.EnQueue(1);                  //进队与出队测试
        squeue.EnQueue(2);
        squeue.EnQueue(3);
        squeue.EnQueue(4);
        squeue.EnQueue(5);
        cout << squeue;
        int outQueVal_1, outQueVal_2;
        squeue.DelQueue(outQueVal_1);
        squeue.DelQueue(outQueVal_2);
        cout << squeue;
    
        int quFrontVal = 0;
        squeue.getFront(quFrontVal);        //提取队头数据测试
        cout << quFrontVal << endl;
    
        squeue.makeEmpty();                 //设置NULL与测试NULL测试
        if (squeue.IsEmpty()) {
            cout << "队列为NULL" << endl;
        }
        else {
            cout << "队列非空" << endl;
        }
    
        squeue.EnQueue(2);                  //取队列大小测试
        squeue.EnQueue(3);
        squeue.EnQueue(4);
        cout << squeue.getSize() << endl;
    
        system("pause");
        return 0;
    }

    运行结果:
    这里写图片描述

    展开全文
  • C++数据结构——队列

    万次阅读 多人点赞 2018-06-26 22:20:30
    C++数据结构——队列参考博客:http://www.cnblogs.com/QG-whz/p/5171123.htmlhttp://www.169it.com/article/2718050585107790752.html1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:(1)队列中...

                                                      C++数据结构——队列

     

    参考博客:

     

    1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

    (1)队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构;

    (2)在队尾添加元素,在队头删除元素。

    2、队列的相关概念:

    (1)队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头;

    (2)入队:队列的插入操作;

    (3)出队:队列的删除操作。

    3、队列的操作:

    (1)入队: 通常命名为push()

    (2)出队: 通常命名为pop()

    (3)求队列中元素个数

    (4)判断队列是否为空

    (5)获取队首元素

    4、队列的分类:

    (1)基于数组的循环队列(循环队列)

    (2)基于链表的队列(链队列)

    5、实例分析

           C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。

           那么我们如何判断队列是空队列还是已满呢?

          a、栈空: 队首标志=队尾标志时,表示栈空。

          b、栈满 : 队尾+1 = 队首时,表示栈满。

           使用标准库的队列时, 应包含相关头文件,在栈中应包含头文件: #include< queue> 。定义:queue< int > q;

    q.empty()               如果队列为空返回true,否则返回false
    q.size()                返回队列中元素的个数
    q.pop()                 删除队列首元素但不返回其值
    q.front()               返回队首元素的值,但不删除该元素
    q.push()                在队尾压入新元素
    q.back()                返回队列尾元素的值,但不删除该元素
    

    (1)基于数组的循环队列(循环队列)

           以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作。具体的示例图参考:http://www.cnblogs.com/QG-whz/p/5171123.html

           循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。参考博客:【c++版数据结构】之循环队列的实现,判断循环队列是“空”还是“ 满”,有两种处理方法:

    • A. 设置状态标志位以区别空还是满
    • B. 少用一个元素,约定“队头front在队尾rear的下一个位置(指的是环的下一个位置)”作为“满”的标志

            C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度;如果用户无法预估所用队列的最大长度,则宜采用链队列。

           定义front为队列头元素的位置,rear为队列尾元素的位置,MAXSIZE为循环队列的最大长度。注意以下几点,循环队列迎刃而解:

    • A.  求元素的个数:(rear - front + MAXSIZE) % MAXSIZE
    • B.  front/rear指向逻辑的下一个空间  front =(front+1)%MAXSIZE,rear = (rear+1)%MAXSIZE
    • C.  判空:front == rear
    • D.  判满:(rear+1+MAXSZIE) == front

     

    例子1、简单的队列操作

    #include <queue>
    #include <iostream>
    using namespace std;
    
    int main(){
    	queue<int> q;
    	for (int i = 0; i < 10; i++){
    		q.push(i);
    	}
    	if (!q.empty()){
    		cout << "队列q非空!" << endl;
    		cout << "q中有" << q.size() << "个元素" << endl;
    	}
    	cout << "队头元素为:" << q.front() << endl;
    	cout << "队尾元素为:" << q.back() << endl;
    	for (int j = 0; j < 10; j++){
    		int tmp = q.front();
    		cout << tmp << " ";
    		q.pop();
    	}
    	cout << endl;
    	if (!q.empty()){
    		cout << "队列非空!" << endl;
    	}
    	system("pause");
    	return 0;
    }
    运行结果:
     
     
    例子2、循环队列的C++实现
    #include <iostream>
    #include <queue>
    #include <string>
    using namespace std;
    
    template <typename T>
    class LoopQueue
    {
    public:
    	LoopQueue(int c = 10);
    	~LoopQueue();
    	bool isEmpty();        //队列的判空
    	int size();            //队列的大小
    	bool push(T t);        //入队列
    	bool pop();            //出队列
    	T front();            //队首元素
    
    private:
    	int capacity;
    	int begin;
    	int end;
    	T*  queue;
    };
    
    
    template<typename T>
    LoopQueue<T>::LoopQueue(int c = 10)
    	:capacity(c), begin(0), end(0), queue(nullptr)
    {
    	queue = new T[capacity];
    };
    
    template<typename T>
    LoopQueue<T>::~LoopQueue()
    {
    	delete[]queue;
    }
    
    template <typename T>
    bool LoopQueue<T>::isEmpty()                   //判断循环队列是否为空
    {
    	if (begin == end)
    		return true;
    	return false;
    };
    
    template<typename T>
    int LoopQueue<T>::size()
    {
    	return (end - begin + capacity) % capacity; //计算循环队列的长度
    };
    
    template<typename T>
    bool LoopQueue<T>::push(T t)
    {
    	if (end + 1 % capacity == begin)            //判断队列是否已满
    	{
    		return false;
    	}
    	queue[end] = t;
    	end = (end + 1) % capacity;
    	return true;
    };
    
    template <typename T>
    bool LoopQueue<T>::pop()                        //判断队列是否为空
    {
    	if (end == begin) 
    	{
    		return false;
    	}
    	begin = (begin + 1) % capacity;
    	return true;
    };
    
    template <typename T>
    T LoopQueue<T>::front()
    {
    	if (end == begin)
    	{
    		return false;
    	}
    	return queue[begin];
    };
    
    int main()
    {
    	LoopQueue<string> queue(6);
    	queue.push("one");
    	queue.push("two");
    	queue.push("three");
    	queue.push("four");
    	queue.push("five");
    	cout << "队列长度" << queue.size() << endl;
    	while (!queue.isEmpty())
    	{
    		cout << queue.front() << endl;
    		queue.pop();
    	}
    	getchar();
    	//system("pause");
    	return 0;
    }

    运行结果:

     

    (2)基于链表的队列(链队列)

           链队列是基于链表实现的队列,它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首,哪头做队尾显然我们应该以链表头部为队首,链表尾部为队尾。存储一个指向队尾的指针,方便从链表尾插入元素;使用带头节点的链表,方便从链表头删除元素

    代码参考:链式队列的C++实现

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    struct QNode    //定义队列结点的数据结构
    {
    	QNode *next; //指针域,指向下一个结点
    	double data;    //数据域,存储队列信息
    };
    
    struct LinkQueue    //定义队列的数据结构
    {
    	QNode *front;      //队首指针,指向QNode类型的指针
    	QNode *rear;       //队尾指针
    };
    
    void InitQueue(LinkQueue &Q)     //构造一个空的队列
    {
    	QNode *q;
    	q = new QNode;    //申请一个结点的空间
    	q->next = NULL;   //当作头结点
    	//队首与队尾指针都指向这个结点,指针域为NULL
    	Q.front = q;
    	Q.rear = q;
    }
    
    int IsEmpty(LinkQueue &Q)    //判断队列是否为空
    {
    	if (Q.rear == Q.front)
    		return 0;
    	else
    		return 1;
    }
    
    void EnQueue(LinkQueue &Q, double e)     //从队列尾部插入元素
    {
    	QNode *p;    //新创建一个结点
    	p = new QNode;
    	p->next = NULL;
    	p->data = e;  //输入数据信息
    	//将新结点插入队列尾部
    	Q.rear->next = p;
    	Q.rear = p;       //设置新的尾结点
    }
    
    void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点
    {
    	QNode *p;
    	p = Q.front->next;
    	e = p->data;    //保存要出队列的数据
    	Q.front->next = p->next;       //将下一个结点当作头结点后面链接的第一个结点
    	if (Q.rear == p)    //如果要删除的元素即为尾结点,则将头指针赋予尾指针,一同指向头结点,表示队列为空
    		Q.rear = Q.front;
    	delete p;
    }
    
    void DestoryQueue(LinkQueue &Q)       //销毁一个队列
    {
    	while (Q.front)
    	{
    		Q.rear = Q.front;    //从头节点开始,一个一个删除队列结点,释放空间
    		delete Q.front;
    		Q.front = Q.rear;
    	}
    }
    int main()
    {
    	LinkQueue *Q;  //定义一个队列Q
    	Q = new LinkQueue;
    	InitQueue(*Q);
    	cout << "开始往队列里输入数据,以-1作为结束符" << endl;
    	cout << "请输入一个数:" << endl;
    	double a, x;
    	cin >> a;
    	while (a != -1)
    	{
    		EnQueue(*Q, a);
    		cout << "请输入一个数:" << endl;
    		cin >> a;
    	}
    	//输出队列元素,队首->队尾
    	QNode *p;
    	p = Q->front->next;
    	if (p == NULL)     //如果为空表,直接退出
    	{
    		cout << "队列为空!" << endl;
    		return 0;
    	}
    	cout << "队列数据依次为:" << endl;
    	while (p != NULL)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    	//删除队列元素
    	while (!IsEmpty(*Q))
    	{
    		DeQueue(*Q, x);
    		cout << x << " ";
    	}
    	//释放内存空间
    	delete Q->front;
    	delete Q;
    	system("pause");
    	return 0;
    }

    运行结果:

    还可以参考代码:C++ 链队列和循环队列基本操作

     

    总结:

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

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

    展开全文
  • 存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。 循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾...
  • 队列 队列简称队, 也是一种操作受限的线性表, 只允许在表的一端进行插入, 而在表的另一端进行删除.其特点为”先进先出(FIFO)”,故又称为先进先出的线性表,简单队列如图所示: 循环队列 顺序队列有一个先天不足,...
  • 数据结构循环队列Java实现

    千次阅读 2016-10-26 12:12:58
    由于顺序队列中会产生假溢出的情形,例如个有6个存储空间的队列存满,并且出队2次之后, 我们无法在第七个存储空间继续入队,但实际上此队列在前方仍然有两个空余的存储空间。 解决这个问题,最好
  • 判断循环队列是“空”还是“满”,有以下两处理方法: 1》设置状态标志位以区别空还是满 2》少用个元素,约定“队头front在队尾rear的下个位置(指的是环的下个位置)”作为“满”的标志 注意以下几...
  • 队列的接口从上个专栏可以看出,栈和队列是非常相似的结构。它们之间的唯一区别是处理元素的顺序。栈使用后进先出(LIFO)的规律,其中对于栈来说push的最后个元素始终是第个pop的元素。而队列采用更接近于...
  • 严蔚敏吴伟民版《数据结构》课本源码第3章栈和队列第8节循环队列,用数组做存储结构。
  • 数据结构——队列

    千次阅读 2018-03-02 09:56:09
    队列一种重要的数据结构,它广泛应用于各种软件系统中,这两种数据结构与线性表有密切的联系。从逻辑上看,队列也属于线性结构,是一种特殊的线性表。其特殊性在队列的基本操作是线性表操作的子集,是限定仅在表尾...
  • 循环队列为充分利用向量空间,克服”假溢出”...循环队列的问题循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列
  • 数据结构习题之栈和队列

    千次阅读 2015-06-27 15:46:24
    第三章  栈和队列   .... 本章的目的是介绍栈和队列的...本章重点是掌握栈和队列在两存储结构上实现的基本运算,难点是循环队列中对边界条件的处理。 二. 考核目标和考核要求 要求达到识记层次的有:栈和队列的
  • 线性结构_循环队列

    千次阅读 2017-03-19 15:42:34
    1、静态队列为什么必须是循环队列:队列的结构是先进先出的,循环队列可对内存重复使用,减少对内存的浪费。 2、循环队列需要几个参数来确定:2个参数:front和rear 3、循环队列各个参数的含义 这两个
  • 数据结构与算法—队列详解

    千次阅读 2019-08-16 01:18:41
    栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入个狭小的山洞,山洞只有个出口,只能后进先出(在外面的先出去)。而队列就好比是个隧道,后面的人跟着...
  • 数据结构是计算机存储、组织数据的方式。一般来讲,数据结构按照数据的逻辑结构分为线性结构和非线性结构两。几乎所有的线性结构都是建立在两最基本的结构上的:内存中连续存储的数组结构以及内存中分散存储的...
  • 数据结构逻辑结构和存储结构

    千次阅读 多人点赞 2020-08-08 11:11:53
    逻辑结构:数据的逻辑结构是对数据之间关系的描述,与存储结构无关,同一种逻辑结构可以有多多种存储结构。 逻辑结构主要分为两大类:线性存储结构和非线性存储结构 线性存储结构是数据元素有序集合,数据结构之间...
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据...
  • C/C++泛型编程实现数据结构队列

    万次阅读 2018-09-17 08:39:46
    C/C++泛型编程实现数据结构队列 早在曾经篇博文中,我曾介绍过顺序存储和链式存储的区别和好处,博文传送门:https://blog.csdn.net/qq_27180763/article/details/82683029 本章将讲诉: 1. 队列逻辑结构...
  • 数据结构篇:循环队列的C语言实现及其基本操作 #简述 循环队列在有些嵌入式软件开发中使用频繁,同时队列是非常重要的数据结构。 #include<stdio.h> #include<stdlib.h> #define Maxsize 20 //队列达到...
  • 循环队列  为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。   条件处理  循环队列中,由于...
  • 数据结构-队列Queue

    万次阅读 2019-11-15 17:48:09
    一、什么是队列 队列也是一种线性结构,相比数组,队列对应的操作是数组的子集,只能从一端( 队尾)添加元素,也只能...队列一种先进先出的数据结构(先到先得 )First In First Out(FIFO)。 二、队列的实现 ...
  • 队列——顺序存储结构循环队列

    千次阅读 2013-05-31 11:27:16
    队列的顺序存储结构 ...为什么小甲鱼上节课说队列的实现上我们更愿意用链式...我们假设队列有n个元素,则顺序存储的队列需建立个大于n的存储单元,并把队列的所有元素存储在数组的前n个单元,数组下标为0的
  • 数据结构逻辑结构和物理结构

    千次阅读 多人点赞 2017-10-25 14:41:05
    数据结构:指的是数据之间的相互关系,包含三个内容:逻辑结构,存储结构和数据的运算 数据的逻辑结构指数据元素之间的逻辑关系,分两,线性结构和非线性结构。 常用的线性结构有:线性表,栈,队列,双队列,...
  • 数据结构篇之栈和队列

    千次阅读 2020-05-14 22:52:38
    数据结构篇之栈和队列一、前言二、栈1、栈的概念2、栈的实现——Stack类源码解读(JDK1.8)三、队列1、队列概念2、双端队列3、链队列4、循环队列四、总结 一、前言 栈和队列是两很重要的线性结构,从数据结构角度看...
  • 顺序循环队列

    千次阅读 2019-01-08 08:49:52
     队列一种运算受限的先进先出线性表,仅允许在队尾插入(入队),在队首删除(出队)。新元素入队后成为新的队尾元素,元素出队后其后继元素就成为队首元素。  队列的顺序存储结构使用一个数组和两个整型变量实现,...
  • 数据结构-队列(Queue)

    千次阅读 多人点赞 2021-01-22 10:45:03
    一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。其操作特性为先进后出(First In Last Out,FIFO),并且只允许在队尾进,...
  •  普通的队列一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高进先出 (largest-in,first-out)的...
  • 数据结构逻辑结构与存储结构

    千次阅读 2013-12-24 22:10:00
    栈只是一种抽象数据类型,是一种逻辑结构,栈逻辑结构对应的顺序存储结构为 顺序栈,对应的链式存储结构为链栈。循环队列是队列的顺序存储结构,链表是线性表的链式存储结构。 http://topic.csdn.net/t
  • 数据结构)——逻辑结构和存储结构(易错)

    千次阅读 多人点赞 2019-01-17 09:54:37
    解析:顺序表、哈希表和单链表表示几种数据结构,既描述逻辑结构,也描述存储结构和数据运算。而有序表是指关键字有序的线性表,可以链式存储也可以顺序存储,仅描述了元素之间的逻辑关系,属于逻辑结构。 2.循环...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,289
精华内容 32,115
关键字:

循环队列是一种逻辑数据结构

数据结构 订阅