c语言实现循环队列和链式队列

Bertha 。 2022-06-09 02:08 263阅读 0赞

**队列与栈不同，队列必须是先进先出(first in first out)，而栈是后进**先出的(last in first out)  
**链式队列与单链表的区别是，链式队列不能随意的增加，删除，以及读取队列中间的某一个数据。**

--------------------

## 循环队列 ##

采用牺牲一个存储单元的方法。  
front = rear表示队列空  
(rear + 1) % MaxSize = front表示队列满  
例如：  
rear = 4 front =0 5的位置为空的储存单元，这个时候队列满

typedef struct{
        ElemType data[MaxSize];
        int front, rear;
    }SqQueue;
    
    void InitQueue(SqQueue * Q);
    int QueueEmpty(SqQueue Q);
    int EnQueue(SqQueue * Q, ElemType e);
    int DeQueue(SqQueue * Q, ElemType * e);
    int GetHead(SqQueue * Q, ElemType * e);
    int ElemNumber(SqQueue Q);

具体函数实现：

void InitQueue(SqQueue * Q){
        Q->front = Q->rear = 0;
    }
    
    int QueueEmpty(SqQueue Q){
        if(Q.front == Q.rear) return 1;
        return 0;
    }
    
    int EnQueue(SqQueue * Q, ElemType e){
        if((Q->rear + 1) % MaxSize == Q->front){
            printf("queue is full!");
            return 0;}//队列满，牺牲一个存储单元
        Q->data[Q->rear] = e;
        Q->rear = (Q->rear+1) % MaxSize;
        return 1;
    }
    
    int DeQueue(SqQueue * Q, ElemType * e){
        if(QueueEmpty(* Q)) return 0;
        * e = Q->data[Q->front];
        Q->front = (Q->front + 1) % MaxSize;
        return 1;
    }
    
    int ElemNumber(SqQueue Q){
        return ((Q.rear + MaxSize - Q.front) % MaxSize);
    }

--------------------

## 链式队列 ##

适合于数据元素变动比较大的情形，而且不会存在队列满产生溢出的问题。  
带头结点的链式队列比较简单，插入和删除比较简单  
初始，front rear指向头结点。

typedef struct LinkNode{
        ElemType data;
        struct LinkNode * next;
    }LinkNode;
    typedef struct{
        LinkNode * front, * rear;
    }LinkQueue;
    
    void InitListQueue(LinkQueue * Q);
    int ListQueueEmpty(LinkQueue Q);
    int EnListQueue(LinkQueue * Q, ElemType e);
    int DeListQueue(LinkQueue * Q, ElemType * e);

*  插入的时候，将新建的节点插入到头结点的后一个节点，使用rear指向这个结点，这个结点的next为空
 *  删除的时候，由于是FIFO，刚刚进来的元素插入到了front的后面，因此删除时候，删除front的next节点。特别需要注意的是，当只有一个节点的时候，删除了队列为空，需要将rear = front

void InitListQueue(LinkQueue * Q){
        Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
        Q->front->next = NULL;
    }
    
    int ListQueueEmpty(LinkQueue Q){
        if(Q.front == Q.rear) return 1;
        return 0;
    }
    
    int EnListQueue(LinkQueue * Q, ElemType e){
        LinkNode * p = (LinkNode *)malloc(sizeof(LinkNode));
        p->data = e;
        p->next = NULL;
        Q->rear->next = p;
        Q->rear = p;
        return 1;
    }
    
    int DeListQueue(LinkQueue * Q, ElemType * e){
        if(Q->front == Q->rear) return 0;
        LinkNode * p = Q->front->next;
        * e = p->data;
        Q->front->next = p->next;
        if(p == Q->rear) Q->front = Q->rear;//如果队列中只有一个节点，那么变为空
        free(p);
        return 1;
    }

测试队列的简单主程序

int main(int argc, const char * argv[]) {
        SqQueue Q;
        InitQueue(& Q);
        printf("front:%d,rear:%d\n", Q.front, Q.rear);
        printf("Empty:%d\n",QueueEmpty(Q));
        EnQueue(& Q, 1);
        printf("front:%d,rear:%d\n", Q.front, Q.rear);
        printf("Empty:%d\n",QueueEmpty(Q));
        EnQueue(& Q, 2);
        EnQueue(& Q, 3);
        EnQueue(& Q, 4);
        printf("front:%d,rear:%d\n", Q.front, Q.rear);
        printf("Empty:%d\n",QueueEmpty(Q));
        printf("ElemNumber:%d\n",ElemNumber(Q));
        int e;
        DeQueue(& Q, & e);
        printf("DeNumber:%d\n",e);
        printf("ElemNumber:%d\n",ElemNumber(Q));
        printf("front:%d,rear:%d\n", Q.front, Q.rear);
        EnQueue(& Q, 5);
        printf("ElemNumber:%d\n",ElemNumber(Q));
        printf("front:%d,rear:%d\n", Q.front, Q.rear);
        return 0;
    }