Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

队列（循环顺序队列、链队列、循环链表队列）_循环链队

作者：Guff_9hys | 2024-07-23 00:03:05

踩

循环链队

一、循环顺序队列

1.1 假溢出现象

1.2 循环顺序队列

循环顺序队列：将顺序队列的数组看成一个环状空间，即规定最后一个单元的后继为第一个单元。

虽然不存在物理的循环操作，但是可以通过软件方法实现 —— 使用求模操作。

求模操作：（4+1）mod 5 = 0

1.3 算法实现

1.3.1 初始化队列


void InitQueue(QueuePtr Q) {
    Q->front = Q->rear = 0;
}

1.3.2 入队操作


bool EnterQueue(QueuePtr Q, QueueElementType x) {
    if (IsFull(Q)) return false;
 
    /* 生成新结点 */
    Q->element[Q->rear] = x;
    
    /* 重新设置队尾 */
    Q->rear = (Q->rear + 1) % MAXSIZE;
 
    return true;
}

1.3.3 出队操作


bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;
 
    /* 将出队的元素存放到x所指向的变量中 */
    *x = Q->element[Q->front];
    /* 重新设置队头 */
    Q->front = (Q->front + 1) % MAXSIZE;
 
    return true;
}

1.3.4 读取队头元素


bool GetHead(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;
    
    /* 将队头元素存放到x所指向的变量中 */
    *x = Q->element[Q->front];
    return true;
}

1.3.5 判空操作


bool IsEmpty(QueuePtr Q) {
    /*
     * if (Q->front == Q->rear)
     *     return true;
     * else
     *     return false;
     */
    return Q->front == Q->rear;
}

1.3.6 判满操作


bool IsFull(QueuePtr Q) {
    /*
     * if ((Q->rear + 1) % MAXSIZE == Q->front)
     *     return true;
     * else
     *     return false;
     */
    return (Q->rear + 1) % MAXSIZE == Q->front;
}

二、链队列

链队列：用链表表示的队列。


/* 定义结点类型 */
typedef struct Node {
    QueueElementType data;     /* 数据域 */
    struct Node *next;         /* 指针域 */
} LinkQueueNode, *LinkQueueNodePtr;
 
/* 定义链表类型 */
typedef struct {
    LinkQueueNode *front;      /* 头指针 */
    LinkQueueNode *rear;       /* 尾指针 */
} LinkQueue, Queue, *QueuePtr;

2.1 初始化队列


void InitQueue(QueuePtr Q) {
    /* 生成头结点，同时设置头指针 */
    Q->front = (LinkQueueNodePtr)malloc(sizeof(LinkQueueNode));
    Q->front->next = NULL;
    /* 设置尾指针 */
    Q->rear = Q->front;
}

2.2 入队操作


bool EnterQueue(QueuePtr Q, QueueElementType x) {
    /* 生成新结点 */
    LinkQueueNode * NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    NewNode->data = x;
    NewNode->next = NULL;
 
    if (NewNode == NULL)
        return false;
 
    /* 通过尾插法实现入队 */
    Q->rear->next = NewNode;
    Q->rear = NewNode;
    return true;
}

2.3 出队操作

情况1：队列中有不止一个元素。

情况2：队列中只有一个元素。


bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;
 
    /* 将队列Q的队头元素出队 */
    LinkQueueNodePtr p = Q->front->next;
    Q->front->next = p->next;
 
    /* 如果队列中只有一个元素p，则p出队后成为空队 */
    if (Q->rear == p)
        Q->rear = Q->front; /* 重新设置尾指针 */
    
    /* 将出队的元素存放到x所指向的变量中 */
    *x = p->data;
    free(p);
 
    return true;
}

2.4 读取队头元素


bool GetHead(QueuePtr Q, int *x) {
    if (IsEmpty(Q)) return false;
    
    /* 将队头元素存放到x所指向的变量中 */
    *x = Q->front->data;
    return true;
}

2.5 判空操作


bool IsEmpty(QueuePtr Q) {
    /*
     * if (Q->front == Q->rear)
     *     return true;
     * else
     *     return false;
     */
    return Q->front == Q->rear;
}

2.6 销毁操作


void ClearQueue(QueuePtr Q) {
    LinkQueueNodePtr p = Q->front, q;
    
    /* p在前，q在后 */
    while (p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
}

三、循环链表队列

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点。


/* 定义结点和链表的类型 */
typedef struct _QueueNode {
    ElemType data;
    struct _QueueNode *next;
} LinkQueueNode, *LinkQueue;
 
/* 初始化队列 */
bool init_queue(LinkQueue *LQ) {
	*LQ = (LinkQueue)malloc(sizeof(LinkQueueNode));
	if (*LQ == NULL) return false;
 
    (*LQ)->next = (*LQ);
    return true;
}
 
/* 入队操作 */
bool enter_queue(LinkQueue *LQ, ElemType x) {
    LinkQueue p = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if (p == NULL) return false;
    p->data = x;
 
    p->next = (*LQ)->next;
    (*LQ)->next = p;
    (*LQ) = p;
    
    return true;
}
 
/* 出队操作 */
bool leave_queue(LinkQueue *LQ, ElemType *x) {
    LinkQueueNode * head = (*LQ)->next, p;
    if ((*LQ) == head) return false;
 
    p = head->next;
    head->next = p->next;
    
    if (p->next == head)
        (*LQ) = head;
    
    *x = p->data;
    free(p);
 
    return true;
}

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】