- 每个元素的长度是固定已知的.
- 单个元素长度是任意的.
先写一个基本的单字节版本，队列元素为 unsigned char
cirque.h#ifndef __CIR_QUE_H__ #define __CIR_QUE_H__ #includecirque.c#include #include typedef struct CirQue { uint32_t head; uint32_t tail; uint32_t elecnt; uint8_t* mem; uint32_t memlen; int (*deque)(struct CirQue* pque); int (*enque)(struct CirQue* pque, uint8_t ele); }CirQue_t; extern void CirQueInit(CirQue_t* pque, void* mem, uint32_t memlen); #endif
#include "cirque.h" #includemain.cstatic int deQueue(CirQue_t* pque) { int retval; if (pque->elecnt == 0) { printf("que nullrn"); return -1; } retval = pque->mem[pque->head]; pque->mem[pque->head] = 0; pque->head++; pque->head %= pque->memlen; pque->elecnt--; return retval; } static int enQueue(CirQue_t* pque, uint8_t element) { if (pque->elecnt == pque->memlen) { printf("que overflow! rn"); return -1; } pque->mem[pque->tail] = element; pque->tail++; pque->tail %= pque->memlen; pque->elecnt++; return 0; } void CirQueInit(CirQue_t* pque, void* mem, uint32_t memlen) { pque->mem = (uint8_t*)mem; pque->memlen = memlen; pque->deque = deQueue; pque->enque = enQueue; pque->elecnt = 0; pque->head = 0; pque->tail = 0; memset(pque->mem, 0, pque->memlen); }
#include "cirque.h" #include测试输出static void printque(CirQue_t* q) { for (int i = 0; i < q->memlen; i++) { printf("%2d ", q->mem[i]); } char arr[23] = " "; if (q->head == q->tail) { arr[q->tail * 4] = 'X'; } else { arr[q->head * 4] = 'h'; arr[q->tail * 4] = 't'; } printf(" %d n %sn" "------------------------------n", q->elecnt, arr); } int main(void) { CirQue_t que; uint8_t arr[5]; static int in = 1; CirQueInit(&que, arr, sizeof(arr)); int i = 0; while (i++ < 4) { que.enque(&que, in++); printque(&que); que.enque(&que, in++); printque(&que); que.enque(&que, in++); printque(&que); que.enque(&que, in++); printque(&que); que.deque(&que);printque(&que); que.deque(&que);printque(&que); que.deque(&que);printque(&que); que.deque(&que);printque(&que); } return 0; }
gcc main.c cirque.c && ./a.out
1 0 0 0 0 1
h t
------------------------------
1 2 0 0 0 2
h t
------------------------------
1 2 3 0 0 3
h t
------------------------------
1 2 3 4 0 4
h t
------------------------------
0 2 3 4 0 3
h t
------------------------------
0 0 3 4 0 2
h t
------------------------------
0 0 0 4 0 1
h t
------------------------------
0 0 0 0 0 0
X
------------------------------
0 0 0 0 5 1
t h
------------------------------
6 0 0 0 5 2
t h
------------------------------
6 7 0 0 5 3
t h
------------------------------
6 7 8 0 5 4
t h
------------------------------
6 7 8 0 0 3
h t
------------------------------
0 7 8 0 0 2
h t
------------------------------
0 0 8 0 0 1
h t
------------------------------
0 0 0 0 0 0
X
------------------------------
0 0 0 9 0 1
h t
------------------------------
0 0 0 9 10 2
t h
------------------------------
11 0 0 9 10 3
t h
------------------------------
11 12 0 9 10 4
t h
------------------------------
11 12 0 0 10 3
t h
------------------------------
11 12 0 0 0 2
h t
------------------------------
0 12 0 0 0 1
h t
------------------------------
0 0 0 0 0 0
X
------------------------------
0 0 13 0 0 1
h t
------------------------------
0 0 13 14 0 2
h t
------------------------------
0 0 13 14 15 3
t h
------------------------------
16 0 13 14 15 4
t h
------------------------------
16 0 0 14 15 3
t h
------------------------------
16 0 0 0 15 2
t h
------------------------------
16 0 0 0 0 1
h t
------------------------------
0 0 0 0 0 0
X
------------------------------
任意字节版本
队列元素可以是任意固定长度的基本类型(int/short)或自定义类型.
cirque.h#ifndef __CIR_QUE_H__ #define __CIR_QUE_H__ #includecirque.c#include #include typedef struct CirQue { uint32_t head; uint32_t tail; uint32_t elecnt; uint32_t elesize; uint32_t maxnumel; uint8_t* mem; uint32_t memlen; void* (*pop)(struct CirQue* pque); int (*push)(struct CirQue* pque, void* eleaddr); }CirQue_t; extern void CirQueInit(CirQue_t* pque, uint32_t elesize, void* mem, uint32_t memlen); #endif
#include "cirque.h" #includemain.cstatic void* pop_front(CirQue_t* pque) { void* retval; if (pque->elecnt == 0) { printf("que nullrn"); return (void*)0; } retval = &pque->mem[pque->head]; // memset(&pque->mem[pque->head], 0, pque->elesize); pque->head += pque->elesize; pque->head %= pque->memlen; pque->elecnt--; return retval; } static int push_back(CirQue_t* pque, void* eleaddr) { if (pque->elecnt == pque->maxnumel) { printf("que overflow! rn"); return -1; } memcpy(&pque->mem[pque->tail], eleaddr, pque->elesize); pque->tail += pque->elesize; pque->tail %= pque->memlen; pque->elecnt++; return 0; } void CirQueInit(CirQue_t* pque, uint32_t elesize, void* mem, uint32_t memlen) { if (memlen == 0 || memlen % elesize != 0) { printf("CirQueInit error: invalid paramn"); return; } pque->maxnumel = memlen / elesize; pque->mem = (uint8_t*)mem; pque->memlen = memlen; pque->elesize = elesize; pque->pop = pop_front; pque->push = push_back; pque->elecnt = 0; pque->head = 0; pque->tail = 0; memset(pque->mem, 0, pque->memlen); }
#include "cirque.h" #include测试结果static void printque(CirQue_t* q) { for (int i = 0; i < q->memlen; i++) { printf(" %4X", q->mem[i]); } char arr[128] = ""; memset(arr, ' ', 128); arr[127] = 0; if (q->head == q->tail) { arr[q->tail * 5 + 9] = 'X'; } else { arr[q->head * 5 + 9] = 'h'; arr[q->tail * 5 + 9] = 't'; } printf(" %d n%sn" "-------------------------------------------" "------------------------------------n", q->elecnt, arr); } int main(void) { CirQue_t que; uint16_t arr[5]; static uint16_t in = 0x1111; CirQueInit(&que, 2, arr, sizeof(arr)); printque(&que); int i = 0; while (i++ < 4) { que.push(&que, &in); printque(&que); in += 0x1111; que.push(&que, &in); in += 0x1111; printque(&que); que.push(&que, &in); in += 0x1111; printque(&que); que.push(&que, &in); printque(&que); uint16_t* p = que.pop(&que); printque(&que); // que.pop(&que);printque(&que); // que.pop(&que);printque(&que); // que.pop(&que);printque(&que); } uint16_t* p = que.pop(&que); printf("pop = %d n", *p); printque(&que); return 0; }
$ gcc main.c cirque.c && ./a.out
0 0 0 0 0 0 0 0 0 0 0
X
-------------------------------------------------------------------------------
11 11 0 0 0 0 0 0 0 0 1
h t
-------------------------------------------------------------------------------
11 11 22 22 0 0 0 0 0 0 2
h t
-------------------------------------------------------------------------------
11 11 22 22 33 33 0 0 0 0 3
h t
-------------------------------------------------------------------------------
11 11 22 22 33 33 44 44 0 0 4
h t
-------------------------------------------------------------------------------
11 11 22 22 33 33 44 44 0 0 3
h t
-------------------------------------------------------------------------------
11 11 22 22 33 33 44 44 44 44 4
t h
-------------------------------------------------------------------------------
55 55 22 22 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 22 22 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 22 22 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
55 55 22 22 33 33 44 44 44 44 4
t h
-------------------------------------------------------------------------------
55 55 77 77 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 33 33 44 44 44 44 5
X
-------------------------------------------------------------------------------
55 55 77 77 33 33 44 44 44 44 4
t h
-------------------------------------------------------------------------------
55 55 77 77 AA AA 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 AA AA 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 AA AA 44 44 44 44 5
X
-------------------------------------------------------------------------------
que overflow!
55 55 77 77 AA AA 44 44 44 44 5
X
-------------------------------------------------------------------------------
55 55 77 77 AA AA 44 44 44 44 4
t h
-------------------------------------------------------------------------------
pop = 17476
55 55 77 77 AA AA 44 44 44 44 3
h t
-------------------------------------------------------------------------------
