队列的存储结构有两种:一种是线性表存储,一种是链式存储。用线性表存储时,要注意队列的长度有没有超过预先设置的大小,在这个程序中,队列的可以在存满的时候,自动增加队列的长度。用链表存储,则没有长度的限制。下面分别是这两种存储结构的实现。
线性表存储:
#include <stdio.h> #include <stdlib.h> #define QUEUE_INIT_SIZE 10 #define QUEUE_REALLOCATION 2 typedef int ElemType; /*顺序队列的存储结构定义*/ typedef struct SqQueue { ElemType *base; int front; int rear; int QueueLength; }SqQueue; void Init_SqQueue(SqQueue *S) { S->base = (ElemType*)malloc(QUEUE_INIT_SIZE*sizeof(ElemType)); if (!S->base) exit(1); S->rear = S->front = 0; S->QueueLength = QUEUE_INIT_SIZE; } void En_SqQueue(SqQueue *S, ElemType e) { if ((S->rear + 1) % S->QueueLength == S->front){ S->base = (ElemType*)malloc(S->base,(S->QueueLength+QUEUE_REALLOCATION)*sizeof(ElemType)); if (!S->base) exit(1); if (S->front > S->rear){ int i; for (i = S->front; i < S->QueueLength; ++i){ S->base[i + QUEUE_REALLOCATION] = S->base[i]; } S->front += QUEUE_REALLOCATION; } S->QueueLength += QUEUE_REALLOCATION; } S->base[S->rear] = e; S->rear = (S->rear + 1) % S->QueueLength; } int De_SqQueue(SqQueue *S, ElemType *e) { if (S->rear == S->front) return 0; *e = S->base[S->front]; S->front = (S->front + 1) % S->QueueLength; return 1; } int SqQueueLength(SqQueue S) { return (S.rear - S.front + S.QueueLength) % S.QueueLength; } int is_SqQueueEmpty(SqQueue S) { if (S.front == S.rear) return 1; else return 0; } void SqQueueTest() { SqQueue S; Init_SqQueue(&S); printf("Please input some numbers to enqueue(Ctrl+Z to end):\n"); int e; while (scanf("%d", &e) != EOF) En_SqQueue(&S, e); printf("The dequeue sequence is:\n"); while (!is_SqQueueEmpty(S)){ De_SqQueue(&S,&e); printf("%d ",e); } printf("\n"); } int main() { SqQueueTest(); return 0; }
链表存储:
#include <stdio.h> #include <stdlib.h> /*链式队列的存储结构定义*/ typedef struct LinkQueue_Node { ElemType data; struct LinkQueue_Node *next; }*Queue_pNode, Queue_Node; typedef struct LinkQueue { struct LinkQueue_Node *front; struct LinkQueue_Node *rear; }LinkQueue; void Init_LinkQueue(LinkQueue *L) { L->front = L->rear = (Queue_pNode)malloc(sizeof(Queue_Node)); if (!L->front) exit(1); L->front->data = 0; L->front->next = NULL; } void En_LinkQueue(LinkQueue *L, ElemType e) { Queue_pNode p = (Queue_pNode)malloc(sizeof(Queue_Node)); if (!p) exit(1); p->data = e; p->next = NULL; L->rear->next = p; L->rear = p; } int De_LinkQueue(LinkQueue *L, ElemType *e) { Queue_pNode p=L->front->next; if (L->front == L->rear) return 0; *e = p->data; L->front->next = p->next; if (p == L->rear) L->rear = L->front; free(p); return 1; } int LinkQueueLength(LinkQueue L) { Queue_pNode p = L.front; if (L.front == L.rear) return 0; int length = 0; while (p != L.rear){ ++length; p = p->next; } return length; } int is_LinkQueueEmpty(LinkQueue L) { if (L.front == L.rear) return 1; else return 0; } void LinkQueueTest() { LinkQueue L; Init_LinkQueue(&L); printf("Please input some numbers to enqueue(Ctrl+Z to end).\n"); int e; while (scanf("%d", &e) != EOF) En_LinkQueue(&L,e); printf("The dequeue sequence is : \n"); while (!is_LinkQueueEmpty(L)){ De_LinkQueue(&L,&e); printf("%d ",e); } printf("\n"); } int main() { LinkQueueTest(); return 0; }
原文:http://blog.csdn.net/nyist327/article/details/29416277