Hàng đợi cơ bản

#ifndef QUEUE_H
#define QUEUE_H

#include <stddef.h>

typedef struct QNode {
    int           data;
    struct QNode *next;
} QNode;

/* Bất biến:
     1. front == NULL  khi và chỉ khi  size == 0
     2. rear == NULL   khi và chỉ khi  front == NULL
     3. rear != NULL   thì  rear->next == NULL
     4. size == số nút đi được từ front theo next               */
typedef struct {
    QNode *front;      /* nút sẽ được lấy ra tiếp theo */
    QNode *rear;       /* nút vừa được thêm vào */
    size_t size;
} Queue;

void   queue_khoi_tao(Queue *q);
void   queue_huy(Queue *q);
int    queue_rong(const Queue *q);
size_t queue_so_phan_tu(const Queue *q);
int    queue_enqueue(Queue *q, int v);
int    queue_dequeue(Queue *q, int *out);
int    queue_xem_dau(const Queue *q, int *out);

#endif

#include <stdlib.h>

#include "queue.h"

void queue_khoi_tao(Queue *q)
{
    q->front = NULL;
    q->rear  = NULL;
    q->size  = 0;
}

int queue_rong(const Queue *q)
{
    return q->front == NULL;
}

size_t queue_so_phan_tu(const Queue *q)
{
    return q->size;
}

/* Thêm vào ĐUÔI. O(1). Trả về 0 nếu ổn, -1 nếu hết bộ nhớ. */
int queue_enqueue(Queue *q, int v)
{
    QNode *n = malloc(sizeof *n);

    if (n == NULL) return -1;

    n->data = v;
    n->next = NULL;

    if (q->rear != NULL) q->rear->next = n;      /* nối vào sau nút cuối */
    else                 q->front      = n;      /* hàng đợi đang rỗng */

    q->rear = n;
    ++q->size;

    return 0;
}

/* Lấy ở ĐẦU. O(1). Trả về 0 nếu ổn, -1 nếu rỗng. */
int queue_dequeue(Queue *q, int *out)
{
    if (q->front == NULL) return -1;

    QNode *n = q->front;

    if (out != NULL) *out = n->data;

    q->front = n->next;

    if (q->front == NULL) q->rear = NULL;        /* vừa lấy nút cuối cùng */

    free(n);
    --q->size;

    return 0;
}

int queue_xem_dau(const Queue *q, int *out)
{
    if (q->front == NULL) return -1;

    if (out != NULL) *out = q->front->data;

    return 0;
}

void queue_huy(Queue *q)
{
    while (queue_dequeue(q, NULL) == 0) { }
}

#include <stdio.h>

#include "queue.h"

int main(void)
{
    Queue q;
    int   v;

    queue_khoi_tao(&q);

    printf("dequeue tren rong: %d\n", queue_dequeue(&q, &v));

    /* Trường hợp biên: thêm một, lấy một, thêm một */
    queue_enqueue(&q, 1);
    queue_dequeue(&q, &v);
    printf("them 1 roi lay ra: %d, size = %zu\n", v, queue_so_phan_tu(&q));

    queue_enqueue(&q, 2);      /* đây là chỗ rear treo nếu quên đặt NULL */
    queue_dequeue(&q, &v);
    printf("them 2 roi lay ra: %d\n", v);

    for (int i = 1; i <= 5; ++i)
        if (queue_enqueue(&q, i * 10) != 0) { queue_huy(&q); return 1; }

    queue_xem_dau(&q, &v);
    printf("dau hang         : %d\n", v);
    printf("so phan tu       : %zu\n", queue_so_phan_tu(&q));

    printf("lay ra           : ");

    while (queue_dequeue(&q, &v) == 0) printf("%d ", v);

    printf("\n");

    queue_huy(&q);

    return 0;
}

#define QMAX 100

typedef struct {
    int    data[QMAX];
    size_t front;      /* chỉ số phần tử đầu */
    size_t rear;       /* chỉ số ô trống kế tiếp */
} QueueTe;

int qt_enqueue(QueueTe *q, int v)
{
    if (q->rear == QMAX) return -1;      /* "đầy" */

    q->data[q->rear++] = v;

    return 0;
}

int qt_dequeue(QueueTe *q, int *out)
{
    if (q->front == q->rear) return -1;  /* rỗng */

    *out = q->data[q->front++];

    return 0;
}

#include <stdio.h>

#include "queue-ptr.h"      /* hàng đợi chứa TNode *, cùng mẫu ở trên */

typedef struct TNode {
    int           data;
    struct TNode *left, *right;
} TNode;

/* In cây theo từng tầng từ trên xuống, trái sang phải. */
void theo_tang(TNode *goc)
{
    if (goc == NULL) return;

    QueueP q;

    queue_khoi_tao(&q);

    if (queue_enqueue(&q, goc) != 0) return;

    while (!queue_rong(&q)) {
        TNode *n;

        queue_dequeue(&q, &n);

        printf("%d ", n->data);

        if (n->left  != NULL) queue_enqueue(&q, n->left);
        if (n->right != NULL) queue_enqueue(&q, n->right);
    }

    printf("\n");
    queue_huy(&q);
}