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;
}
