链式队列的定义，ios基础知识篇！

数据结构与算法-链式队列

链式队列的定义

链式队列是用链表来实现的队列，不存在队满的情况。链式队列也包里队列的特点。所以我们实现链式队列的 尾部进，头部出。

链式队列的结构

我们实现链式队列，首先要定一个链式队列的结构。我们要：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

关注下面的标签，发现更多相似文章