双端队列(deque,即double-ended queue的缩写)是一种具有队列和栈性质的数据结构,即可以(也只能)在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列,请编写例程实现下列操作: push(x,d):将元素x插入到双端队列d的头; pop(d):删除双端队列d的头元素,并返回; inject(x,d):将元素x插入到双端队列d的尾部; eject(d):删除双端队列d的尾部元素,并返回。
时间: 2024-04-07 10:30:33 浏览: 13
以下是使用顺序存储方式实现双端队列的例程:
#define MAXSIZE 100 // 双端队列最大长度
typedef struct {
int data[MAXSIZE]; // 存储元素的数组
int front; // 头指针,指向队头元素
int rear; // 尾指针,指向队尾元素的下一个位置
} Deque;
// 初始化双端队列
void initDeque(Deque *d) {
d->front = d->rear = 0;
}
// 判断双端队列是否为空
int isDequeEmpty(Deque *d) {
return d->front == d->rear;
}
// 判断双端队列是否已满
int isDequeFull(Deque *d) {
return (d->rear + 1) % MAXSIZE == d->front;
}
// 在双端队列头部插入元素x
void push(int x, Deque *d) {
if (isDequeFull(d)) {
printf("Deque is full.\n");
return;
}
d->front = (d->front - 1 + MAXSIZE) % MAXSIZE;
d->data[d->front] = x;
}
// 删除双端队列头部元素,并返回
int pop(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque is empty.\n");
return -1;
}
int x = d->data[d->front];
d->front = (d->front + 1) % MAXSIZE;
return x;
}
// 在双端队列尾部插入元素x
void inject(int x, Deque *d) {
if (isDequeFull(d)) {
printf("Deque is full.\n");
return;
}
d->data[d->rear] = x;
d->rear = (d->rear + 1) % MAXSIZE;
}
// 删除双端队列尾部元素,并返回
int eject(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque is empty.\n");
return -1;
}
d->rear = (d->rear - 1 + MAXSIZE) % MAXSIZE;
return d->data[d->rear];
}
使用示例:
int main() {
Deque d;
initDeque(&d);
push(1, &d);
push(2, &d);
inject(3, &d);
inject(4, &d);
printf("%d\n", pop(&d)); // 输出1
printf("%d\n", eject(&d)); // 输出4
return 0;
}