精华内容
下载资源
问答
  • 从生活中,可以抽象出队列的概念队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表...

    生活中有很多队列的影子,比如打饭排队,买火车票排队问题等,可以说与时间相关的问题,一般都会涉及到队列问题;从生活中,可以抽象出队列的概念,队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。这里讲的是循环队列,首先我们必须明白下面几个问题

    一、循环队列的基础知识

    1.循环队列需要几个参数来确定

    循环队列需要2个参数,front和rear

    2.循环队列各个参数的含义

    (1)队列初始化时,front和rear值都为零;

    (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置;

    (3)当队列为空时,front与rear的值相等,但不一定为零;

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

    (1)把值存在rear所在的位置;

    (2)rear=(rear+1)%maxsize ,其中maxsize代表数组的长度;

    程序代码:

    [cpp] view plain copy
    1. bool Enqueue(PQUEUE Q, int val)  
    2. {  
    3.     if(FullQueue(Q))  
    4.         return false;  
    5.     else  
    6.     {  
    7.         Q->pBase[Q->rear]=val;  
    8.         Q->rear=(Q->rear+1)%Q->maxsize;  
    9.         return true;  
    10.     }  
    11. }  


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

    (1)先保存出队的值;

    (2)front=(front+1)%maxsize ,其中maxsize代表数组的长度;

    程序代码:

    [cpp] view plain copy
    1. bool Dequeue(PQUEUE Q, int *val)  
    2. {  
    3.     if(EmptyQueue(Q))  
    4.     {  
    5.         return false;  
    6.     }  
    7.     else  
    8.     {  
    9.         *val=Q->pBase[Q->front];  
    10.         Q->front=(Q->front+1)%Q->maxsize;  
    11.         return true;  
    12.     }  
    13. }  


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

    if(front==rear)

    队列空;

    else

      队列不空;

    [cpp] view plain copy
    1. bool EmptyQueue(PQUEUE Q)  
    2. {  
    3.     if(Q->front==Q->rear)    //判断是否为空  
    4.         return true;  
    5.     else  
    6.         return false;  
    7. }  


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


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

    解决这个问题有两个办法:一是增加一个参数,用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间,也就是数组的最后一个存数空间不用,当(rear+1)%maxsiz=front时,队列满;

    [cpp] view plain copy
    1. bool FullQueue(PQUEUE Q)  
    2. {  
    3.     if(Q->front==(Q->rear+1)%Q->maxsize)    //判断循环链表是否满,留一个预留空间不用  
    4.         return true;  
    5.     else  
    6.         return false;  
    7. }  


    附录:

    queue.h文件代码:

    [cpp] view plain copy
    1. #ifndef __QUEUE_H_  
    2. #define __QUEUE_H_  
    3. typedef struct queue   
    4. {  
    5.     int *pBase;  
    6.     int front;    //指向队列第一个元素  
    7.     int rear;    //指向队列最后一个元素的下一个元素  
    8.     int maxsize; //循环队列的最大存储空间  
    9. }QUEUE,*PQUEUE;  
    10.   
    11. void CreateQueue(PQUEUE Q,int maxsize);  
    12. void TraverseQueue(PQUEUE Q);  
    13. bool FullQueue(PQUEUE Q);  
    14. bool EmptyQueue(PQUEUE Q);  
    15. bool Enqueue(PQUEUE Q, int val);  
    16. bool Dequeue(PQUEUE Q, int *val);  
    17. #endif  


    queue.c文件代码:

    [cpp] view plain copy
    1. #include<stdio.h>  
    2. #include<stdlib.h>  
    3. #include"malloc.h"  
    4. #include"queue.h"  
    5. /*********************************************** 
    6. Function: Create a empty stack; 
    7. ************************************************/  
    8. void CreateQueue(PQUEUE Q,int maxsize)  
    9. {  
    10.     Q->pBase=(int *)malloc(sizeof(int)*maxsize);  
    11.     if(NULL==Q->pBase)  
    12.     {  
    13.         printf("Memory allocation failure");  
    14.         exit(-1);        //退出程序  
    15.     }  
    16.     Q->front=0;         //初始化参数  
    17.     Q->rear=0;  
    18.     Q->maxsize=maxsize;  
    19. }  
    20. /*********************************************** 
    21. Function: Print the stack element; 
    22. ************************************************/  
    23. void TraverseQueue(PQUEUE Q)  
    24. {  
    25.     int i=Q->front;  
    26.     printf("队中的元素是:\n");  
    27.     while(i%Q->maxsize!=Q->rear)  
    28.     {  
    29.         printf("%d ",Q->pBase[i]);  
    30.         i++;  
    31.     }  
    32.     printf("\n");  
    33. }  
    34. bool FullQueue(PQUEUE Q)  
    35. {  
    36.     if(Q->front==(Q->rear+1)%Q->maxsize)    //判断循环链表是否满,留一个预留空间不用  
    37.         return true;  
    38.     else  
    39.         return false;  
    40. }  
    41. bool EmptyQueue(PQUEUE Q)  
    42. {  
    43.     if(Q->front==Q->rear)    //判断是否为空  
    44.         return true;  
    45.     else  
    46.         return false;  
    47. }  
    48. bool Enqueue(PQUEUE Q, int val)  
    49. {  
    50.     if(FullQueue(Q))  
    51.         return false;  
    52.     else  
    53.     {  
    54.         Q->pBase[Q->rear]=val;  
    55.         Q->rear=(Q->rear+1)%Q->maxsize;  
    56.         return true;  
    57.     }  
    58. }  
    59.   
    60. bool Dequeue(PQUEUE Q, int *val)  
    61. {  
    62.     if(EmptyQueue(Q))  
    63.     {  
    64.         return false;  
    65.     }  
    66.     else  
    67.     {  
    68.         *val=Q->pBase[Q->front];  
    69.         Q->front=(Q->front+1)%Q->maxsize;  
    70.         return true;  
    71.     }  
    72. }  
    展开全文
  • 本文将对队列的概念及操作函数进行简要介绍,并说明顺序队列(利用数组)和链式队列(利用链表)的一些基本算法。 一、队列的相关概念 1.队列及其操作 (先进先出) 1.1 相关概念 (1)队列:只允许在表的一端删除...

    前言

    太久没更新了,早就说要写结果拖到现在。闲话说完,正式开始内容。
    队列——顾名思义,其实在线性表中也是一种极其重要的结构。
    与栈不同的是,栈对元素的插入和删除均在一端进行,而队列,从队头删除,队尾插入,正如日常生活中的排队一样,还是比较形象的。
    本文将对队列的概念及操作函数进行简要介绍,并说明顺序队列(利用数组)和链式队列(利用链表)的一些基本算法。

    一、队列的相关概念

    1.队列及其操作 (先进先出)

    1.1 相关概念

    (1)队列:只允许在表的一端删除元素,在另一端插入元素的线性表
    (2)空队列:不含元素的队列
    (3)队首:队列中只允许删除元素的一端,又称head,front
    (4)队尾:队列中只允许插入元素的一端,又称rear,tail
    (5)进队(入队):将新元素插入到队尾
    (6)出队:从队列删除一个元素,即删除队首元素
    注:进出队可类比为排队

    1.2 队列的基本操作
    (1)InitQueue(q):初始化,将q置为空队列
    (2)QueueEmpty(q):判断q是否为空队列
    (3)EnQueue(q,e):将e插入队列q的尾端
    (4)DeQueue(q,e):取走队列q的首元素,赋值给e
    (5)GetHead(q,e);读取队列首元素,赋值给e
    (6)QueueClear(q):置q为空队列

    二、链式队列的基本操作

    1.链式队列:运用链式结构进行存储的队列,一般用带表头结点的单链表表示

    为提高插入删除效率,在头指针中设置两个指针
    一般形式:
    (1)Q.front:队首指针,指向表头结点
    (2)Q.rear:队尾指针,指向队尾结点
    注:当队列为空时,(1)(2)均执行表头结点
    (3)Q.front->data:不放元素
    (4)Q.fornt->next:指向队首结点a1

    2.定义结点类型

    (1)存放元素的结点类型:数据域和指针域

    //定义结点类型
    typedef struct Qnode
    {
    	ElemType data;//其中数据域data为抽象元素类型
    	struct Qnode *next;//其中next为指针类型 
    }Qnode,*QueuePtr;//其中,Qnode为结点类型, QueuePtr:指向Qnode的指针类型
    

    (2)由头、尾指针组成的结点类型

    //由头、尾指针组成的结点类型
    typedef struct
    {
    	Qnode *front;//头指针
    	Qnode *rear;//尾指针 
    }LinkQueue;//链式队列类型 
    

    (3)生成空队列算法:初始化队列

    //生成空队列算法:初始化队列	
    #define LENG sizeof(Qnode)//求结点所占的单元数
    LinkQueue InitQueue()//生成仅带表头结点的空队列Q
    {
    	LinkQueue Q;//说明变量Q
    	Q.front = Q.rear = (QueuePtr)malloc(LENG);//生成表头结点
    	Q.front->next = NULL;//表头结点的next为空指针
    	return Q;//返回Q的值 
    } 
    

    (4)(非)空队列时插入新元素x

    //(非)空队列时插入新元素x	
    LinkQueue Enqueue(LinkQueue Q,ElemType e)
    {
    	Qnode *p;//说明变量p
    	p = (Qnode*)malloc(LENG);//生成新元素结点
    	p->data = e;//装入元素e
    	p->next = NULL;//为队尾结点
    	Q.rear->next = p;//插入新结点
    	Q.rear = p;//修改尾指针
    	return Q;//返回Q的新值 
    } 
    

    3.元素的删除(变化表头结点即可)

    注:若原队列只有一个结点,则还需考虑尾指针
    链式队列的出队算法

    //链式队列的出队算法	
    LinkQueue DelQueue(LinkQueue Q,ElemType *e)
    {
    	Qnode *p;//声明变量p
    	if (Q.front==Q.rear)//若原队列为空
    	{
    		printf ("Empty queue");//空队列
    		return Q; 
    	}
    	p = Q.front->next;//p指向要删除的队头结点
    	(*e) = p->data;//取出元素
    	Q.front->next = p->next;//删除队头结点
    	if (Q.rear==p)//若原队列只有1个结点
    	{
    		Q.rear = Q.front;//修改尾指针 
    	}
    	free(p);//释放被删除的空间
    	return Q;//返回出队后的Q 
    }
    

    三、顺序队列的基本操作

    1.顺序队列与“假溢出”

    假设用一维数组Q[0…5]表示顺序队列
    设f指向队头元素,r指向队尾元素后一空单元
    (1)初始化后:空队列r=f
    (2)元素ABC进队后:f指向A,r指向C后一单元(即Q[3])
    (3)ABC出队后:f后移至r,此时空队列f=r
    (4)DEF进队后,r后移至F后(Q[5])后
    (5)若此时G要进入,会判定为假溢出
    但此时Q[0],Q[1]等还是空的

    2.解决假溢出的方法一:移动元素

    (6)DEF移到前端后,占据Q[0],Q[1],Q[2],此时fr也移动
    (7)G进队之后,r指向Q[3]
    此方法缺点:比较费时,移动元素开销大

    3.方法二:将Q当循环表使用(循环队列)

    即在(4)时,r会重新指向Q[0]
    在(5)中,G要进队时便会放在Q[0],r再后移指向Q[1]
    (6)此时HI进队之后,则队列已满,f=r
    便产生了问题,f=r时,是空队列还是满队列(二义性)

    (1)二义性解决方案

    方案一 :增加一个标识变量
    方案二:预留最后一个单元不使用,即:进队前测试
    若r+1==f,表明还剩最后一个单元,认为此时是满队列
    即:若队列为Q[0…maxleng-1],共有maxleng-1个元素

    (2)循环队列的满队列条件
    当r+1f或(f0)&&(rmaxleng-1),即:(r+1)%maxlengf为满队列
    空队列条件仍为r==f

    4.顺序队列算法举例

    (1)定义队列的C类型

    //顺序队列算法举例:定义队列的C类型
    #define MAXLENG 100
    typedef struct
    {
    	ElemType elem[MAXLENG];
    	int front,rear;//分别指向队首结点和队尾结点后的下一个单元 
    }SeQueue;
    SeQueue Q;//定义结构变量Q表示队列 
    

    (2)进队算法En_Queue

    //假设用Q表示顺序队列,e为进队元素
    int En_Queue (SeQueue &Q,ElenType e)
    {
    	if ((Q.rear+1)%MAXLENG==Q.front)//若Q已满,退出
    		return ERROR;
    	Q.elem[Q.rear] = e;//装入新元素e
    	Q.rear++;//尾指针后移一个位置
    	Q.rear = Q.rear%MAXLENG;//为循环队列
    	return OK; 
    } 
    在这里插入代码片
    

    (3)出队算法De_Queue

    //出队算法De_Queue
    int De_Queue
    {
    	if (Q.front==Q.rear)//Q为空队列,退出
    		return ERROR;
    	e = Q.elem[Q.front];//取走队头元素,赋值给e
    	Q.front = (Q.front+1)%MAXLENG;//循环后移到一个位置
    	return OK; 
     } 
     
    

    总结

    总的来说,队列的判空和判满比栈要复杂的多,可能出现假溢出现象。又因其在队头删除,要通过移动元素解决问题,比较花时间。因此,链式队列就具有其优越性。对计算机的要求也比数组低,不要求有连续空间。当存放数据较多时,可以选用链式队列。
    ps:代码非原创。
    如有错误,欢迎指正。
    下一篇将介绍一些特殊矩阵的操作。

    展开全文
  • 队列 C语言(转)

    2015-01-05 11:23:24
    队列的操作方式与堆栈类似,唯一区别在于队列只允许新数据在后端进行添加。 队列的属性 以队列q为例。 q.head指向队头元素; q.tail指向下一个新元素将要插入位置。 在队列中,位置1紧邻在n后面...

    概念

    队列的操作

    队列是受限制的线性表,只允许在队尾(tail)插入、对头(head)删除。

    队列的操作方式与堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

    队列的属性

    以队列q为例。

    q.head指向队头元素;
    q.tail指向下一个新元素将要插入的位置。

    在队列中,位置1紧邻在n的后面形成一个环序。

    队列的状态

    当q.head = q.tail时,队列为空,
    初始时有q.head = q.tail = 1 ;
    当q.head = q.tail + 1时,队列是满的 。

    数组实现

    利用数组q.key[n]实现一个最多容纳n-1个元素的队列。

    # include <stdio.h>
    # define M 100
    typedef struct queue {
     int head;
     int tail;
     int key[M];
     int length;
    } queue;
    queue q;
    void enqueue(int x);
    int dequeue(void);
    int main(void)
    {
     q.head = q.tail = 1;
     q.length = 98;
     enqueue(1);
     enqueue(3);
     enqueue(5);
     enqueue(7);
     printf("%d\n", dequeue());
     printf("%d\n", dequeue());
     printf("%d\n", dequeue());
     printf("\t%d\n", q.head);
     printf("%d\n", dequeue());
    }
    void enqueue(int x)
    {
     q.key[q.tail] = x;
     if(q.tail == q.length) {
      q.tail = 1;
     } else {
      q.tail++;
     }
    }
    int dequeue(void)
    {
     int x;
     
     x = q.key[q.head];
     if(q.head == q.length) {
      q.head = 1;
     } else {
      q.head++;
     }
     return x;
    }

    全局变量实现

    全局变量也挺方便的,只是注意不要和局部变量重名而被取代了。

    # include <stdio.h>
    # define M 100
    typedef struct queue {
     int head;
     int tail;
     int key[M];
     int length;
    } queue;

    void enqueue(queue * qp, int x);
    int dequeue(queue * qp);
    int main(void)
    {
     queue q;
     q.head = q.tail = 1;
     q.length = 98;
     enqueue(&q, 1);
     enqueue(&q, 3);
     enqueue(&q, 5);
     enqueue(&q, 7);
     printf("%d\n", dequeue(&q));
     printf("%d\n", dequeue(&q));
     printf("%d\n", dequeue(&q));
     printf("%d\n", dequeue(&q));
    }
    void enqueue(queue * pq, int x)
    {
     pq -> key[pq -> tail] = x;
     if(pq -> tail == pq -> length) {
      pq -> tail = 1;
     } else {
      pq -> tail++;
     }
    }
    int dequeue(queue * pq)
    {
     int x;
     
     x = pq -> key[pq -> head];
     if(pq -> head == pq -> length) {
      pq -> head = 1;
     } else {
      pq -> head++;
     }
     return x;
    }

    整体实现



    #include<malloc.h>
    #include<stdio.h>


    #ifndef Queue_H
    #define Queue_H


    typedef int Item;
    typedef struct node * PNode;
    typedef struct node
    {
    Item data;
    PNode next;
    }Node;


    typedef struct
    {
    PNode front;
    PNode rear;
    int size;
    }Queue;


    /*构造一个空队列*/
    Queue *InitQueue();


    /*销毁一个队列*/
    void DestroyQueue(Queue *pqueue);


    /*清空一个队列*/
    void ClearQueue(Queue *pqueue);


    /*判断队列是否为空*/
    int IsEmpty(Queue *pqueue);


    /*返回队列大小*/
    int GetSize(Queue *pqueue);


    /*返回队头元素*/
    PNode GetFront(Queue *pqueue,Item *pitem);


    /*返回队尾元素*/
    PNode GetRear(Queue *pqueue,Item *pitem);


    /*将新元素入队*/
    PNode EnQueue(Queue *pqueue,Item item);


    /*队头元素出队*/
    PNode DeQueue(Queue *pqueue,Item *pitem);


    /*遍历队列并对各数据项调用visit函数*/
    void QueueTraverse(Queue *pqueue,void (*visit)());


    #endif






    /*构造一个空队列*/
    Queue *InitQueue()
    {
    Queue *pqueue = (Queue *)malloc(sizeof(Queue));
    if(pqueue!=NULL)
    {
    pqueue->front = NULL;
    pqueue->rear = NULL;
    pqueue->size = 0;
    }
    return pqueue;
    }


    /*销毁一个队列*/
    void DestroyQueue(Queue *pqueue)
    {
    if(IsEmpty(pqueue)!=1)
    ClearQueue(pqueue);
    free(pqueue);
    }


    /*清空一个队列*/
    void ClearQueue(Queue *pqueue)
    {
    while(IsEmpty(pqueue)!=1)
    {
    DeQueue(pqueue,NULL);
    }


    }


    /*判断队列是否为空*/
    int IsEmpty(Queue *pqueue)
    {
    if(pqueue->front==NULL&&pqueue->rear==NULL&&pqueue->size==0)
    return 1;
    else
    return 0;
    }


    /*返回队列大小*/
    int GetSize(Queue *pqueue)
    {
    return pqueue->size;
    }


    /*返回队头元素*/
    PNode GetFront(Queue *pqueue,Item *pitem)
    {
    if(IsEmpty(pqueue)!=1&&pitem!=NULL)
    {
    *pitem = pqueue->front->data;
    }
    return pqueue->front;
    }


    /*返回队尾元素*/


    PNode GetRear(Queue *pqueue,Item *pitem)
    {
    if(IsEmpty(pqueue)!=1&&pitem!=NULL)
    {
    *pitem = pqueue->rear->data;
    }
    return pqueue->rear;
    }


    /*将新元素入队*/
    PNode EnQueue(Queue *pqueue,Item item)
    {
    PNode pnode = (PNode)malloc(sizeof(Node));
    if(pnode != NULL)
    {
    pnode->data = item;
    pnode->next = NULL;

    if(IsEmpty(pqueue))
    {
    pqueue->front = pnode;
    }
    else
    {
    pqueue->rear->next = pnode;
    }
    pqueue->rear = pnode;
    pqueue->size++;
    }
    return pnode;
    }


    /*队头元素出队*/
    PNode DeQueue(Queue *pqueue,Item *pitem)
    {
    PNode pnode = pqueue->front;
    if(IsEmpty(pqueue)!=1&&pnode!=NULL)
    {
    if(pitem!=NULL)
    *pitem = pnode->data;
    pqueue->size--;
    pqueue->front = pnode->next;
    free(pnode);
    if(pqueue->size==0)
    pqueue->rear = NULL;
    }
    return pqueue->front;
    }


    /*遍历队列并对各数据项调用visit函数*/
    void QueueTraverse(Queue *pqueue,void (*visit)())
    {
    PNode pnode = pqueue->front;
    int i = pqueue->size;
    while(i--)
    {
    // visit(pnode->data);
    pnode = pnode->next;
    }

    }




    void print(Item i)
    {
    printf("该节点元素为%d\n",i);
    }




    void use_fun11(void)
    {
    Queue *pq = InitQueue();
    int i,item;
    printf("0-9依次入队并输出如下:\n");
    for(i=0;i<10;i++)
    {
    EnQueue(pq,i);
    GetRear(pq,&item);
    printf("%d ",item);
    }


    printf("\n从队头到队尾遍历并对每个元素执行print函数:\n");
    QueueTraverse(pq,print);


    printf("队列中元素依次出队列并输出如下:\n");
    for(i=0;i<10;i++)
    {
    DeQueue(pq,&item);
    printf("%d ",item);
    }
    ClearQueue(pq);
    if(IsEmpty(pq))
    printf("\n将队列置空成功\n");
    DestroyQueue(pq);
    printf("队列已被销毁\n");
    }



    展开全文
  • 栈和队列 C语言实现

    千次阅读 多人点赞 2013-11-28 13:09:04
    1、栈的概念 2、栈的顺序存储 示意图: 下面通过一个实例展示栈的顺序存储结构的操作实现,其中包含了6种操作: #include #include typedef int ElemType; //定义元素类型 struct StackSq //定义栈

    1、栈的概念

    栈又称堆栈,它是一种运算受限的线性表,其限制是仅允许在表的一端进行插入和删除运算。

    2、栈的顺序存储结构和操作实现

    栈的顺序存储结构示意图:


    下面通过一个实例展示栈的顺序存储结构的操作实现,其中包含了6种操作:

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElemType;  //定义元素类型
    struct StackSq         //定义栈结构类型
    {
        ElemType* stack;   //存栈元素的数组指针
        int top;           //存栈顶元素的下标位置
        int MaxSize;       //存stack数组长度
    };
    
    //栈满需要重新分配更大空间 的情况
    void againMalloc(struct StackSq* S)
    {
        ElemType *p = realloc(S->stack, 2*S->MaxSize*sizeof(ElemType));//此处重新分配的空间为原来的2倍
        if (!p)  //重新分配失败
        {
            printf("存储空间用完!\n");
            exit(1);
        }
        S->stack = p;             //使list指向新栈空间
        S->MaxSize = 2 * S->MaxSize;
        printf("存储空间已扩大为当前的2倍!\n");//输出提示已扩充空间
    }
    
    //1、初始化栈S为空
    void InitStack(struct StackSq* S, int ms)
    {
        if (ms < 0)
        {
            printf("ms的值非法!\n");
            exit(1);
        }
        S->MaxSize = ms;
        S->stack = malloc(ms*sizeof(ElemType));
        if (!S->stack)
        {
            printf("动态存储分配失败!\n");
            exit(1);
        }
        S->top = -1;   //值为-1,表示栈空
    }
    
    //2、新元素进栈,即把它插入到栈顶
    void Push(struct StackSq* S, ElemType x)
    {
        if (S->top == S->MaxSize - 1)
            againMalloc(S);
        S->top++;
        S->stack[S->top] = x;
    }
    
    //3、删除栈顶元素并返回值
    ElemType Pop(struct StackSq* S)
    {
        if (S->top == -1)
        {
            printf("栈空,无元素出栈!\n");
            exit(1);
        }
        S->top--;
        return S->stack[S->top + 1];
    }
    
    //4、读取栈顶元素的值(并不改变栈)
    ElemType Peek(struct StackSq* S)
    {
        if (S->top == -1)
        {
            printf("栈空,无任何元素!\n");
            exit(1);
        }
        return S->stack[S->top];
    }
    
    //5、判断S是否为空。若是空返回1,否则返回0
    int EmptyStack(struct StackSq* S)
    {
        if (S->top == -1)
            return 1;
        else
            return 0;
    }
    
    //6、清除栈S中的所有元素,释放动态存储空间
    void ClearStack(struct StackSq* S)
    {
        if (S->stack)
        {
            free(S->stack);   //释放存储空间
            S->stack = 0;
            S->top == -1;
            S->MaxSize = 0;
        }
    }
    
    //主函数
    void main()
    {void againMalloc(struct List *L)
    {
        ElemType *p = realloc(L->list, 2*L->MaxSize*sizeof(ElemType));//此处重新分配的空间为原来的2倍
        if (!p)  //重新分配失败
        {
            printf("存储空间用完!\n");
            exit(1);
        }
        L->list = p;             //使list指向新线性表空间
        L->MaxSize = 2 * L->MaxSize;
        printf("存储空间已扩大为当前的2倍!\n");//输出提示已扩充空间
    }
        struct StackSq s;
        int a[8] = {3, 8, 5, 17, 9, 30, 15, 22};
        int i;
        InitStack(&s, 5);
        for (i = 0; i < 8; i++)
            Push(&s, a[i]);
        printf("%d ", Pop(&s));
        printf("%d \n", Pop(&s));
        Push(&s, 68);
        printf("%d ", Peek(&s));
        printf("%d \n", Pop(&s));
        while (!EmptyStack(&s))
            printf("%d ", Pop(&s));
        printf("\n");
        ClearStack(&s);
    }
    

    运行结果:


    3、栈的链接存储结构和操作实现

    栈的链接存储结构与线性表的链接存储结构相同。

    栈的链接存储结构及操作过程示意图:


    下面通过一个实例展示栈的链接存储结构的操作,其中包括6种操作

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef int ElemType;  //定义元素类型
    struct sNode           //定义链栈结点类型
    {
        ElemType data;
        struct sNode* next;
    };
    
    //1、初始化链栈为空
    void InitStack(struct sNode** HS)
    {
        *HS = NULL;   //HS表示栈顶指针
    }
    
    //2、向链栈中插入一个元素
    void Push(struct sNode** HS, ElemType x)
    {
        struct sNode *newp;
        newp = malloc(sizeof(struct sNode));
        if (newp == NULL)
        {
            printf("内存动态空间用完,退出运行!\n");
            exit(1);
        }
        newp->data = x;
        newp->next = *HS;
        *HS = newp;
    }
    
    //3、从链栈中删除栈顶元素并返回它
    ElemType Pop(struct sNode** HS)
    {
        struct sNode* p;
        ElemType temp;
        if (*HS == NULL)
        {
            printf("栈空无法删除!\n");
            exit(1);
        }
        p = *HS;
        *HS = p->next;
        temp = p->data;
        free(p);
        return temp;
    }
    
    //4、读取栈顶元素
    ElemType Peek(struct sNode** HS)
    {
        if (*HS == NULL)
        {
            printf("栈空,无栈顶结点!\n");
            exit(1);
        }
        return (*HS)->data;
    }
    
    //5、检查链栈是否为空
    int EmptyStack(struct sNode** HS)
    {
        if (*HS == NULL)
            return 1;
        else
            return 0;
    }
    
    //6、清除链栈为空
    void ClearStack(struct sNode** HS)
    {
        struct sNode *cp, *np;
        cp = *HS;
        while (cp != NULL)
        {
            np = cp->next;
            free(cp);
            cp = np;
        }
        *HS = NULL;
    }
    
    //主函数
    void main()
    {
        struct sNode *a;
        int x = 0;
        int m[8] = {3, 8, 5, 17, 9, 30, 15, 22};
        printf("当前序列:3,8,5,17,9,30,15,22\n");
        InitStack(&a);
        while (x != 8)
        {
            Push(&a, m[x]);
            x++;
        }
        printf("逆序列为:");
        while (!EmptyStack(&a))
            printf("%d,", Pop(&a));
        printf("\n");
        ClearStack(&a);
    }
    

    运行结果:


    4、队列概念

    队列也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入(队尾),在表的另一端进行删除(队首)。

    5、队列的顺序存储结构和操作实现(循环列队)

    如上图,当队列处于图(d)的状态时不可再插入元素,不然就越界了,但实际队列空间并未占满,为了解决这个问题,就有了循环队列,如下图:

    图片展示的很详细,为了区分队空和队满,我们采取少用一个元素空间,约定以“对头指针在队尾指针的下一位置(指环状的下一位置)上”作为队列满状态的标志。

                                      空队列时:Q.front = Q.rear = 0;

                                       一般情况时:入队一个元素,尾指针后移一次,出队一个元素,头指针后移一次。

                                       队列满时:( Q.rear + 1 ) % MaxSize == Q.front (如图中的情况为:(5+1)% 6 == 0)

    注意,当情况如下时:


    插入a1元素时,Q.rear后移一个位置,但不是直接加1,比如上图 : 5+1=6,但实际位置应为0,所以必须写成:

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

    删除元素时的情况同理。

    注意:关于内存不足时扩大内存的情况,若Q.rear = Q.MaxSize - 1 时,即 Q.rear 为 5 时,直接扩大内存即可,但当Q.rear != Q.MaxSize - 1 时,如下图:(Q.rear,2)


    此时,原来位置为0、1位置的元素现在变成了位置为6、7的元素了,而且队尾指针由原来的2变成了8,所以内存扩大后应该进行操作(后面有详细讲解):

            for (i = 0; i < Q->rear; i++)
                Q->queue[i + Q->MaxSize] = Q->queue[i];
            Q->rear += Q->MaxSize;


    具体情况见下面的程序代码。

    下面通过一个实例展示队列顺序存储的操作,包含6种操作

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElemType;
    struct QueueSq
    {
        ElemType *queue;   //指向存储队列的数组空间
        int front, rear;   //队首指针、队尾指针
        int MaxSize;       //queue数组长度
    };
    
    //扩展存储空间函数
    void againMalloc(struct QueueSq* Q)
    {
        ElemType *p;
        p = realloc(Q->queue, 2*Q->MaxSize*sizeof(ElemType));
        if (!p)
        {
            printf("存储空间用完!\n");
            exit(1);
        }
        Q->queue = p;     //使queue指向新的队列空间
        if (Q->rear != Q->MaxSize - 1)
        {
            int i;
            for (i = 0; i < Q->rear; i++)                                
                Q->queue[i + Q->MaxSize] = Q->queue[i];   //原队列的尾部内容后移MaxSize个位置
            Q->rear += Q->MaxSize;                                    //队尾指针后移MaxSize个位置
        }
        Q->MaxSize = 2*Q->MaxSize;                                //队列空间修改为原来的2倍
        printf("存储空间已为当前2倍!\n");
    }
    //1、初始化队列
    void InitQueue(struct QueueSq* Q, int ms)
    {
        if (ms <= 0)
        {
            printf("ms值非法!\n");
            exit(1);
        }
        Q->MaxSize = ms;
        Q->queue = malloc(ms*sizeof(ElemType));
        if (!Q->queue)
        {
            printf("内存空间用完!\n");
            exit(1);
        }
        Q->front = Q->rear = 0;    //置队列为空
    }
    
    //2、向队列插入元素
    void EnQueue(struct QueueSq* Q, ElemType x)
    {
        if ((Q->rear + 1) % Q->MaxSize == Q->front)  //队空间满
            againMalloc(Q);
        Q->queue[Q->rear] = x;                       //插入值
        Q->rear = (Q->rear + 1) % Q->MaxSize;        //队尾指针后移一个位置
    }
    
    //3、从队列中删除元素并返回
    ElemType OutQueue(struct QueueSq* Q)
    {
        ElemType temp;
        if (Q->front == Q->rear)
        {
            printf("队列已空,无法删除!\n");
            exit(1);
        }
        temp = Q->queue[Q->front];                  //保存队首元素值
        Q->front = (Q->front + 1) % Q->MaxSize;     //使队首后移一个位置
        return temp;
    }
    
    //4、读取队首元素,不改变队列状态
    ElemType PeekQueue(struct QueueSq* Q)
    {
        if (Q->front == Q->rear)
        {
            printf("队列已空,无法读取!\n");
            exit(1);
        }
        return Q->queue[Q->front];
    }
    
    //5、检查一个队列是否为空,若是则返回1,否则返回0
    int EmptyQueue(struct QueueSq* Q)
    {
        if (Q->front == Q->rear)
            return 1;
        else
            return 0;
    }
    
    //6、清除一个队列为空,释放动态存储空间
    void ClearQueue(struct QueueSq* Q)
    {
        if (Q->queue != NULL)
        {
            free(Q->queue);
            Q->queue = 0;
            Q->front = Q->rear = 0;
            Q->MaxSize = 0;
        }
    }
    
    //主函数
    void main()
    {
        struct QueueSq q;
        int a[8] = {3,8,5,17,9,30,15,22};
        int i;
        InitQueue(&q, 5);
        for (i = 0; i < 8; i++)
            EnQueue(&q, a[i]);
        printf("%d ", OutQueue(&q));
        printf("%d \n", OutQueue(&q));
        EnQueue(&q, 68);
        printf("%d ", PeekQueue(&q));
        printf("%d \n", OutQueue(&q));
        while (!EmptyQueue(&q))
            printf("%d ", OutQueue(&q));
        printf("\n");
        ClearQueue(&q);
    }
    

    运行结果:


    为验证和详解上面提到的内存扩大问题,我们把上面的主函数换为如下:

    void main()
    {
        struct QueueSq q;
        struct QueueSq* p = &q;
        int a[5] = {3,8,5,17,9};
        int i;
        InitQueue(&q, 6);
        for (i = 0; i < 5; i++)
            EnQueue(&q, a[i]);
        printf("%d ", OutQueue(&q));
        printf("%d ", OutQueue(&q));
        printf("%d \n", OutQueue(&q));
        EnQueue(&q, 67);
        printf("插入了67!\n");
        EnQueue(&q, 68);
        printf("插入了68!\n");
        EnQueue(&q, 69);
        printf("插入了69!\n");
        EnQueue(&q, 100);
        printf("插入了100!\n");
        printf("%d ", PeekQueue(&q));          //显示队头元素
        printf("\n");
        for (i = 0; i < 12; i++)
            printf("%d ,", p->queue[i]);     //显示所有元素
        printf("\n");
        while (!EmptyQueue(&q))
            printf("%d ", OutQueue(&q));
        printf("\n");
        ClearQueue(&q);
    }

    运行结果:

    分析:先是依次入队 3,8,5,17,9 五个元素,然后出队3,8,5三个元素,再然后入队67,68,69三个元素,此时状态如下图的左图,

    注意:出队的元素虽然不在队里,但在内存里仍存在,如图中的暗绿色的元素。

    下面当要将100入队时,内存空间不够,扩大为原来的2倍,此时队中的尾端位置将发生变化如下右图,(暗绿色元素并不在队里)

    此时的队头位置元素仍为 17,一次输出下标从0到11位置的内存内容:如上面的运行结果所示,68,69,5仍存在,下标6,7,8三个位置为别是68,69,100,后面的空间无值。

    将队的所有元素出队,结果即为上图的运行结果中的:17,9,67,68,69,100。

    至此循环顺序队列的相关内容已经非常清晰了。


    6、队列的链接存储结构和操作实现

    链队的示意图如下:

    下面通过实例展示链队的6种操作

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElemType;
    struct sNode             //结点类型
    {
        ElemType data;       //值域
        struct sNode* next;  //链接指针域
    };
    struct QueueLk           //队列链接存储结构类型
    {
        struct sNode* front; //队首指针
        struct sNode* rear;  //队尾指针
    };
    
    //1、初始化链队
    void InitQueue(struct QueueLk* HQ)
    {
        HQ->front = HQ->rear = NULL;
    }
    
    //2、向链队中插入元素
    void EnQueue(struct QueueLk* HQ, ElemType x)
    {
        struct sNode* newp;
        newp = malloc(sizeof(struct sNode));
        if (newp == NULL)
        {
            printf("内存动态空间用完,退出运行!\n");
            exit(1);
        }
        newp->data = x;
        newp->next = NULL;
        if (HQ->front == NULL)  //若链队为空,则新节点既是队首结点又是队尾结点
            HQ->front = HQ->rear = newp;
        else       //若链队非空,则依次修改队尾结点的指针域和队尾指针,使之都指向新的队尾结点
            HQ->rear = HQ->rear->next = newp;
    }
    
    //3、从链队中删除元素并返回
    ElemType OutQueue(struct QueueLk* HQ)
    {
        struct sNode* p;
        ElemType temp;
        if (HQ->front == NULL)
        {
            printf("队列为空,无法删除!\n");
            exit(1);
        }
        temp = HQ->front->data;
        p = HQ->front;
        HQ->front = p->next; //使队首指针指向下一个结点
        if (HQ->front == NULL) //若删除后队空,则使队尾指针也变为空
            HQ->rear = NULL;
        free(p);
        return temp;
    }
    
    //4、读取队首元素,不改变队列状态
    ElemType PeekQueue(struct QueueLk* HQ)
    {
        if (HQ->front == NULL)
        {
            printf("队列已空,无法读取!\n");
            exit(1);
        }
        return HQ->front->data;
    }
    
    //5、检查一个链队是否为空,若是则返回1,否则返回0
    int EmptyQueue(struct QueueLk* HQ)
    {
        if (HQ->front == NULL)
            return 1;
        else
            return 0;
    }
    
    //6、清除链队为空,释放动态存储空间
    void ClearQueue(struct QueueLk* HQ)
    {
       struct sNode* p = HQ->front;
       while (p != NULL)  //依次删除队列中的每一个结点,循环结束后队首指针已变为空
       {
            HQ->front = HQ->front->next;
            free(p);
            p = HQ->front;
       }
       HQ->rear = NULL;  //置队尾指针为空
    }
    
    //主函数
    void main()
    {
        struct QueueLk q;
        int a[8] = {3,8,5,17,9,30,15,22};
        int i;
        InitQueue(&q);
        for (i = 0; i < 8; i++)
            EnQueue(&q, a[i]);
        printf("%d ", OutQueue(&q));
        printf("%d \n", OutQueue(&q));
        EnQueue(&q, 68);
        printf("%d ", PeekQueue(&q));
        printf("%d \n", OutQueue(&q));
        while (!EmptyQueue(&q))
            printf("%d ", OutQueue(&q));
        printf("\n");
        ClearQueue(&q);
    }
    
    

    运行结果同循环队列相同,只是链队无需考虑内存空间的大小。


    展开全文
  • 队列的概念 对于队列,它也是一种受限制的线性表。(即特殊的线性表) 队列是限定所有的插入操作在表的一端进行,而删除操作在表的另一端进行的线性表。 允许进行插入的一端为队尾。 允许进行删除的一段为对头。 它...
  • 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作一端称为队尾 出队列:进行删除操作一端称为队头 队列也可以...
  • 一、队列(Queue)链式存储结构 队列的链式实现 typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的...
  • 队列的概念及结构2.队列的实现 前言 栈和队列是两种常用的数据结构,因此,了解他们的概念、结构和实现方法是十分基础且必要的。 一、栈 1.栈的概念及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和...
  • 循环队列的C语言实现

    2017-05-04 19:01:00
    从生活中,可以抽象出队列的概念队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表...
  • 循环队列的c语言实现

    千次阅读 2016-09-23 21:04:46
    静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大内存浪费;链式队列是用链表来实现队列的。说白了循环队列就是一个数组,我们把这个数组当成首尾相连来使用(写到数组末尾后从头开始写)。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 629
精华内容 251
关键字:

队列c语言的概念

c语言 订阅