赞
踩
目录
队列是一种特殊的线性表,也是一种运算受限的线性表,插入限定在表的某一端进行,删除限定在表的另一端进行。
先进先出、后进后出
与栈类似,队列也有两种常用存储结构,即顺序存储结构和链式存储结构。
以顺序存储方式存储的队列称为顺序队。由一个一维数组和队头指针和队尾指针变量组成,一般用循环队列。
(1)队空条件:sq.front==qs.rear.
(2)队满条件:(sq.rear+1)%MaxSize==sq.front.
(3)进队操作:sq.rear循环进1;元素进队。
(4)出队操作:sq.front 循环进1;元素出队.
- #include <stdio.h>
- #include<malloc.h>
- typedef char ElemType;
- #define MaxSize 200
- typedef struct
- {
- ElemType data[MaxSize];
- int front,rear; //定义队头队尾指针
- }SqQueue;
- //初始化
-
- void InitQueue(SqQueue &sq)
- {
- sq.rear=sq.front=0; //指针初始化
- }
- //销毁
- void DestroyQueue(SqQueue sq)
- {
- }
- //进栈
- int EnQueue(SqQueue &sq,ElemType x)
- {
- if((sq.rear+1)%MaxSize==sq.front) //判断队满情况
- return 0;
- sq.rear=(sq.rear+1)%MaxSize; //从队尾插入,进1
- sq.data[sq.rear]=x;
- return 1;
- }
- //出队
- int DeQueue(SqQueue &sq,ElemType &x)
- {
- if(sq.rear==sq.front) //判断队空
- return 0;
- sq.front=(sq.front+1)%MaxSize; //队头循环进1
- x=sq.data[sq.front];
- return 1;
- }
- int GetHead(SqQueue sq,ElemType &x)
- {
- if(sq.rear==sq.front) //队空情况
- return 0;
- x=sq.data[(sq.front+1)%MaxSize];
- return 1;
- }
- //判断队空
- int QueueEmpty(SqQueue sq)
- {
- if(sq.rear==sq.front)
- return 1;
- else return 0;
- }
-
- void main()
- {
- SqQueue sq;
- ElemType e;
- printf("初始化队列\n");
- InitQueue(sq);
- printf("队%s\n",(QueueEmpty(sq)==1 ? "空":"不空"));
- printf("a进队\n");
- EnQueue(sq,'a');
- printf("b进队\n");
- EnQueue(sq,'b');
- printf("c进队\n");
- EnQueue(sq,'c');
- printf("d进队\n");
- EnQueue(sq,'d');
- printf("e进队\n");
- EnQueue(sq,'e');
- printf("f进队\n");
- EnQueue(sq,'f');
- printf("队%s\n",(QueueEmpty(sq)==1 ? "空":"不空"));
- GetHead(sq,e);
- printf("队头元素:%c\n",e);
- printf("出队次序:");
- while(!QueueEmpty(sq))
- {
- DeQueue(sq,e);
- printf("%c",e);
- }
- printf("\n");
- DestroyQueue(sq);
- }
采用链式存储的队列称为链队。含有单链表的基本特性。
(1)队空条件: st->front ==NULL.
(2)队满:不考虑
(3)进队操作:创建结点p,将其插入到队尾,并由st->rear指向它。
(4)出队操作:删除队头结点。
- #include <stdio.h>
- #include <malloc.h>
- #include<string.h>
- typedef ElemType;
-
- //数据结点类型声明
- typedef struct QNode
- {
- ElemType data;
- struct QNode *next;
- }QType;
-
- //链队的数据类型结点声明
- typedef struct qptr
- {
- QType *front; //队头指针
- QType *rear; //队尾指针
- }LinkQueue; //链队结点类型
-
- //初始化
- void InitQueue(LinkQueue *&st)
- {
- st=(LinkQueue *)malloc(sizeof(LinkQueue));
- st->rear=st->front=NULL; //初始化,队头和队尾指针均为空
- }
-
- //销毁
- void DestroyQueue(LinkQueue *&st)
- {
- QType *p1=st->front,*p;
- if(p1!=NULL) //队不为空时
- {
- if(p1==st->rear) //只有一个数据结点的情况
- free(p1); //释放p1结点
- else //有两个或多个数据结点的情况
- {
- p=p1->next;
- while(p!=NULL)
- {
- free(p1); //释放p1结点
- p1=p;
- p=p->next;
- }
- free(p1);
- }
- }
- free(st); //释放链队结点
- }
-
- //进队
- int EnQueue(LinkQueue *&st,ElemType x)
- {
- QType *s;
- s=(QType *)malloc(sizeof(QType)); //创建新结点s,
- s->data=x;
- s->next=NULL;
- if(st->front==NULL)
- st->rear=st->front=s;
- else
- {
- st->rear->next=s;
- st->rear=s;
- }
- return 1;
- }
-
- //出队
- int DeQueue(LinkQueue *&st,ElemType &x)
- {
- QType *p;
- if(st->front ==NULL) //空队的情况
- return 0;
- p=st->front;
- x=p->data;
- if(st->rear==st->front) //取队头元素
- {
- st->rear=st->front=NULL;
- }else
- {
- st->front=st->front->next;
- }
- free(p);
- return 1;
- }
- //取队头元素计算
- int GetHead(LinkQueue *st,ElemType &x)
- {
- if(st->front==NULL)
- return 0;
- x=st->front->data;
- return 1;
- }
- //判断是否队空
- int QueueEmpty(LinkQueue *st)
- {
- if(st->front==NULL)
- return 1;
- else
- return 0;
- }
-
- void main()
- {
- LinkQueue *st;
- ElemType e;
- printf("初始化队列\n");
- InitQueue(st);
- printf("队%s\n",(QueueEmpty(st)==1 ? "空":"不空"));
- printf("a进队\n");
- EnQueue(st,'a');
- printf("b进队\n");
- EnQueue(st,'b');
- printf("c进队\n");
- EnQueue(st,'c');
- printf("d进队\n");
- EnQueue(st,'d');
- printf("e进队\n");
- EnQueue(st,'e');
- printf("f进队\n");
- EnQueue(st,'f');
- printf("队%s\n",(QueueEmpty(st)==1 ? "空":"不空"));
- GetHead(st,e);
- printf("队头元素:%c\n",e);
- printf("出队次序:");
- while(!QueueEmpty(st))
- {
- DeQueue(st,e);
- printf("%c",e);
- }
- printf("\n");
- DestroyQueue(st);
- }
顺序队和链队比较,链表可以实时申请空间,不考虑空间利用问题,因此比顺序队有一定的优势。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。