小言_互联网的博客

数据结构C语言——队列的实现（数组、链表）

2020-04-28 13:20 427人阅读  评论(0)

3 队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

3.1 队列的数组实现

  1. 顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针 head，它指向队头元素；另一个是队尾指针 tail，它指向下一个入队元素的存储位置。每次在队尾插入一个元素是， tail 增1；每次在队头删除一个元素时，head 增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当 head = tail 时，队列中没有任何元素，称为空队列。当 tail 增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

  1. 循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦 tail 指针增1或 head 指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算 tail %MaxSize和 head %MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

在循环队列中，当队列为空时，有 head = tail ，而当所有队列空间全占满时，也有 head = tail 。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时 head = tail ，而队列判满的条件时 head =（rear+1）%MaxSize。

下面将使用C语言数组实现循环队列

queue.h

#ifndef QUEUE_H__
#define QUEUE_H__

#define MAXSIZE 5


typedef int datatype;
typedef struct node_st queue;

struct node_st{
    datatype data[MAXSIZE];
    int head, tail;

};

queue *queue_create();

int queue_isempty(queue *);

int queue_enqueue(queue *, datatype *);

int queue_dequeue(queue *, datatype *);

void queue_travel(queue *);

int queue_clear(queue *);

void queue_destroy(queue *);

#endif

queue.c

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

#include "queue.h"


queue *queue_create(){
    queue *sq;
    sq = malloc(sizeof(*sq));
    if(sq == NULL){
        return NULL;
    }
    sq->head = 0;
    sq->tail = 0;

    return sq;
}

int queue_isempty(queue *sq){
    return (sq->head == sq->tail);
}

int queue_enqueue(queue *sq, datatype *data){
    if((sq->tail + 1) % MAXSIZE == sq->head){
        return -1;
    }
    sq->tail = (sq->tail + 1) % MAXSIZE;
    sq->data[sq->tail] = *data;

    return 0;
}

int queue_dequeue(queue *sq, datatype *data){
    if(queue_isempty(sq)){
        return -1;
    }
    sq->head = (sq->head + 1) % MAXSIZE;
    *data = sq->data[sq->head];

    return 0;
}

void queue_travel(queue *sq){
    if(queue_isempty(sq)){
        return ;
    }
    int i;
    for( i = (sq->head + 1) % MAXSIZE; i != sq->tail; i = (i + 1) % MAXSIZE){
        printf("%d ",sq->data[i]);
    }
    printf("%d ",sq->data[i]);
    printf("\n");

    return ;
}

int queue_clear(queue *sq){
    sq->head = sq->tail;
}

void queue_destroy(queue *sq){
    free(sq);
    sq = NULL;
    return ;
}

main.c

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

#include "queue.h"


int main(){

    queue *sq;
    datatype arr[] = {23,3,123,75}, tmp;
    sq = queue_create();
    if(sq == NULL){
        exit(-1);
    }
    int i, ret;
    for(int i = 0; i < sizeof(arr)/sizeof(*arr); i++){
        queue_enqueue(sq, &arr[i]);
    }

    queue_travel(sq);
#if 0
    tmp = 5643;
    ret = queue_enqueue(sq, &tmp);
    if(ret != 0){
        printf("enqueue failed!\n");
    }
    else{
        queue_travel(sq);
    }
#endif

    queue_dequeue(sq, &tmp);
    printf("DEQYEYE: %d\n", tmp);

    queue_travel(sq);
    queue_destroy(sq);

    return 0;
}

3.2 队列的链表实现

在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

本次将采用之前封装好的双向环链来实现队列：

llist.h

#ifndef LLIST_H__
#define LLIST_H__

#define LLIST_FORWARD   0x0
#define LLIST_BACKWARD  0x1

typedef void llist_op(const void *);
typedef int llist_cmp(const void *, const void *);

struct llist_node_st{
    //void *data;
    struct llist_node_st *prev;
    struct llist_node_st *next;
    char data[0];
};

typedef struct llist_head{
    int size;
    struct llist_node_st head;

    int (*insert)(struct llist_head *, const void *, unsigned char );
    void *(*find)(struct llist_head *, const void *, llist_cmp *);
    int (*delete)(struct llist_head *, const void *, llist_cmp *);
    int (*fetch)(struct llist_head *, const void *, llist_cmp *, void *);
    void (*travel)(struct llist_head *, llist_op *);

}LLIST;



LLIST *llist_creat(int size);

int llist_insert(LLIST *, const void *data, unsigned char mode);
void *llist_find(LLIST *, const void *key, llist_cmp *);
int llist_delete(LLIST *, const void *key, llist_cmp *);
int llist_fetch(LLIST *, const void *key, llist_cmp *, void *data);
void llist_travel(LLIST *, llist_op *);

void llist_destroy(LLIST *);


#endif

llist.c

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

#include "llist.h"

int llist_insert(LLIST *, const void *data, unsigned char mode);
void *llist_find(LLIST *, const void *key, llist_cmp *);
int llist_delete(LLIST *, const void *key, llist_cmp *);
int llist_fetch(LLIST *, const void *key, llist_cmp *, void *data);
void llist_travel(LLIST *, llist_op *);

LLIST *llist_creat(int size){
    LLIST *new;
    new = malloc(sizeof(*new));
    if(new == NULL){
        return NULL;
    }

    new->size = size;
    //new->head.data = NULL;
    new->head.prev = &new->head;
    new->head.next = &new->head;
    new->insert = llist_insert;
    new->find = llist_find;
    new->delete = llist_delete;
    new->fetch = llist_fetch;
    new->travel = llist_travel;

    return new;
}

int llist_insert(LLIST *ptr, const void *data, unsigned char mode){
    struct llist_node_st *newnode;
    
    newnode = malloc(sizeof(*newnode) + ptr->size);
    if(newnode == NULL){
        return -1;
    }

    //newnode->data = malloc(ptr->size);
    if(newnode->data == NULL){
        return -2;
    }
    memcpy(newnode->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        newnode->prev = &ptr->head;
        newnode->next = ptr->head.next;

    }
    else if(mode == LLIST_BACKWARD){
        newnode->prev = ptr->head.prev;
        newnode->next = &ptr->head;
    }
    else{
        return -3;
    }

    newnode->next->prev = newnode;
    newnode->prev->next = newnode;
    
    return 0;
}

static struct llist_node_st *find_(LLIST *ptr, const void *key, llist_cmp *cmp){
    struct llist_node_st *cur = NULL;

    for(cur = ptr->head.next; cur != &ptr->head; cur = cur->next){
        if(cmp(key, cur->data) == 0)
            break;
    }

    return cur;
}


void *llist_find(LLIST *ptr, const void *key, llist_cmp *cmp){
    
    struct llist_node_st *node;

    node = find_(ptr, key, cmp);

    if(node == &ptr->head){
        return NULL;
    }

    return node->data;
}

int llist_delete(LLIST *ptr, const void *key, llist_cmp* cmp){
    struct llist_node_st *node;
    node = find_(ptr, key, cmp);
    if(node == &ptr->head){
        return -1;
    }

    node->prev->next = node->next;
    node->next->prev = node->prev;

    //free(node->data);
    free(node);
    return 0;

}

int llist_fetch(LLIST *ptr, const void *key, llist_cmp *cmp, void *data){
    struct llist_node_st *node;
    node = find_(ptr, key, cmp);
    if(node == &ptr->head){
        return -1;
    }

    node->prev->next = node->next;
    node->next->prev = node->prev;

    if(node->data != NULL){
        //memset(data, 0, ptr->size);
        memcpy(data, node->data, ptr->size);
        
    }

    //free(node->data);
    free(node);
    return 0;    
}

void llist_travel(LLIST *ptr, llist_op *op){
    struct llist_node_st *cur, *next;

    for(cur = ptr->head.next; cur != &ptr->head; cur = cur->next){
        op(cur->data);
    }

}

void llist_destroy(LLIST *ptr){
    struct llist_node_st *cur, *next;

    for(cur = ptr->head.next; cur != &ptr->head; cur = next){
        next = cur->next;
        //free(cur->data);
        free(cur);
    }

    free(ptr);
    ptr = NULL;

}

queue.h

#ifndef QUEUE_H__
#define QUEUE_H__

#include "llist.h"

#define MAXSIZE 5


typedef int datatype;
typedef LLIST queue;



queue *queue_create(int size);

int queue_isempty(queue *);

int queue_enqueue(queue *, const void *);

int queue_dequeue(queue *, void *);

void queue_travel(queue *);

int queue_clear(queue *);

void queue_destroy(queue *);

#endif

queue.c

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

#include "queue.h"


queue *queue_create(int size){
    return llist_creat(size);
}

int queue_isempty(queue *ptr){
    return 0;
};

int queue_enqueue(queue *ptr, const void *data){

    return llist_insert(ptr, data, LLIST_BACKWARD);
}

static int always_macth(const void *a, const void *b){
    return 0;
}

int queue_dequeue(queue *ptr, void *data){
    return llist_fetch(ptr, (void *)0, always_macth, data);
}

void queue_travel(queue *);

int queue_clear(queue *);

void queue_destroy(queue *ptr){
    llist_destroy(ptr);
}

main.c

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

#include "queue.h"

#define NAMESIZE    32

typedef struct score_st SCORE;

struct score_st{
      
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
           
};

void print_s(const void *record){
    const SCORE *r = record;
    printf("%d %s %d %d\n", r->id, r->name, r->math, r->chinese);
}

int main(){

    queue *q = queue_create(sizeof(SCORE));

    SCORE tmp;
    int ret;


    if(q == NULL){
        exit(-1);
    }


    for(int i = 0; i < 6; i++){
        tmp.id = i;
        snprintf(tmp.name, NAMESIZE, "stu%d", i);
        tmp.math = rand() % 100;
        tmp.chinese = rand() % 100;

        ret = queue_enqueue(q, &tmp);        
        if(ret != 0){
            exit(-1);
        }
    }

    while(1){
        ret = queue_dequeue(q, &tmp);

        if(ret != 0){
            break;
        }
        print_s(&tmp);
    }


    return 0;
}

转载：https://blog.csdn.net/baidu_39049318/article/details/105809147
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场