【数据结构】队列

队列

队列是限制在两端进行数据插入或删除的线性表，其特点为“先入先出，后入后出”。

 允许进行入队的一端称为“队尾”，允许进行出兑的一端称为“队首”。

顺序队相关代码：

 sequeue.h

typedef int datatype;
#define N 128

typedef struct {
    datatype data[N];
    int front;
    int rear;
}sequeue;

sequeue * queue_create();　　　　　　　　　　//创建顺序队列　　返回值：队列结构体指针
int enqueue(sequeue *sq, datatype x);　　 //入队操作
datatype dequeue(sequeue *sq);　　　　　　 //出队操作　　返回值：出队数据的值
int queue_empty(sequeue *sq);　　　　　　  //判断队列是否为空队
int queue_full(sequeue *sq);   　　　　　　//判断队列是否为满队
int queue_clear(sequeue *sq);　　　　　　  //清空队列数据
sequeue * queue_free(sequeue *sq);　　　　//释放队列存储空间  返回值：NULL

sequeue.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sequeue.h"

sequeue * queue_create() {
    sequeue *sq;

    if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {
        printf("malloc failed\n");
        return NULL;
    }

    memset(sq->data, 0, sizeof(sq->data));
    sq->front = sq->rear = 0;
    return sq;
}

int enqueue(sequeue *sq, datatype x) {
    if (sq == NULL) {
        printf("sq is NULL\n");
        return -1;
    }

    if ((sq->rear + 1) % N == sq->front) {
        printf("sequeue is full\n");
        return -1;
    }

    sq->data[sq->rear] = x;
    sq->rear = (sq->rear + 1) % N;

    return  0;
}

datatype dequeue(sequeue *sq) {
    datatype ret;

    ret = sq->data[sq->front];

    sq->front = (sq->front + 1) % N;

    return ret;
}

int queue_empty(sequeue *sq) {
    if (sq == NULL) {
        printf("sq is NULL\n");
        return -1;
    }

    return (sq->front == sq->rear ? 1 : 0);
}

int queue_full(sequeue *sq) {
    if (sq == NULL) {
        printf("sq is NULL\n");
        return -1;
    }

    if ((sq->rear + 1) % N == sq->front) {
        return 1;
    }
    else {
        return 0;
    }
}

int queue_clear(sequeue *sq) {
    if (sq == NULL) {
        printf("sq is NULL\n");
        return -1;
    }

    sq->front = sq->rear = 0;

    return 0;
}

sequeue * queue_free(sequeue *sq) {
    if (sq == NULL) {
        printf("sq is NULL\n");
        return NULL;
    }

    free(sq);
    sq = NULL;

    return NULL;
}

链式队列相关代码：

linkqueue.h

typedef int datatype;

typedef struct node {　　  //对队列结构体内成员做提前定义
    datatype data;
    struct node *next;
}listnode , *linklist;

typedef struct {　　　　　　//队列数据结构
    linklist front;
    linklist rear;
}linkqueue;

linkqueue * queue_create();　　　　　　　　　　//创建链式队列　　返回值：队列数据结构指针
int enqueue(linkqueue *lq, datatype x);　　 //入队操作
datatype dequeue(linkqueue *lq);　　　　　　 //出队操作
int queue_empty(linkqueue *lq);            //判断队列是否为空
int queue_clear(linkqueue *lq);            //清除队列内容
linkqueue * queue_free(linkqueue *lq);     //释放队列所占内存

linkqueue.c

#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"

linkqueue * queue_create() {
    linkqueue *lq;

    if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
        printf("malloc linkqueue failed\n");
        return NULL;
    }

    lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
    if (lq->front == NULL) {
        printf("malloc node failed\n");
        return NULL;
    }
    lq->front->data = 0;
    lq->front->next = NULL;

    return lq;
}

int enqueue(linkqueue *lq, datatype x) {
    linklist p;

    if (lq == NULL) {
        printf("lq is NULL\n");
        return -1;
    }

    if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
        printf("malloc node failed\n");
        return -1;
    }
    p->data = x;
    p->next = NULL;

    lq->rear->next = p;
    lq->rear = p;

    return 0;
}

datatype dequeue(linkqueue *lq) {
    linklist p;

    if (lq == NULL) {
        printf("lq is NULL\n");
        return -1;
    }

    p = lq->front;
    lq->front = p->next;
    free(p);
    p = NULL;

    return (lq->front->data);
}

int queue_empty(linkqueue *lq) {
    if (lq == NULL) {
        printf("lq is NULL\n");
        return -1;
    }

    return (lq->front == lq->rear ? 1 : 0);
}

int queue_clear(linkqueue *lq) {
    linklist p;

    if (lq == NULL) {
        printf("lq is NULL\n");
        return -1;
    }

    while (lq->front->next) {
        p = lq->front;
        lq->front = p->next;
        printf("clear free:%d\n", p->data);
        free(p);
        p = NULL;
    }
    return 0;
}

linkqueue * queue_free(linkqueue *lq) {
    linklist p;

    if (lq == NULL) {
        printf("lq is NULL\n");
        return NULL;
    }

    while (lq->front) {
        p = lq->front;
        lq->front = p->next;
        printf("free:%d\n", p->data);
        free(p);
    }

    free(lq);
    lq = NULL;

    return NULL;
}