Deque

int deque_them_dau (Deque *d, int v);
int deque_them_cuoi(Deque *d, int v);
int deque_lay_dau  (Deque *d, int *out);
int deque_lay_cuoi (Deque *d, int *out);

/* Cộng ba hàm hỏi trạng thái */
int    deque_rong(const Deque *d);
size_t deque_so_phan_tu(const Deque *d);
int    deque_xem_dau(const Deque *d, int *out);
int    deque_xem_cuoi(const Deque *d, int *out);

#ifndef DEQUE_H
#define DEQUE_H

#include <stddef.h>

#define DMAX 8

typedef struct {
    int    data[DMAX];
    size_t front;
    size_t size;
} Deque;

void   dq_khoi_tao(Deque *d);
int    dq_rong(const Deque *d);
int    dq_day(const Deque *d);
size_t dq_so_phan_tu(const Deque *d);
int    dq_them_dau(Deque *d, int v);
int    dq_them_cuoi(Deque *d, int v);
int    dq_lay_dau(Deque *d, int *out);
int    dq_lay_cuoi(Deque *d, int *out);
int    dq_tai(const Deque *d, size_t i, int *out);

#endif

#include "deque.h"

void dq_khoi_tao(Deque *d) { d->front = 0; d->size = 0; }

int dq_rong(const Deque *d) { return d->size == 0; }
int dq_day (const Deque *d) { return d->size == DMAX; }

size_t dq_so_phan_tu(const Deque *d) { return d->size; }

/* Thêm vào cuối: y hệt enqueue của Bài 23.2. */
int dq_them_cuoi(Deque *d, int v)
{
    if (d->size == DMAX) return -1;

    d->data[(d->front + d->size) % DMAX] = v;
    ++d->size;

    return 0;
}

/* Thêm vào đầu: LÙI front một bước theo vòng, rồi ghi vào đó. */
int dq_them_dau(Deque *d, int v)
{
    if (d->size == DMAX) return -1;

    d->front = (d->front + DMAX - 1) % DMAX;      /* lùi một, không dùng số âm */
    d->data[d->front] = v;
    ++d->size;

    return 0;
}

/* Lấy ở đầu: y hệt dequeue. */
int dq_lay_dau(Deque *d, int *out)
{
    if (d->size == 0) return -1;

    if (out != NULL) *out = d->data[d->front];

    d->front = (d->front + 1) % DMAX;
    --d->size;

    return 0;
}

/* Lấy ở cuối: chỉ cần giảm size, front không đổi. */
int dq_lay_cuoi(Deque *d, int *out)
{
    if (d->size == 0) return -1;

    if (out != NULL) *out = d->data[(d->front + d->size - 1) % DMAX];

    --d->size;

    return 0;
}

/* Truy cập phần tử thứ i tính từ đầu. O(1). */
int dq_tai(const Deque *d, size_t i, int *out)
{
    if (i >= d->size) return -1;

    *out = d->data[(d->front + i) % DMAX];

    return 0;
}

#include <stdlib.h>

typedef struct DNode {
    int           data;
    struct DNode *prev, *next;
} DNode;

typedef struct {
    DNode *head, *tail;
    size_t size;
} DequeLK;

int dql_them_dau(DequeLK *d, int v)
{
    DNode *n = malloc(sizeof *n);

    if (n == NULL) return -1;

    n->data = v;
    n->prev = NULL;
    n->next = d->head;

    if (d->head != NULL) d->head->prev = n;
    else                 d->tail       = n;

    d->head = n;
    ++d->size;

    return 0;
}

int dql_lay_cuoi(DequeLK *d, int *out)
{
    if (d->tail == NULL) return -1;

    DNode *n = d->tail;

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

    d->tail = n->prev;

    if (d->tail != NULL) d->tail->next = NULL;
    else                 d->head       = NULL;

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

    return 0;
}

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

/* Deque chứa CHỈ SỐ, không chứa giá trị.
   Bất biến: các giá trị tại những chỉ số trong deque giảm dần.
   Nhờ vậy phần tử đầu deque luôn là chỉ số của giá trị lớn nhất
   trong cửa sổ hiện tại.                                          */
int cua_so_lon_nhat(const int *a, size_t n, size_t k, int *ra)
{
    if (a == NULL || ra == NULL || k == 0 || k > n) return -1;

    size_t *dq = malloc(n * sizeof *dq);      /* deque chỉ số, đủ chỗ xấu nhất */

    if (dq == NULL) return -1;

    size_t dau = 0, cuoi = 0;                 /* [dau, cuoi) là vùng dùng */
    size_t m = 0;

    for (size_t i = 0; i < n; ++i) {
        /* 1. Bỏ ở ĐẦU những chỉ số đã rơi ra ngoài cửa sổ */
        while (dau < cuoi && dq[dau] + k <= i) ++dau;

        /* 2. Bỏ ở CUỐI những chỉ số có giá trị nhỏ hơn hoặc bằng a[i].
              Chúng không bao giờ còn là lớn nhất nữa, vì a[i] vào sau
              và lớn hơn, nên sẽ ở lại lâu hơn.                        */
        while (dau < cuoi && a[dq[cuoi - 1]] <= a[i]) --cuoi;

        /* 3. Thêm i vào cuối */
        dq[cuoi++] = i;

        /* 4. Từ cửa sổ đầy đủ trở đi, ghi kết quả */
        if (i + 1 >= k) ra[m++] = a[dq[dau]];
    }

    free(dq);

    return 0;
}

#include <stdio.h>

int cua_so_lon_nhat(const int *a, size_t n, size_t k, int *ra);

int main(void)
{
    int    a[] = { 1, 3, -1, -3, 5, 3, 6, 7 };
    size_t n   = sizeof a / sizeof a[0];
    size_t k   = 3;
    int    ra[8];

    if (cua_so_lon_nhat(a, n, k, ra) != 0) return 1;

    printf("mang : ");

    for (size_t i = 0; i < n; ++i) printf("%d ", a[i]);

    printf("\nk = %zu\n", k);

    for (size_t i = 0; i + k <= n; ++i) {
        printf("cua so [");

        for (size_t j = i; j < i + k; ++j) printf("%d%s", a[j], j + 1 < i + k ? " " : "");

        printf("] -> %d\n", ra[i]);
    }

    return 0;
}

Deque d;

dq_khoi_tao(&d);

/* Dùng như NGĂN XẾP: chỉ đụng vào cuối */
dq_them_cuoi(&d, 10);
dq_them_cuoi(&d, 20);
dq_lay_cuoi(&d, &v);      /* 20, LIFO */

/* Dùng như HÀNG ĐỢI: thêm cuối, lấy đầu */
dq_them_cuoi(&d, 10);
dq_them_cuoi(&d, 20);
dq_lay_dau(&d, &v);       /* 10, FIFO */