数据结构7——链式队列

前言：
本专栏属于数据结构相关内容，附带一些代码加深对一些内容的理解，为方便读者观看，本专栏内的所有文章会同时附带C语言和Python对应的代码，（可自行通过目录跳转到对应的部分）辅助不同主修语言的读者去更好的理解对应的内容，若是代码0基础的读者，可先去博主其他专栏学习一下基础的语法及知识点：

魔法天才的跳转链接：

C语言：C基础_Gu_shiwww的博客-CSDN博客
Python语言：python1_Gu_shiwww的博客-CSDN博客
其他数据结构内容可见：数据结构_Gu_shiwww的博客-CSDN博客

1 链式队列

        队列在尾部添加元素，在头部删除元素。使用有头单向链表实现队列。那就让链表的头作为队列的头，因为链表头部容易执行删除操作，链表的尾部只能作为队列的尾部，执行插入操作。

        但链表尾部插入操作有一个问题：每次都要遍历整个链表找到终端结点，才能执行插入操作。为了减少遍历，要再维护一个尾指针指向链表的尾部。因此，使用单向链表实现一个队列，链表需要两个指针——头指针和尾指针。头指针指向链表的头部，用于出列。尾指针指向链表尾部，用于入列。

链式栈：无头单向链表，头为栈顶，对无头单向链表进行头插和头删。

链式队列：有头单向链表，头结点为队头，终端结点为队尾，对有头单向链表进行头删和尾插。

1.2 图示

        队列的链式存储结构，其实就是线性表的单链表，只不过它是操作受限的线性表。它只能尾进头出而已，将其简称为链式队列。

        为了操作上的方便，我们将队头指针指向链式队列的头结点，而队尾指针指向终端结点，如下图所示。

入队：

出队：

2 编程实现链式队列

C语言实现链式队列

#include <stdio.h>
#include <stdlib.h>

typedef int datatype;
//链表节点结构体
typedef struct node_t
{
    datatype data;
    struct node_t *next;
} link_node_t, *link_node_p;

//队列结构体：包含头指针和尾指针
typedef struct
{
    link_node_p front;
    link_node_p rear;
} linkqueue_t, *linkqueue_p;

//创建一个空链式队列，用有头链表
linkqueue_p createEmptyLinkQueue()
{
    //1.开辟队列结构体空间
    linkqueue_p p = (linkqueue_p)malloc(sizeof(linkqueue_t));
    if (NULL == p)
    {
        perror("p malloc err");
        return NULL;
    }
    //2.初始化队列结构体空间
    p->front = p->rear = (link_node_p)malloc(sizeof(link_node_t));
    if (NULL == p->front)
    {
        perror("p->front malloc err");
        return NULL;
    }
    //3.对头节点初始化
    p->front->next = NULL;

    return p;
}

//入列 data代表入列的数据
int inLinkQueue(linkqueue_p p, datatype data)
{
    // 新建节点，初始化新节点
    link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));
    if (NULL == pnew)
    {
        perror("pnew err");
        return -1;
    }
    pnew->data = data;
    pnew->next = NULL;
    // 将尾指针所指节点连接新节点
    p->rear->next = pnew;
    // 移动尾指针到新节点
    p->rear = pnew;

    return 0;
}

//判断队列是否为空
int isEmptyLinkQueue(linkqueue_p p)
{
    return p->front == p->rear;
}

//出列
datatype outLinkQueue(linkqueue_p p)
{
    // 1. 判空：p->rear == p->front;
    if (isEmptyLinkQueue(p))
    {
        perror("out err");
        return -1;
    }
    // 2. 设指针pdel指向要释放节点(也就是此时头节点)
    link_node_p pdel = p->front;
    // 3. 将头指针向后移动一个单位
    p->front = p->front->next;
    // 4. 释放要删除节点
    free(pdel);
    // 5. 将此时头指针指所指节点的数据出队
    return p->front->data;
}

//求队列长度的函数
int lengthLinkQueue(linkqueue_p p)
{
    int len = 0;
    link_node_p t = p->front;
    while (t->next != NULL)
    {
        t = t->next;
        len++;
    }
    return len;
}

int main(int argc, char const *argv[])
{
    linkqueue_p p = createEmptyLinkQueue();
    for (int i = 1; i < 5; i++)
        inLinkQueue(p, i);
    printf("len = %d\n", lengthLinkQueue(p));
    while (!isEmptyLinkQueue(p))
        printf("%d\n", outLinkQueue(p)); //1 2 3 4 先进先出

    return 0;
}

Python实现链式队列

# 1、定义链式队列节点
class Node:
    def __init__(self, value):
        self.data = value  # 数据域
        self.next = None  # 指针域


# 定义队列函数
class LinkQueue:
    # 队列初始化
    def __init__(self):
        self.front = Node(None)  # 相当于队列的头指针
        self.rear = self.front  # 相当于队列的尾指针

    # 2、判断队列是否为空
    def is_empty(self):
        return self.front.next is None

    # 3、元素入队
    def InLinkQueue(self, data):
        new_node = Node(data)
        # 将新节点连接到队尾
        self.rear.next = new_node
        # 队尾指针指向新的队尾节点
        self.rear = new_node

    # 4、队列元素出队
    def OutLinkQueue(self):
        if self.is_empty():
            # print("OutLinkQueue error")
            return "error"
        '''
          # 方法一：头节点不动，剩最后一个节点时需将尾结点回到队头，以防下一次入队且正常出队
        del_queue = self.front.next
        if self.front.next == self.rear:
            self.rear = self.front
        # 跨越删除
        self.front.next = del_queue.next
        return del_queue.data
        '''
        # 方法二：
        data = self.front.next.data
        self.front = self.front.next
        return data

    # 5、获取队首元素
    def Get_top(self):
        if self.is_empty():
            return "Get_top error"
        return self.front.next.data

    # 6、遍历队列
    def display(self):
        if self.is_empty():
            print("display error")
            return
        current = self.front
        while current.next:
            current = current.next
            print(current.data)

    # 7、清空队列
    def ClearLinkQueue(self):
        while not self.is_empty():
            self.OutLinkQueue()

    # 8、返回队列长度
    def LengthLinkQueue(self):
        current = self.front
        length = 0
        while current.next:
            current = current.next
            length += 1
        return length


if __name__ == '__main__':
    link_queue = LinkQueue()
    for i in range(6):
        link_queue.InLinkQueue(i)

    print("queue_topdata=",link_queue.Get_top())
    print("queue_len=",link_queue.LengthLinkQueue())

    for _ in range(6):
        print("queue_data", link_queue.OutLinkQueue())

3 拓展

如何用两个栈实现一个队列的功能？简述思想