首页 > 代码库 > 队列的数组和链表实现
队列的数组和链表实现
队列的数组和链表实现
队列的单链表实现
queue.h
#ifndef QUEUE_H_#define QUEUE_H_typedef int ElementType;#ifndef _QUEUE_LIST_#define _QUEUE_LIST_struct QNode;typedef struct QNode * QNodePtr;struct QNode{ ElementType Element; QNodePtr Next;}QNode;typedef struct Node{ QNodePtr Front; QNodePtr Rear;}Node,*PtrToNode;typedef PtrToNode Queue;int IsEmpty(Queue Q); //判断队列是否为空Q->Rear == Q->Front;Queue CreateQueue(); //构造队列void DisposeQueue(Queue Q); //删除整个队列，回收空间void MakeEmpty(Queue Q); //释放队列空间，将其置为空void EnQueue(ElementType X, Queue Q); //在队列尾端插入元素ElementType Front(Queue Q); //取出对头元素，但不删除void Dequeue(Queue Q); //删除对头元素ElementType FrontAndDequeue(Queue Q); //void PrintQueue(Queue Q); //打印队列#endif#endif /* QUEUE_H_ */
queue.c
#include "queue.h"#include <stdio.h>#include <stdlib.h>int IsEmpty(Queue Q) { return Q->Rear == Q->Front;}void MakeEmpty(Queue Q) { if (Q == NULL) { printf("The queue is empty! Must use CreateQueue first!\n"); return; } else { while (!IsEmpty(Q)) Dequeue(Q); }}Queue CreateQueue() { //不仅要为对头(Queue)申请空间，还要为队列元素/节点（QNode）申请空间. Queue Q; Q = (Queue) malloc(sizeof(struct Node)); if (Q == NULL) { printf("Out of space!\n"); return NULL; } Q->Front = Q->Rear = (QNodePtr) malloc(sizeof(struct QNode)); if (Q->Front == NULL) { printf("Out of space!\n"); return NULL; } Q->Front->Next = NULL; return Q;}void DisposeQueue(Queue Q) { while (Q->Front != NULL) { Q->Rear = Q->Front->Next; free(Q->Front); Q->Front = Q->Rear; }}void Dequeue(Queue Q) { //删除链队列第一个元素 if (!IsEmpty(Q)) { QNodePtr P; P = Q->Front->Next; Q->Front->Next = P->Next; if (Q->Rear == P) //判断队列中是否只有一个元素 Q->Rear = Q->Front; free(P); } else { printf("The queue is empty!\n"); }}void EnQueue(ElementType X, Queue Q) { QNodePtr P = (QNodePtr) malloc(sizeof(struct QNode)); if (P == NULL) { printf("Out of space!\n"); return; } else { P->Next = NULL; P->Element = X; Q->Rear->Next = P; Q->Rear = P; }}ElementType Front(Queue Q) { return Q->Front->Next->Element;}ElementType FrontAndDequeue(Queue Q) { ElementType X = 0; if (!IsEmpty(Q)) { X = Front(Q); Dequeue(Q); } else { printf("The queue is empty!\n"); } return X;}void PrintQueue(Queue Q) { QNodePtr P = Q->Front; while (P != Q->Rear) { P = P->Next; printf("%d\n", P->Element); }}
linkqueue.c
#include<stdio.h>#include "queue.h"int main(void) { Queue Q; Q = CreateQueue(); int i; for (i = 0; i < 10; i++) { EnQueue(i, Q); } PrintQueue(Q); return 0;}
单链表实现创建头结点
循环数组实现
循环队列一般是用循环数组实现，其判空条件有多种方式：其一是设一个标志位以区别队列是空还是满；其二是少用一个元素空间，约定以队列头指针在队列尾指针的下一位置上作为队列呈满状态标志。或者是如下面代码所示，为表示队列的结构体设置一个表示队列大小的size标志，若size为0，那么队列为空。
queue.h
#ifndef _QUEUE_#define _QUEUE_typedef int ElementType;typedef struct QueueRecord{ int Capacity; int Front; int Rear; int Size; ElementType *Array;}*Queue;int IsEmpty( Queue Q );int IsFull( Queue Q );Queue CreateQueue( int MaxElements );void DisposeQueue( Queue Q );void MakeEmpty( Queue Q );void EnQueue( ElementType X, Queue Q );ElementType Front( Queue Q );void Dequeue( Queue Q );ElementType FrontAndDequeue( Queue Q );#endif
queue.c
#include "queue.h"#include <stdio.h>#include <stdlib.h>int IsEmpty( Queue Q ){ return Q->Size == 0;}int IsFull( Queue Q ){ return Q->Size == Q->Capacity;}void MakeEmpty( Queue Q ){ Q->Size = 0; Q->Front = 1; Q->Rear = 0;}Queue CreateQueue( int MaxElements ){ Queue Q; Q = (Queue)malloc(sizeof(struct QueueRecord)); if (Q == NULL) { printf("Out of space!\n"); return NULL; } Q->Array = (ElementType*)malloc(sizeof(ElementType) * MaxElements); if (Q->Array == NULL) { printf("Out of space!\n"); return NULL; } Q->Capacity = MaxElements; MakeEmpty(Q); return Q;}void DisposeQueue( Queue Q ){ if (Q != NULL) { free(Q->Array); free(Q); }}static int Succ(int Value, Queue Q){ if (++Value =http://www.mamicode.com/= Q->Capacity) Value = 0; return Value;}void EnQueue( ElementType X, Queue Q ){ if (IsFull(Q)) { printf("Queue is full!\n"); return; } else { Q->Size++; Q->Rear = Succ(Q->Rear, Q); //Q->Rear = (Q->Rear + 1) % Q->Capacity ? Q->Rear + 1 : 0; Q->Array[Q->Rear] = X; }}ElementType Front( Queue Q ){ if (!IsEmpty(Q)) { return Q->Array[Q->Front]; } printf("Queue is Empty!\n"); return 0;}void Dequeue( Queue Q ){ if (!IsEmpty(Q)) { Q->Size--; Q->Front = Succ(Q->Front, Q); } else { printf("Queue is Empty!\n"); }}ElementType FrontAndDequeue( Queue Q ){ ElementType X = 0; if (!IsEmpty(Q)) { Q->Size--; X = Q->Array[Q->Front]; Q->Front = Succ(Q->Front, Q); } else { printf("Queue is Empty!\n"); } return X;}
main.c
#include<stdio.h>#include "queue.h"int main(void) { Queue Q; Q = CreateQueue(10); int i,j; for (i = 0; i < 10; i++) { EnQueue(i, Q); } for(i = 0;i < 10;i++){ j = FrontAndDequeue(Q); printf("%d ",j); } return 0;}
循环数组实现队列 通过size来判断队列是否为空，capacity来判断是否已满，头尾指针只关心基本操作，数组内值在入队后改变，之前值保留
单链表实现队列，设置头结点，头尾指针都指向头结点链表为空，动态增加节点，出队释放空间
转自 http://blog.csdn.net/universitycd/article/details/8862180
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。