C语言详解链式队列与循环队列的实现

// 初始化队列 
void QueueInit(Queue* q);
​
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListnode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;
​
// 队列的结构 
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

void QueueInit(Queue* q)
{
    assert(q);
    q->_front = NULL;
    q->_rear = NULL;
}

void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* cur = q->_front;
    while (cur != NULL)
    {
        QNode* next = cur->_next;
        free(cur);
        cur = next;
    }
    q->_front = q->_rear = NULL;
}

bool QueueEmpty(Queue* q)
{
    assert(q);
    //if (q->_front == NULL)
    //{
    //  return 1;
    //}
    //else
    //{
    //  return 0;
    //}
    return q->_front == NULL;
}

void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        exit(-1);
    }
    newnode->_data = data;
    newnode->_next = NULL;
    if (q->_front == NULL)
    {
        q->_front = q->_rear = newnode;
    }
    else
    {
        q->_rear->_next = newnode;
        q->_rear = newnode;
    }
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    QNode* next = q->_front->_next;
    free(q->_front);
    q->_front = next;
    if (q->_front == NULL)
    {
        q->_rear = NULL;
    }
}

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_front->_data;
}

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_rear->_data;
}

int QueueSize(Queue* q)
{
    assert(q);
    int size = 0;
    QNode* cur = q->_front;
    while (cur) 
    {
        size++;
        cur = cur->_next;
    }
    return size;
}

typedef struct {
    int *a;
    int front;
    int tail;
    int k;
} MyCircularQueue;
​
//提前声明判空判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->a=(int*)malloc(sizeof(int)*(k+1));
    cq->front=cq->tail=0;
    cq->k=k;
    return cq;
}
//循环队列入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)){
        return false;
    }
    obj->a[obj->tail]=value;
    obj->tail++;
    obj->tail%=(obj->k+1);
​
    return true;
}
//循环队列出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
​
}
//循环队列取队头
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->a[obj->front];
}
//循环队列取队尾
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    int i=(obj->tail+obj->k)%(obj->k+1);
    return obj->a[i];
}
//循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
//循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}