用c语言编写并实现双端队列并给出所使用的函数库。双端队列(deque)是可进行如下操作的线性表: push (item): 将元素item插入到双端队列的前端; pop (item): 从双端队列中删除前端元素并将该值赋给变量item; inject (item): 将元素item插入到双端队列的尾端; eject (item): 从双端队列中删除尾端元素并将该值赋给变量item .
时间: 2024-02-20 18:59:27 浏览: 25
好的,以下是使用 C 语言实现双端队列的代码示例,使用了标准库中的 `<stdlib.h>` 和 `<stdbool.h>`:
```c
#include <stdlib.h>
#include <stdbool.h>
#define CAPACITY 100 // 双端队列的最大容量
typedef struct Deque {
int items[CAPACITY];
int front;
int rear;
int size;
} Deque;
// 创建一个新的双端队列
Deque* create_deque() {
Deque* deque = (Deque*) malloc(sizeof(Deque));
deque->front = 0;
deque->rear = -1;
deque->size = 0;
return deque;
}
// 判断双端队列是否为空
bool is_empty(Deque* deque) {
return deque->size == 0;
}
// 判断双端队列是否已满
bool is_full(Deque* deque) {
return deque->size == CAPACITY;
}
// 在双端队列前端插入元素
void push(Deque* deque, int item) {
if (is_full(deque)) {
exit(EXIT_FAILURE);
}
deque->front = (deque->front - 1 + CAPACITY) % CAPACITY;
deque->items[deque->front] = item;
deque->size++;
}
// 从双端队列前端删除元素
int pop(Deque* deque) {
if (is_empty(deque)) {
exit(EXIT_FAILURE);
}
int item = deque->items[deque->front];
deque->front = (deque->front + 1) % CAPACITY;
deque->size--;
return item;
}
// 在双端队列后端插入元素
void inject(Deque* deque, int item) {
if (is_full(deque)) {
exit(EXIT_FAILURE);
}
deque->rear = (deque->rear + 1) % CAPACITY;
deque->items[deque->rear] = item;
deque->size++;
}
// 从双端队列后端删除元素
int eject(Deque* deque) {
if (is_empty(deque)) {
exit(EXIT_FAILURE);
}
int item = deque->items[deque->rear];
deque->rear = (deque->rear - 1 + CAPACITY) % CAPACITY;
deque->size--;
return item;
}
// 释放双端队列占用的内存
void destroy_deque(Deque* deque) {
free(deque);
}
```
以上代码通过一个结构体来存储双端队列的元素,使用了循环数组的方式来实现队列的插入和删除操作。其中 `push` 和 `pop` 操作分别在数组的前端进行插入和删除操作,而 `inject` 和 `eject` 操作则在数组的后端进行插入和删除操作。
要使用这个双端队列,只需要在需要的地方调用相应的函数即可。例如:
```c
#include <stdio.h>
int main() {
Deque* deque = create_deque();
push(deque, 1);
push(deque, 2);
inject(deque, 3);
inject(deque, 4);
printf("%d\n", pop(deque)); // 输出 2
printf("%d\n", eject(deque)); // 输出 4
destroy_deque(deque);
return 0;
}
```