# jh_dynamic_deque

**Repository Path**: arrco/jh_dynamic_deque

## Basic Information

- **Project Name**: jh_dynamic_deque
- **Description**: jh_dynamic_deque是一个支持动态扩展大小的双端队列(deque)。
- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-08-13
- **Last Updated**: 2022-08-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# jh_dynamic_deque

## 介绍

jh_dynamic_deque是一个支持动态扩展大小的双端队列(deque)。

## 使用说明

只需要包含jh_dynamic_deque.c和jh_dynamic_deque.h两个文件即可使用。

## 接口函数

提供以下接口用于动态双端队列的使用：

```c
/*判断动态双端队列是否为空*/
int jh_dynamic_deque_is_empty(jh_dynamic_deque_t* deque);
/*判断动态双端队列是否已满*/
int jh_dynamic_deque_is_full(jh_dynamic_deque_t* deque);
/*获取动态双端队列的数据数量*/
size_t jh_dynamic_deque_count(jh_dynamic_deque_t* deque);
/*获取动态双端队列的大小*/
size_t jh_dynamic_deque_size(jh_dynamic_deque_t* deque);
/*获取动态双端队列的容量*/
size_t jh_dynamic_deque_capacity(jh_dynamic_deque_t* deque);
/*数据添加到队首*/
int jh_dynamic_deque_push_head(jh_dynamic_deque_t* deque, void* item);
/*数据添加到队尾*/
int jh_dynamic_deque_push_tail(jh_dynamic_deque_t* deque, void* item);
/*强制数据添加到队首*/
int jh_dynamic_deque_force_push_head(jh_dynamic_deque_t* deque, void* item);
/*强制数据添加到队尾*/
int jh_dynamic_deque_force_push_tail(jh_dynamic_deque_t* deque, void* item);
/*队首数据出队*/
int jh_dynamic_deque_pop_head(jh_dynamic_deque_t* deque, void* item);
/*队尾数据出队*/
int jh_dynamic_deque_pop_tail(jh_dynamic_deque_t* deque, void* item);
/*查看队首的数据*/
int jh_dynamic_deque_peek_head(jh_dynamic_deque_t* deque, void* item);
/*查看队尾的数据*/
int jh_dynamic_deque_peek_tail(jh_dynamic_deque_t* deque, void* item);
/*调整动态双端队列大小*/
int jh_dynamic_deque_resize(jh_dynamic_deque_t* deque, size_t num);
/*压缩动态双端队列的容量到合适大小*/
int jh_dynamic_deque_shrink_to_fit(jh_dynamic_deque_t* deque);
/*清空动态双端队列*/
int jh_dynamic_deque_clear(jh_dynamic_deque_t* deque);
/*获取动态双端队列指定位置的指定数量数据*/
int jh_dynamic_deque_get_data(jh_dynamic_deque_t* deque, void* item, size_t start, size_t num);
/*动态双端队列数据排序*/
int jh_dynamic_deque_sort(jh_dynamic_deque_t* deque, int (*compare)(const void*, const void*));
/*创建动态双端队列*/
jh_dynamic_deque_t* jh_dynamic_deque_create(size_t num, size_t size);
/*销毁动态双端队列*/
void jh_dynamic_deque_destroy(jh_dynamic_deque_t* deque);
```

另外还提供两个宏接口用于数据迭代：

```c
/*动态双端队列数据迭代*/
JH_DYNAMIC_DEQUE_ITER(jh_dynamic_deque_t* deque, void* item)
/*动态双端队列数据反向迭代*/
JH_DYNAMIC_DEQUE_ITER_REVERSE(jh_dynamic_deque_t* deque, void* item)
```

## 接口使用说明

### 1.创建动态双端队列

调用接口`jh_dynamic_deque_create`创建动态双端队列。

```c
/*创建动态双端队列*/
jh_dynamic_deque_t* jh_dynamic_deque_create(size_t num, size_t size);
```

函数参数含义：

| 参数 | 含义                     |
| ---- | ------------------------ |
| num  | 队列中能存放的数据项数量 |
| size | 队列中每个数据项的大小   |

函数返回值`jh_dynamic_deque_t*` 动态双端队列：

| 返回值 | 含义                   |
| ------ | ---------------------- |
| 非NULL | 成功，返回动态双端队列 |
| NULL   | 失败                   |

使用示例：

```c
jh_dynamic_deque_t *deque = jh_dynamic_deque_create(10, sizeof(int));
```

### 2.销毁动态双端队列

调用接口`jh_dynamic_deque_destroy`销毁动态双端队列。

```c
/*销毁动态双端队列*/
void jh_dynamic_deque_destroy(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数无返回值。

### 3.数据添加到队首

调用接口`jh_dynamic_deque_push_head`将数据添加到队首。如果队列已满则会添加失败，返回-1。

```c
/*数据添加到队首*/
int jh_dynamic_deque_push_head(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要入队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 4.数据添加到队尾

调用接口`jh_dynamic_deque_push_tail`将数据添加到队尾。如果队列已满则会添加失败，返回-1。

```c
/*数据添加到队尾*/
int jh_dynamic_deque_push_tail(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要入队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 5.强制数据添加到队首

调用接口`jh_dynamic_deque_force_push_head`将数据添加到队首。如果双端队列已满则会增加双端队列的大小，并将数据添加到队首。

```c
/*强制数据添加到队首*/
int jh_dynamic_deque_force_push_head(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要入队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 6.强制数据添加到队尾

调用接口`jh_dynamic_deque_force_push_tail`将数据添加到队尾。如果双端队列已满则会增加双端队列的大小，并将数据添加到队尾。

```c
/*强制数据添加到队尾*/
int jh_dynamic_deque_force_push_tail(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要入队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 7.队首数据出队

调用接口`jh_dynamic_deque_pop_head`将队首数据出队。

```c
/*队首数据出队*/
int jh_dynamic_deque_pop_head(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要出队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 8.队尾数据出队

调用接口`jh_dynamic_deque_pop_tail`将队尾数据出队。

```c
/*队尾数据出队*/
int jh_dynamic_deque_pop_tail(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 要出队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 9.查看队首的数据

调用接口`jh_dynamic_deque_peek_head`查看队首的数据。

```c
/*查看队首的数据*/
int jh_dynamic_deque_peek_head(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |
| item  | 队首的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 10.查看队尾的数据

调用接口`jh_dynamic_deque_peek_tail`查看队尾的数据。

```c
/*查看队尾的数据*/
int jh_dynamic_deque_peek_tail(jh_dynamic_deque_t* deque, void* item);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |
| item  | 队尾的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 11.获取动态双端队列的数据数量

调用接口`jh_dynamic_deque_count`查看动态双端队列中已有的数据数量。

```c
/*获取动态双端队列的数据数量*/
size_t jh_dynamic_deque_count(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数返回值：

| 返回值 | 含义                   |
| ------ | ---------------------- |
| >=0    | 动态双端队列的数据数量 |

### 12.获取动态双端队列的大小

调用接口`jh_dynamic_deque_size`查看动态双端队列的大小，也就是双端队列中能存放的数据数量。

```c
/*获取动态双端队列的大小*/
size_t jh_dynamic_deque_size(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数返回值：

| 返回值 | 含义                   |
| ------ | ---------------------- |
| >=0    | 动态双端队列的数据数量 |

### 13.调整动态双端队列大小

调用接口`jh_dynamic_deque_resize`调整动态双端队列的大小。注意，如果将双端队列的大小变小，并且数据数量大于调整后队列大小，会导致数据丢失，因为在压缩队列大小时会自动将多余数据弹出。

```c
/*调整动态双端队列大小*/
int jh_dynamic_deque_resize(jh_dynamic_deque_t* deque, size_t num);
```

函数参数含义：

| 参数  | 含义                     |
| ----- | ------------------------ |
| deque | 动态双端队列             |
| num   | 队列中能存放的数据项数量 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 14.判断动态双端队列是否已满

调用接口`jh_dynamic_deque_is_full`判断动态双端队列是否已满。

```c
/*判断动态双端队列是否已满*/
int jh_dynamic_deque_is_full(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数返回值：

| 返回值 | 含义             |
| ------ | ---------------- |
| 1      | 动态双端队列已满 |
| 0      | 动态双端队列未满 |
| -1     | 失败             |

### 15.判断动态双端队列是否为空

调用接口`jh_dynamic_deque_is_empty`判断动态双端队列是否为空。

```c
/*判断动态双端队列是否为空*/
int jh_dynamic_deque_is_empty(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数返回值：

| 返回值 | 含义               |
| ------ | ------------------ |
| 1      | 动态双端队列为空   |
| 0      | 动态双端队列不为空 |
| -1     | 失败               |

### 16.清空动态双端队列

调用接口`jh_dynamic_deque_clear`清空动态双端队列内的数据。

```c
/*清空动态双端队列*/
int jh_dynamic_deque_clear(jh_dynamic_deque_t* deque);
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 17.动态双端队列数据迭代

调用接口`JH_DYNAMIC_DEQUE_ITER`或者`JH_DYNAMIC_DEQUE_ITER_REVERSE`进行数据迭代。

```c
/*双端队列数据迭代*/
JH_DYNAMIC_DEQUE_ITER(jh_dynamic_deque_t* deque, void* item)
/*双端队列数据反向迭代*/
JH_DYNAMIC_DEQUE_ITER_REVERSE(jh_dynamic_deque_t* deque, void* item)
```

函数参数含义：

| 参数  | 含义         |
| ----- | ------------ |
| deque | 动态双端队列 |
| item  | 数据项       |

使用示例，打印出当前动态双端队列中的所有数据：

```c
//从队首到队尾的顺序遍历
JH_DYNAMIC_DEQUE_ITER(&deque, &val) {
    printf("val : %d\n", val);
}

//从队尾到队首的顺序遍历
JH_DYNAMIC_DEQUE_ITER_REVERSE(&deque, &val) {
    printf("val : %d\n", val);
}
```

### 18.获取动态双端队列指定位置的指定数量数据

这是一个特殊接口，正常双端队列是没有这个功能的。可以获取动态双端队列中任意位置的数据，或者从任意位置开始，指定数量的连续数据。如果指定的位置超出双端队列范围，则获取失败返回 0 ；如果指定数量超过实际的数据长度，则返回实际长度的数据。

调用接口`jh_dynamic_deque_get_data`使用。

```c
/*获取动态双端队列指定位置的指定数量数据*/
int jh_dynamic_deque_get_data(jh_dynamic_deque_t* deque, void* item, size_t start, size_t num);
```

函数参数含义：

| 参数  | 含义           |
| ----- | -------------- |
| deque | 动态双端队列   |
| item  | 获取的数据项   |
| start | 指定的起始位置 |
| num   | 指定的数量     |

函数返回值：

| 返回值 | 含义        |
| --- | --------- |
| >=0 | 成功获取的数据数量 |
| -1  | 失败        |

### 19.动态双端队列数据排序

调用接口`jh_dynamic_deque_sort`对动态双端队列内的数据进行排序。

```c
/*动态双端队列数据排序*/
int jh_dynamic_deque_sort(jh_dynamic_deque_t* deque, int (*compare)(const void*, const void*));
```

函数参数含义：

| 参数    | 含义                             |
| ------- | -------------------------------- |
| deque   | 动态双端队列                     |
| compare | 指向用于比较两个数据项的函数指针 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

#### 定义compare函数

需要定义一个用于比较两个数据项的compare函数。这个函数的实现方式影响数据会如何排序。

函数的类型为`int (*compare)(const void* p1, const void* p2)`。

函数返回值：

| 返回值 | 含义                                   |
| ------ | -------------------------------------- |
| 小于0  | p1指向的数据项排在在p2指向的数据项之前 |
| 大于0  | p1指向的数据项排在在p2指向的数据项之后 |
| 等于0  | p1指向的数据项与p2指向的数据项相同     |

使用示例，假设保存的数据类型为int，按从小到大的方式排序：

```c
int compare(const void * p1, const void * p2)
{
    return ( *(int*)p1 - *(int*)p2 );
}
```

## 使用示例

动态双端队列的基础用法：

```c
int main(int argc, char* argv[])
{
    //双端队列初始化
    jh_dynamic_deque_t *deque = jh_dynamic_deque_create(10, sizeof(int));
    
    //定义要用于传入的数据
    int items[] = {81, 13, 16, 38, 49, 67};
    int i, val;
    
    //数据添加到队尾
    printf("\npush tail:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_dynamic_deque_push_tail(deque, &items[i]))
            printf("%d ", items[i]);
    }
    printf("\n");
    
    //查看当前的状态
    printf("\nsize : %zu count %zu empty : %d full : %d\n", jh_dynamic_deque_size(deque), jh_dynamic_deque_count(deque), jh_dynamic_deque_is_empty(deque), jh_dynamic_deque_is_full(deque));
    
    //查看队首的数据
    jh_dynamic_deque_peek_head(deque, &val);
    printf("\npeek head %d\n", val);
    
    //查看队尾的数据
    jh_dynamic_deque_peek_tail(deque, &val);
    printf("\npeek tail %d\n", val);
    
    //队首数据出队
    printf("\npop head:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_dynamic_deque_pop_head(deque, &val))
            printf("%d ", val);
    }
    printf("\n");
    
    //查看当前的状态
    printf("\nsize : %zu count %zu empty : %d full : %d\n", jh_dynamic_deque_size(deque), jh_dynamic_deque_count(deque), jh_dynamic_deque_is_empty(deque), jh_dynamic_deque_is_full(deque));


    //数据添加到队首
    printf("\npush head:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_dynamic_deque_push_head(deque, &items[i]))
            printf("%d ", items[i]);
    }
    printf("\n");
    
    //可以查看当前所有数据，从队首到队尾的顺序遍历
    printf("\niter:\n");
    JH_DYNAMIC_DEQUE_ITER(deque, &val) {
        printf("%d ", val);
    }
    printf("\n");
    
    //可以查看当前所有数据，从队尾到队首的顺序遍历
    printf("\niter reverse:\n");
    JH_DYNAMIC_DEQUE_ITER_REVERSE(deque, &val) {
        printf("%d ", val);
    }
    printf("\n");
    
    //将队尾数据出队
    printf("\npop tail:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_dynamic_deque_pop_tail(deque, &val))
            printf("%d ", val);
    }
    printf("\n");
    
    
    //数据添加到队首
    printf("\npush head:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_dynamic_deque_push_head(deque, &items[i]))
            printf("%d ", items[i]);
    }
    printf("\n");
    
    //查看当前的状态
    printf("\nsize : %zu count %zu empty : %d full : %d\n", jh_dynamic_deque_size(deque), jh_dynamic_deque_count(deque), jh_dynamic_deque_is_empty(deque), jh_dynamic_deque_is_full(deque));
    
    //清空队列
    printf("\nclear\n");
    jh_dynamic_deque_clear(deque);
    
    //查看当前的状态
    printf("\nsize : %zu count %zu empty : %d full : %d\n", jh_dynamic_deque_size(deque), jh_dynamic_deque_count(deque), jh_dynamic_deque_is_empty(deque), jh_dynamic_deque_is_full(deque));

    //销毁动态双端队列
    jh_dynamic_deque_destroy(deque);
    
    return 0;
}
```

运行结果如下：

```shell
push tail:
81 13 16 38 49 67

size : 10 count 6 empty : 0 full : 0

peek head 81

peek tail 67

pop head:
81 13 16 38 49 67

size : 10 count 0 empty : 1 full : 0

push head:
81 13 16 38 49 67

iter:
67 49 38 16 13 81

iter reverse:
81 13 16 38 49 67

pop tail:
81 13 16 38 49 67

push head:
81 13 16 38 49 67

size : 10 count 6 empty : 0 full : 0

clear

size : 10 count 0 empty : 1 full : 0
```

## License

MIT License

Copyright (c) 2022 Hong Jiahua

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.