先进先出(FIFO, First In First Out)
顺序队列
error.h
#ifndef __ERROR_H__ #define __ERROR_H__ #include <stdio.h> #define ERROR -1 #define FULL_STACK -2 #define EMPTY_STACK -3 #define MALLOC_ERROR -4 #define FULL_QUEUE -5 #define EMPTY_QUEUE -6 int errno; // 错误号 void myError(char *str); char* myStrError(int num); #endif // __ERROR_H__error.c
#include "error.h" void myError(char *str) { char *msg = myStrError(errno); printf ("%s: %s\n", str, msg); /* switch (errno) { case ERROR: printf ("%s: 输入参数错误\n", str); break; case FULL_STACK: printf ("%s: 满栈状态\n", str); break; case EMPTY_STACK: printf ("%s: 空栈状态\n", str); break; case MALLOC_ERROR: printf ("%s: 空间分配失败\n", str); break; } */ } char* myStrError(int num) { switch (errno) { case ERROR: return "输入参数错误"; case FULL_STACK: return "满栈状态"; case EMPTY_STACK: return "空栈状态"; case MALLOC_ERROR: return "空间分配失败"; case FULL_QUEUE: return "队满状态"; case EMPTY_QUEUE: return "队空状态"; } }
SqQueue.h
#ifndef __SQQUEUE_H__ #define __SQQUEUE_H__ #include "error.h" #define TRUE 1 #define FALSE 0 #define SIZE 10 typedef int QueueData; typedef struct _queue { QueueData data[SIZE]; int front; // 指向队头的下标 int rear; // 指向队尾的下标 }Queue; // 置空队 int InitQueue (Queue *Q); // 判队空否 int QueueEmpty (Queue *Q); // 判队满否 int QueueFull (Queue *Q); // 进队 int EnQueue (Queue *Q, QueueData x); // 出队 int DeQueue (Queue *Q, QueueData *x); // 取队头 int GetFront (Queue *Q, QueueData *x); #endif // __SQQUEUE_H__SqQueue.c
#include "SqQueue.h" int InitQueue (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } // 置空队 q->front = 0; q->rear = 0; return TRUE; } int QueueEmpty (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } return q->front == q->rear; } int QueueFull (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } return q->front == (q->rear+1)%SIZE; } int EnQueue (Queue *q, QueueData x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueFull(q)) { errno = FULL_QUEUE; return FALSE; } q->rear = (q->rear+1) % SIZE; q->data[q->rear] = x; return TRUE; } int DeQueue (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } q->front = (q->front + 1) % SIZE; *x = q->data[q->front]; return TRUE; } int GetFront (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } int index = (q->front + 1) % SIZE; *x = q->data[index]; return TRUE; }main.c
#include "SqQueue.h" #include <stdio.h> int main() { Queue q; InitQueue(&q); if (QueueEmpty(&q)) { printf ("空队\n"); } int i; char str[50]; for (i = 0; i < 10; i++) { if (EnQueue(&q, i) != TRUE) { sprintf (str, "第 %d 个元素入队失败", i); myError(str); } } int x; for (i = 0; i < 10; i++) { if (DeQueue(&q, &x) != TRUE) { sprintf (str, "第 %d 个元素出队失败", i); myError(str); } printf ("x = %d\n", x); } return 0; }
链式队列
error.h
#ifndef __ERROR_H__ #define __ERROR_H__ #include <stdio.h> #define ERROR -1 #define FULL_STACK -2 #define EMPTY_STACK -3 #define MALLOC_ERROR -4 #define FULL_QUEUE -5 #define EMPTY_QUEUE -6 int errno; // 错误号 void myError(char *str); char* myStrError(int num); #endif // __ERROR_H__error.c
#include "error.h" void myError(char *str) { char *msg = myStrError(errno); printf ("%s: %s\n", str, msg); /* switch (errno) { case ERROR: printf ("%s: 输入参数错误\n", str); break; case FULL_STACK: printf ("%s: 满栈状态\n", str); break; case EMPTY_STACK: printf ("%s: 空栈状态\n", str); break; case MALLOC_ERROR: printf ("%s: 空间分配失败\n", str); break; } */ } char* myStrError(int num) { switch (errno) { case ERROR: return "输入参数错误"; case FULL_STACK: return "满栈状态"; case EMPTY_STACK: return "空栈状态"; case MALLOC_ERROR: return "空间分配失败"; case FULL_QUEUE: return "队满状态"; case EMPTY_QUEUE: return "队空状态"; } }LinkQueue.h
#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ #include "error.h" #define TRUE 1 #define FALSE 0 typedef int QueueData; typedef struct _node { QueueData data; struct _node *next; }Node; typedef struct _queue { Node *front; Node *rear; }Queue; Queue* Create_Queue(); int QueueEmpty (Queue *Q); // 进队 int EnQueue (Queue *Q, QueueData x); // 出队 int DeQueue (Queue *Q, QueueData *x); // 取队头 int GetFront (Queue *Q, QueueData *x); int Destroy_Queue (Queue *Q); #endif // __LINKQUEUE_H__LinkQueue.c
#include "LinkQueue.h" #include <stdlib.h> Queue* Create_Queue() { Queue * q = (Queue*)malloc(sizeof(Queue)/sizeof(char)); if (q == NULL) { errno = MALLOC_ERROR; return NULL; } // 置空队 q->front = NULL; q->rear = NULL; return q; } int QueueEmpty (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } return q->front == NULL; } int EnQueue (Queue *q, QueueData x) { if (q == NULL) { errno = ERROR; return FALSE; } Node * node = (Node*)malloc(sizeof(Node)/sizeof(char)); if (node == NULL) { errno = MALLOC_ERROR; return FALSE; } node->data = x; node->next = NULL; if (q->front == NULL) { q->front = node; q->rear = node; } else { q->rear->next = node; q->rear = node; } return TRUE; } int DeQueue (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } Node *p = q->front; *x = p->data; q->front = p->next; free(p); if (q->front == NULL) q->rear = NULL; return TRUE; } int GetFront (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } *x = q->front->data; return TRUE; } int Destroy_Queue (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } int x; while (QueueEmpty(q) != TRUE) { DeQueue(q, &x); } free(q); return TRUE; }main.c
#include "LinkQueue.h" #include <stdio.h> int main() { Queue* q = Create_Queue(); int i; char str[50]; for (i = 0; i < 10; i++) { if (EnQueue(q, i) != TRUE) { sprintf (str, "第 %d 个元素入队失败", i); myError(str); } } int x; for (i = 0; i < 10; i++) { if (DeQueue(q, &x) != TRUE) { sprintf (str, "第 %d 个元素出队失败", i); myError(str); } printf ("x = %d\n", x); } return 0; }