queue

queue是一种先进先出的数据结构。以下由简入繁引入queue。

queue的操作主要有：入队，出队，空满判断等。

1. 数组实现简单队列

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

#define MAX 10
int arr[MAX];
int head = 0;
int tail = 0;
int counter = 0;

void enqueueint value)
{
    arr[tail ++] = value;
}

int dequeuevoid)
{
    return arr[head ++];
}

bool is_emptyvoid)
{
    return head == tail;
}

bool is_fullvoid)
{
    return tail == MAX;
}

int mainint argc, char *argv[])
{
    char ch;

    whilech = getchar)) != '
') {
        if ! is_full)) {
            enqueuech);
        }
    }
    while! is_empty)) {
        putchardequeue));
    }

    return 0;
}

2. 数组实现循环队列

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

#define MAX 10
int arr[MAX];
int head = 0;
int tail = 0;
int counter = 0;

void enqueueint value)
{
    counter ++;
    arr[tail] = value;
    tail = tail + 1) % MAX;
}

int dequeuevoid)
{
    int data;
    counter --;
    data = arr[head];
    head = head + 1) % MAX;
    return data;
}

bool is_emptyvoid)
{
    return counter == 0;
}

bool is_fullvoid)
{
    return counter == MAX;
}

int mainint argc, char *argv[])
{
    char ch;

    whilech = getchar)) != '
') {
        if ! is_full)) {
            enqueuech);
        }
    }
    while! is_empty)) {
        putchardequeue));
    }

    return 0;
}

3. 链表实现队列

// queue.h
#ifndef _QUEUE_H_
#define _QUEUE_H_

#include <stdbool.h>

struct node {
    void *data;
    struct node *next;
};

typedef struct {
    struct node *head;
    struct node *tail;
} Queue;

extern void queue_initQueue *queue);
extern void queue_destroyQueue *queue,
        void *destroy)void *data));

extern void queue_enqueueQueue *queue, void *data);
extern void *queue_dequeueQueue *queue);

extern bool queue_is_fullQueue *queue);
extern bool queue_is_emptyQueue *queue);

#endif    //_QUEUE_H_

#include <stdlib.h>
#include <assert.h>

#include "queue.h"

void queue_initQueue *queue)
{
    queue->head = NULL;
    queue->tail = NULL:    
}
void queue_destroyQueue *queue,
        void *destroy)void *data))
{
    while! queue_is_emptyqueue)) {
        if destroy) {
            destroyqueue_dequeuequeue));
        } else {
            queue_dequeuequeue);
        }
    }
}

static struct node * make_nodevoid *data)
{
    struct node *n;

    n = mallocsizeofstruct node));
    assertn);
    n->data = data;
    n->next = NULL;

    return n;
}

void queue_enqueueQueue *queue, void *data)
{
    struct node *n;

    n = make_nodedata);

    if queue->head == NULL) {
        queue->head = n;
        queue->tail = n;
    } else {
        queue->tail->next = n;
        queue->tail = n;
    }
}

void *queue_dequeueQueue *queue)
{
    void *data;
    struct node *n;

    n = queue->head;
    data = n->data;
    queue->head = n->next;
    freen);
    return data;
}

bool queue_is_fullQueue *queue)
{
    return false;
}
bool queue_is_emptyQueue *queue)
{
    return queue->head == NULL;
}

 参考：

1. libubox-runqueue

2. 数据结构学习之队列