单链队列

  1 /**
  2  * @brief 队列的链式表示与实现
  3  * 
  4  * @author amur-leopard
  5  *
  6  * @date 2014/06/01
  7  */
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 
 11 //-----------------预定义常量和类型-------------------
 12 #define OK           1
 13 #define ERROR        0
 14 #define OVERFLOW     -1
 15 
 16 typedef int status; // 函数类型，其值是函数结果状态代码
 17 
 18 
 19 //----------------队列的链式存储结构------------------
 20 struct node
 21 {
 22     int data;
 23     struct node *next;
 24 };
 25 
 26 typedef struct node node;
 27 
 28 typedef struct
 29 {
 30     struct node *front;
 31     struct node *back;
 32 }link_queue;
 33 
 34 
 35 //------------------基本操作的声明--------------------
 36 status init(link_queue &queue); // 初始化队列
 37 status enqueue(link_queue &queue, int e); // 入队
 38 status dequeue(link_queue &queue, int &e); // 出队
 39 
 40 //------------------基本操作的实现--------------------
 41 /**
 42  * @brief 初始化队列
 43  * 
 44  * @param queue 队列
 45  *
 46  * @return 函数状态
 47  */
 48 status init(link_queue &queue)
 49 {
 50     queue.front = queue.back = (node *)malloc(sizeof(node)); // 头结点
 51     if(!queue.front)
 52     {
 53         exit(OVERFLOW);
 54     }
 55     queue.front->next = NULL; // queue.back->next = NULL
 56     return OK;
 57 }
 58 
 59 /**
 60  * @brief 入队
 61  *
 62  * @queue queue 队列
 63  * @param e 入队元素
 64  *
 65  * @return 函数状态
 66  */
 67 status enqueue(link_queue &queue, int e)
 68 {
 69     node *n = (node *)malloc(sizeof(node)); // 新入队元素结点
 70     if(!n)
 71     {
 72         exit(OVERFLOW);
 73     }
 74     n->data = e;
 75     n->next = NULL;
 76     queue.back->next = n;
 77     queue.back = n;
 78     return OK;
 79 }
 80 
 81 /**
 82  * @brief 出队
 83  *
 84  * @queue queue 队列
 85  * @queue e 用于返回队首元素
 86  *
 87  * @return 函数状态
 88  */
 89 status dequeue(link_queue &queue, int &e)
 90 {
 91     node *p; // 用于指向队首
 92     if(queue.front == queue.back)
 93     {
 94         return ERROR;
 95     }
 96     p = queue.front->next;
 97     e = p->data;
 98     queue.front->next = p->next;
 99     if(queue.back == p) // 最后一个元素
100     {
101         queue.back = queue.front; // 队尾指针重新赋值
102     }
103     free(p);
104     return OK;
105 }
106 
107 
108 //-----------------------测试-------------------------
109 /**
110  * @brief 测试函数
111  */
112 void main()
113 {
114     int e; link_queue queue; init(queue);
115 
116     if(OK == enqueue(queue, 11)) printf("enqueue succeed! 11\n");
117     if(OK == enqueue(queue, 22)) printf("enqueue succeed! 22\n");
118     if(OK == enqueue(queue, 33)) printf("enqueue succeed! 33\n");
119 
120     if(OK == dequeue(queue, e)) printf("dequeue succeed! %d\n", e);
121     if(OK == dequeue(queue, e)) printf("dequeue succeed! %d\n", e);
122     if(OK == dequeue(queue, e)) printf("dequeue succeed! %d\n", e);
123 
124     if(ERROR == dequeue(queue, e)) printf("empty!\n");
125 
126     system("pause");
127 }