数据结构––队列

1.队列的定义

2.队列的分类

2.1循环队

2.2链式队

3.队列的实现

3.1循环队

3.1.1声明

typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {QDataType *data;int front;  //头指针int rear;   //尾指针
}Queue;

3.1.2初始化

void QueueInit(Queue* q) 
{q->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);if (q->data == NULL){perror("malloc fail:");return;}q->front = 0;q->rear = 0;
}

3.1.3判断队列是否为空

bool QueueEmpty(Queue*q)
{assert(q);return q->front == q->rear;
}

3.1.4判断队列是否为满

bool QueueFull(Queue*q)
{assert(q);return q->front == (q->rear+1)%MAXSIZE;
}

3.1.5入队

void QueuePush(Queue* q, QDataType x) 
{assert(q);if(QueueFull){printf("队列已满\n");return ;}q->data[q->rear] = x;   q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}

3.1.6出队

void QueuePop(Queue* q){assert(q);assert(!QueueEmpty(q));q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部}

3.1.7打印队列

void QueuePrint(Queue* q){assert(q);int cur = q->front;printf("队头->");while (cur != q->rear){printf("%d->", q->data[cur]);cur = (cur + 1) % MAXSIZE;}printf("队尾\n");}

3.1.8销毁队列

void QueueDestroy(Deque* q)//销毁队列
{assert(q);free(q->data);q->data = NULL;q->front = q->rear = 0;
}

3.2链

3.2.1声明

typedef int QDataType;
typedef struct QueueNode 
{QDataType data;struct QueueNode* next;
}QNode;
typedef struct Queue 
{QNode* front;QNode* rear;size_t size;
}Queue;

3.2.2初始化

void QueueInit(Queue* q)
{q->front = NULL;q->rear = NULL;q->size = 0;
}

3.2.3判断队列是否为空

bool QueueEmpty(Queue* q)
{assert(q);return (q->front == NULL) && (q->rear == NULL);
}

void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;if (newnode == NULL){perror("malloc fail");return;}if (q->front == NULL){q->front = q->rear = newnode;}else{q->rear->next = newnode;q->rear = newnode;}q->size++;
}

3.2.4出队

void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//1.只有一个结点if (q->front == q->rear){free(q->front);q->front = q->rear = NULL;}//2.有多个结点else{QNode* del = q->front;q->front = q->front->next;free(del);del = NULL;}q->size--;
}

3.2.5打印队列

void QueuePrint(Queue* q)
{assert(q);QNode* cur = q->front;QNode* tail = q->rear;printf("队头->");while (cur != tail->next){printf("%d->",cur->data);cur = cur->next;}printf("队尾\n");
}

3.2.6销毁队列

void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* del = cur;cur = cur->next;free(del);del = NULL;}q->front = q->rear = NULL;
}