队列实现(循环队列、链式队列)

叁歲伎倆 2021-09-21 04:46 549阅读 0赞

队列(Queue)是一种类似栈的数据结构, 栈是"后进先出", 而队列是"先进先出"; 队列通常模拟进出一致的数据处理场景, 例如消息推送处理, 商城中的购物处理等.

**循环队列预备知识:**

*  循环队列无法区分队空或队满, 解决办法: rear+1 == front mod 数组长度
 *  队空条件: front==rear (初始值: front = rear)
 *  判断队满: (rear+1)%MAXQSIZE == front
 *  队列长度: (rear - front + MAXQSIZE) % MAXSIZE
 *  最大存储 MAX\_SIZE - 1 个元素

**链式队列预备知识**

*  一般使用带头链表实现, 初始化时front和rear指针指向此元素
 *  判断队列是否为空: front==rear
 *  第一个队列元素: front.next

### 循环队列(数组) ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -1
    #define MAX_SIZE 5
    
    
    typedef int ElemType;
    typedef int status;
    
    typedef struct { 
        ElemType *base;
        int front;
        int rear;
    } SqQueue;
    
    status InitQueue(SqQueue &Q) { 
        if (!Q.base) exit(OVERFLOW);
        Q.base = (ElemType *) malloc(sizeof(ElemType) * MAX_SIZE);
        Q.rear = Q.front = 0;
        return OK;
    }
    
    status EnQueue(SqQueue &Q, ElemType e) { 
        if (!Q.base) return ERROR;
        if ((Q.rear + 1) % MAX_SIZE == Q.front)exit(OVERFLOW);
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear+1) % MAX_SIZE;
        return OK;
    }
    
    
    status DeQueue(SqQueue &Q, ElemType &e) { 
        if (!Q.base) return ERROR;
        e = Q.base[Q.front];
        Q.front = (Q.front+1) % MAX_SIZE;
        return OK;
    }
    
    status isEmpty(SqQueue Q) { 
        if(Q.rear == Q.front) return TRUE;
        return FALSE;
    }
    
    int main() { 
        SqQueue Q;
        InitQueue(Q);
        EnQueue(Q,1);
        EnQueue(Q,2);
        EnQueue(Q,3);
        EnQueue(Q,4);
    
        ElemType e;
        DeQueue(Q,e);
        EnQueue(Q,5);
        while(!isEmpty(Q)){ 
            DeQueue(Q,e);
            printf("%d\n",e);
        }
        return 0;
    }

### 链式队列 ###

typedef struct QNode { 
        ElemType data;
        struct QNode *next;
    } QNode, *QNodePtr;
    
    typedef struct { 
        QNodePtr front;
        QNodePtr rear;
    } *LinkQueue;
    
    void InitLinkQueue(LinkQueue &Q) { 
        Q = (LinkQueue)malloc(sizeof(LinkQueue));
        QNode *node = new QNode;//头结点
        node->data = -1;
        node->next = NULL;
        Q->front = node;
        Q->rear = node;
    }
    
    status EnLinkQueue(LinkQueue &Q, ElemType e) { 
        if (!Q) exit(OVERFLOW);
        QNode *p = new QNode;
        p->data = e;
        p->next = NULL;
    
        Q->rear->next = p;
        Q->rear = p;
        return OK;
    }
    
    status DeLinkQueue(LinkQueue &Q, ElemType &e) { 
        if (!Q)return ERROR;
        if (Q->rear == Q->front) return ERROR;
    
        QNodePtr de_node = Q->front->next;
        e = de_node->data;
        if (de_node == Q->rear) { 
            Q->rear = Q->front;
        } else { 
            Q->front->next = de_node->next;
        }
        free(de_node);
        return OK;
    }
    
    status DestroyLinkQueue(LinkQueue &Q){ 
        if(!Q)return ERROR;
        if(Q->front==Q->rear)return OK;//无内容
        QNodePtr p;
        while(Q->front != Q->rear){ 
            p = Q->front->next;
            Q->front->next = p->next;
            free(p);
        }
        Q->rear = Q->front;
        return OK;
    }
    
    status isEmpty(LinkQueue Q) { 
        if (Q->front == Q->rear) return TRUE;
        return FALSE;
    }
    
    int length(LinkQueue Q){ 
        QNodePtr p = Q->front;
        int n=0;
    
        while(p != Q->rear){ 
            n++;
            p = p->next;
        }
        return n;
    }
    
    int main(){ 
        LinkQueue Q;
        InitLinkQueue(Q);
        EnLinkQueue(Q,1);
        EnLinkQueue(Q,2);
        EnLinkQueue(Q,3);
        EnLinkQueue(Q,4);
    
        printf("len: %d\n",length(Q));
    
        ElemType e;
        while(!isEmpty(Q)){ 
            DeLinkQueue(Q, e);
            printf("%d\n",e);
        }
        return 0;
    }