队列queue的C实现

时间:2022-06-02 00:20:14
头文件——————————————————————————————
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdlib.h>
#define Element int
struct node
{
     Element data;
     struct node *next;
};
typedef struct node *PtrToNode;
typedef struct _Queue
{
     PtrToNode head;
     PtrToNode rear;
} *Queue;
//头进尾出
int IsEmpty(Queue q);
Queue CreateQueue();
void DestroyQueue(Queue q);
void MakeEmpty(Queue q);
void Enqueue(Element x, Queue q);
Element Front(Queue q);
Element Rear(Queue q);
void Dequeue(Queue q);
#endif
源文件————————————————————————————
#include <iostream>
#include "./Queue.h"

int IsEmpty(Queue q)
{
     return q->head == q->rear && q->head == NULL;
}
Queue CreateQueue()
{
     Queue q = (Queue)malloc(sizeof(struct _Queue));
     if(NULL == q) return NULL;
     q->head = q->rear = NULL;
     return q;
}
void DestroyQueue(Queue q)
{
     MakeEmpty(q);
     free(q);
}
void MakeEmpty(Queue q)
{
     while(!IsEmpty(q))
          Dequeue(q);
}
void Enqueue(Element x, Queue q)//头进尾出
{
     if(NULL == q) return ;
     PtrToNode p = (PtrToNode)malloc(sizeof(struct node));
     if(NULL == p) return ;
     p->data = x;
     if(IsEmpty(q))
          q->rear = p;
     p->next = q->head;
     q->head = p;
}
Element Front(Queue q)
{
     return q->head->data;
}
Element Rear(Queue q)
{
     return q->rear->data;
}
void Dequeue(Queue q)//头进尾出
{
     if(NULL == q || IsEmpty(q)) return ;
     PtrToNode prev = q->head;
     while(NULL != prev && prev != q->rear && prev->next != q->rear)
          prev = prev->next;
     if(NULL == prev) return ;
     if(prev == q->rear)
     {
          q->head = q->rear = NULL;
          free(prev);
     }
     PtrToNode tmp = prev->next;
     prev->next = NULL;
     q->rear = prev;
     free(tmp);
     /*if(q->head == q->rear)
     {
          PtrToNode tmp = q->head;
          free(tmp);
          q->head = q->rear = NULL;
     }
     PtrToNode prev = q->head;
     while(NULL != prev && prev->next->data != q->rear->data)
          prev = prev->next;
     PtrToNode tmp = prev->next;
     prev->next = NULL;
     q->rear = prev;
     free(tmp);
     */
}