数据结构与算法-链式队列
链式队列的定义
链式队列是用链表来实现的队列，不存在队满的情况。链式队列也包里队列的特点。所以我们实现链式队列的 尾部进，头部出。
链式队列的结构
我们实现链式队列，首先要定一个链式队列的结构。我们要：1.定义结点。2.定义结构。
#define OK 1
#define ERROR 0
#define TURE 1
#define FLASE 0
typedef int Status;
typedef int ElemType;
//结点
typedef struct SqNode{
ElemType data;
struct SqNode *next;
}SqNode, *SqQueuePtr;
//结构
typedef struct Queue{
SqQueuePtr front;
SqQueuePtr rear;
}LinkQueue;
这样，我们就定义了一个链式队列的结构，我们就可以进行链式队列的操作了。
链式队列的初始化
链式队列的初始化，即是给开辟一个空间，然后让队列的头指针和尾指针都指向这个开辟的空间。由此，一个简单的队列就完成了。
//初始化
Status InitLinkQueue(LinkQueue *Q){
Q->front = Q->rear = (SqQueuePtr)malloc(sizeof(SqNode));
if (!Q->front) return ERROR;
Q->front->next = NULL;//头结点置空
return OK;
}
链式队列的销毁
链式队列的销毁不同于链式队列的清空。销毁的意思很明确，就是 干掉 😝。
//销毁队列
Status DestroyLinkQueue(LinkQueue *Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
链式队列的清空
上面说了销毁，接下来说下清空。可以和销毁的代码比对下，就可以更好的理解。
//置空
Status ClearLinkQueue(LinkQueue *Q){
SqQueuePtr p,temp;
//清空
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
//删除内存
while (p) {
temp = p->next;
p = temp;
free(temp);
}
return OK;
}
判断链式队列是否为空
判断链式队列为空的条件就是，头尾指针是否指向同一块内存。
//判断队列是否为空
Status IsEmptyLinkQueue(LinkQueue Q){
if (Q.front == Q.rear) {
return OK;
}
return ERROR;
}
获取链式队列的长度
链式队列的长度即是其中的结点树，这里我声明一个int i，然后遍历队列。
//长度
int LengthOfLinkQueue(LinkQueue Q){
int i = 0;
SqQueuePtr p;
p = Q.front;
while (p != Q.rear) {
p = p->next;
i++;
}
return i;
}
链式队列的入队操作
链式队列不存在队满的情况，所以入队操作就直接在尾指针后再加一个，然后移动一下尾指针。
//入队
Status InLinkQueue(LinkQueue *Q, ElemType data){
SqQueuePtr temp = (SqQueuePtr)malloc(sizeof(SqNode));
if (!temp) return ERROR;
temp->data = data;
temp->next = NULL;
Q->rear->next = temp;
Q->rear = temp;
return OK;
}
链式队列的出队操作
出队操作：首先要考虑队列是否为空。然后顶部元素出去。这里我们设置了头结点，所以很方便操作。头结点指向第一个元素，移除，然后向后移动一下就可以了。当然，不能忘记把移除的内存free掉。😆
//出队
Status OutLinkQueue(LinkQueue *Q, ElemType *e){
if (IsEmptyLinkQueue(*Q)) return ERROR;
SqQueuePtr temp;
temp = Q->front->next;
*e = temp->data;
Q->front->next = temp->next;
if (Q->rear == temp) {
Q->rear = Q->front;
}
free(temp);
return OK;
}
链式队列的对头元素
这个就很简单了。头顶的元素。直接获取即可。
Status GetTopValue(LinkQueue Q, ElemType *e){
if (IsEmptyLinkQueue(Q)) return ERROR;
*e = Q.front->next->data;
return OK;
}
链式队列的遍历
链式队列的遍历，我们直接通过打印可以更直观的观察。
void printLinkQueue(LinkQueue Q){
printf("打印链式队列\n");
if (IsEmptyLinkQueue(Q)) return;
SqQueuePtr temp;
temp = Q.front->next;
while (temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
以上就是链式队列的基本操作。 我在main方法写了一些打印：
int main(int argc, const char * argv[]) {
// insert code here...
printf("链式队列，go go go!\n");
LinkQueue Q;
ElemType data;
if (InitLinkQueue(&Q)) {
printf("插入队列\n");
for (int i = 1; i < 6; i++) {
InLinkQueue(&Q, i);
}
}
printLinkQueue(Q);
printf("出队一个元素\n");
OutLinkQueue(&Q, &data);
printf("出队元素为%d\n",data);
printf("队列长度为%d\n",LengthOfLinkQueue(Q));
GetTopValue(Q, &data);
printf("对头元素为:%d\n",data);
return 0;
}
输出如下：
链式队列，go go go!
插入队列
打印链式队列1 2 3 4 5
出队一个元素
出队元素为1
队列长度为4
对头元素为:2
Program ended with exit code: 0
网友评论