链队列-阿里云开发者社区

来源：http://blog.csdn.net/hopeyouknow/article/details/6736987

队列也是常用的数据结构之一，下面给出一个链式队列的实现~~

头文件Queue.h

[cpp] view plain copy

#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.c如下:

[cpp] view plain copy

#include"Queue.h"
#include<malloc.h>
#include<stdio.h>
/*构造一个空队列*/
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;
}
}

简单测试程序Test.c

[cpp] view plain copy

#include"Queue.h"
#include<stdio.h>
void print(Item i)
{
printf("该节点元素为%d\n",i);
}
main()
{
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");
}

方法二：

  1 /*******************************************************************************
  2 /* <PRE>
  3 /* 版权所有    : -
  4 /* 模块名      : 栈和队列
  5 /* 文件名      : lqueue.cpp
  6 /* 功能描述    : 链队列的表示与实现 
  7 /* 作者        : <xxx>
  8 /* 版本        : 1.0
  9 /* -----------------------------------------------------------------------------
 10 /* 备注        : -
 11 /* -----------------------------------------------------------------------------
 12 /* 修改记录    :
 13 /* 日 期        版本     修改人        修改内容
 14 /* 2011/01/01   1.0      <xxx>         创建
 15 /* </PRE>
 16 *******************************************************************************/
 17 #include <stdio.h>
 18 #include <stdlib.h>
 19 
 20 /******************************************************************************
 21 /* 数据类型和常量定义
 22 /******************************************************************************/
 23 #define OK           1
 24 #define ERROR        0
 25 #define OVERFLOW    -2
 26 
 27 typedef int Status;
 28 typedef int QElemType;
 29 
 30 
 31 /******************************************************************************
 32 /* 数据结构声明
 33 /******************************************************************************/
 34 /* 单链队列 - 队列的链式存储结构 */
 35 typedef struct QNode{
 36     QElemType data;
 37     struct QNode *next;
 38 } QNode, *QueuePtr;
 39 
 40 typedef struct {
 41     QueuePtr front; /* 队头指针 */
 42     QueuePtr rear;  /* 队尾指针 */
 43 } LinkQueue;
 44 
 45 
 46 /******************************************************************************
 47 /* 函数原型声明
 48 /******************************************************************************/
 49 /*队列操作函数*/
 50 Status InitQueue(LinkQueue &Q);
 51 Status DestroyQueue(LinkQueue &Q);
 52 Status ClearQueue(LinkQueue &Q);
 53 Status QueueEmpty(LinkQueue Q);
 54 int QueueLength(LinkQueue Q);
 55 Status GetHead(LinkQueue Q, QElemType &e);
 56 Status EnQueue(LinkQueue &Q, QElemType e);
 57 Status DeQueue(LinkQueue &Q, QElemType &e);
 58 
 59 
 60 /*******************************************************************************
 61 /* <FUNC>
 62 /* 函数名   : InitQueue
 63 /* 功能     : 构造空队列
 64 /* 参数     : -
 65 /* 返回值   : -
 66 /* 备注     : 构造一个空队列Q
 67 /* 作者     : <xxx>
 68 /* </FUNC>
 69 *******************************************************************************/
 70 Status InitQueue(LinkQueue &Q) {
 71     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
 72     if (!Q.front) exit(OVERFLOW);
 73     Q.front->next = NULL;
 74     return OK;
 75 }
 76 
 77 /*******************************************************************************
 78 /* <FUNC>
 79 /* 函数名   : DestroyQueue
 80 /* 功能     : 销毁队列
 81 /* 参数     : -
 82 /* 返回值   : -
 83 /* 备注     : 销毁队列Q
 84 /* 作者     : <xxx>
 85 /* </FUNC>
 86 *******************************************************************************/
 87 Status DestroyQueue(LinkQueue &Q) {
 88     while (Q.front) {
 89         Q.rear = Q.front->next;
 90         free(Q.front);
 91         Q.front = Q.rear;
 92     }
 93     return OK;
 94 }
 95 
 96 /*******************************************************************************
 97 /* <FUNC>
 98 /* 函数名   : EnQueue
 99 /* 功能     : 入队列
100 /* 参数     : -
101 /* 返回值   : -
102 /* 备注     : 插入元素e为Q的新的队尾元素
103 /* 作者     : <xxx>
104 /* </FUNC>
105 *******************************************************************************/
106 Status EnQueue(LinkQueue &Q, QElemType e) {
107     struct QNode *p = (QueuePtr)malloc(sizeof(QNode));
108     if (!p) exit(OVERFLOW);
109     p->data = e; p->next = NULL;
110     Q.rear->next = p;
111     Q.rear = p;
112     return OK;
113 }
114 
115 /*******************************************************************************
116 /* <FUNC>
117 /* 函数名   : DeQueue
118 /* 功能     : 出队列
119 /* 参数     : -
120 /* 返回值   : -
121 /* 备注     : 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
122 /* 作者     : <xxx>
123 /* </FUNC>
124 *******************************************************************************/
125 Status DeQueue(LinkQueue &Q, QElemType &e) {
126     struct QNode *p = NULL;
127     if (Q.front == Q.rear) return ERROR;
128     p = Q.front->next;
129     e = p->data;
130     Q.front->next = p->next;
131     if (Q.rear == p) Q.rear = Q.front;
132     free(p);
133     return OK;
134 }
135 
136 
137 /*******************************************************************************
138 /* <FUNC>
139 /* 函数名   : main
140 /* 功能     : 测试函数
141 /* 参数     : -
142 /* 返回值   : -
143 /* 备注     : -
144 /* 作者     : <xxx>
145 /* </FUNC>
146 *******************************************************************************/
147 void main()
148 {
149     LinkQueue Q;  QElemType e;
150     InitQueue(Q);
151     EnQueue(Q, 10);
152     EnQueue(Q, 20);
153     EnQueue(Q, 30);
154     if(OK == DeQueue(Q, e)) printf("%d\n", e);
155     if(OK == DeQueue(Q, e)) printf("%d\n", e);
156     if(OK == DeQueue(Q, e)) printf("%d\n", e);
157     if(OK == DeQueue(Q, e)) printf("%d\n", e);
158 }

参考：http://www.cnblogs.com/JCSU/articles/2005839.html

微信公众号：猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。

链队列

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

链队列

热门文章

最新文章

相关电子书