C 语言双端队列

2025年1月7日 | 阅读 8 分钟

在 C 语言中，Deque（双端队列）是一种允许从左端和右端进行插入和删除的队列数据结构。

我们可以从上图的双端队列中看到，当我们在后端添加一个元素时，R 向右移动；当我们在后端删除一个元素时，R 向左移动。

同样地，当元素从前端删除时，F 向右移动；当元素添加到前端时，F 向左移动。

双端队列操作

双端队列支持四种操作。

1. 添加尾部元素

它用于从尾部添加一个元素。

2. 删除尾部元素

它用于从尾部删除一个元素。

3. 添加头部元素

它用于从头部添加一个元素。

4. 删除头部元素

它用于删除头部的一个元素。

我们将使用循环数组来实现双端队列。

双端队列的添加尾部元素操作

如果 te 的值大于数组的大小，将显示消息“队列已满”。否则，R 的值将增加 R=(R+1)%Size，并将元素添加到数组中 R 的新位置。最后，te 的值将增加1。

在这种情况下，数组中的元素总数由变量 te 维护。添加元素时，te 的值增加1。删除元素后，te 的值减少1。

程序

让我们以一个例子来演示 C++ 中双端队列的添加尾部元素操作。

#include <stdio.h>
int main() {
    int size = 10;  // Define the size of the queue
    int te = 0;     
    int R = -1;     // Initialize the rear pointer (assuming -1 means empty queue)
    int arr[10];    // Define the array to hold the queue elements

    int new_item = 42;  

    if (te == size) {
        printf("Queue is full\n");
    } else {
        R = (R + 1) % size;
        arr[R] = new_item;
        te = te + 1;
        printf("Item %d added to the queue at position %d\n", new_item, R);
    }
    printf("Queue contents: ");
    for (int i = 0; i < te; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

输出

Item 10 added to the queue at position 0
Queue contents: 10

双端队列的删除尾部元素操作

如果 te 的值为0，我们将显示消息队列为空；否则，我们将检查 R 的值是否为-1，如果是，我们将初始化 R=size-1。之后，我们将显示它并在删除元素后将 R 和 te 减1。

程序

让我们以一个例子来演示 C++ 中双端队列的删除尾部元素操作。

#include <stdio.h>

int main() {
    int size = 10;  
    int te = 0;     
    int R = -1;     // Initialize the rear pointer (assuming -1 means empty queue)
    int arr[10];    // Define the array to hold the queue elements

    int new_item = 42;  // Replace this with the actual item you want to add

    if (te == size) {
        printf("Queue is full\n");
    } else {
        R = (R + 1) % size;
        arr[R] = new_item;
        te = te + 1;
        printf("Item %d added to the queue at position %d\n", new_item, R);
    }
    if (te == 0) {
        printf("Queue is empty\n");
    } else {
        if (R == -1) {
            R = size - 1;
        }
        printf("Number Deleted From Rear End = %d\n", arr[R]);
        R = (R - 1 + size) % size;
        te = te - 1;
    }

    printf("Queue contents: ");
    for (int i = 0; i < te; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

输出

Item 42 added to the queue at position 0
Number Deleted From Rear End = 42
Queue contents:

双端队列的添加头部元素操作

当从前端添加元素时，我们首先检查 te 的值是否等于数组大小，然后显示消息。如果不是，则队列已满，我们将检查 F 的值是否为 0，如果是，则将其初始化为size-1；否则，将其减1。之后，将元素添加到数组中元素 F 的新位置，然后将 te 的值增加1。

程序

让我们以一个例子来演示 C++ 中双端队列的添加头部元素操作。

#include <stdio.h>
int main() {
    int size = 10;  // Define the size of the queue
    int te = 0;     // Initialize the current number of elements in the queue
    int F = 0;      // Initialize the front pointer (assuming 0 means empty queue)
    int arr[10];    // Define the array to hold the queue elements

    // Placeholder for the item you want to add to the queue
    int new_item = 42;  // Replace this with the actual item you want to add

    if (te == size) {
        printf("Queue is full\n");
    } else {
        if (F == 0) {
            F = size - 1;
        } else {
            F = F - 1;
        }
        arr[F] = new_item;
        te = te + 1;
        printf("Item %d added to the front end of the queue at position %d\n", new_item, F);
    }

    // Printing the contents of the queue
    printf("Queue contents: ");
    for (int i = F; i < F + te; i++) {
        printf("%d ", arr[i % size]);
    }
    printf("\n");

    return 0;
}

输出

Item 42 added to the front end of the queue at position 9
Queue contents: 42

双端队列的删除头部元素操作

在删除前端元素时，我们首先检查 te 的值是否等于 0，在这种情况下将显示消息“队列为空”。如果不是，将被删除的元素将显示在屏幕上。之后，我们将 F 的值增加 F=(F+1)%Size，然后将 te 的值减少1。

程序

让我们以一个例子来演示 C++ 中双端队列的删除头部元素操作。

#include <stdio.h>

int main() {
    int size = 10;  
    int te = 0;     
    int F = 0;      
    int arr[10];    
    int new_item = 42;  

    if (te == size) {
        printf("Queue is full\n");
    } else {
        if (F == 0) {
            F = size - 1;
        } else {
            F = F - 1;
        }
        arr[F] = new_item;
        te = te + 1;
        printf("Item %d added to the front end of the queue at position %d\n", new_item, F);
    }
    // Deleting an item from the front end of the queue
    if (te == 0) {
        printf("Queue is empty\n");
    } else {
        printf("Number Deleted From Front End = %d\n", arr[F]);
        F = (F + 1) % size;
        te = te - 1;
    }
    printf("Queue contents: ");
    for (int i = 0; i < te; i++) {
        printf("%d ", arr[(F + i) % size]);
    }
    printf("\n");

    return 0;
}

输出

Item 42 added to the front end of the queue at position 9
Number Deleted From Front End = 42
Queue contents:

实现循环数组的双端队列程序

这是一个使用大小为 7 的循环数组实现的双端队列的示例 C 程序。

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

#define MAX_SIZE 7

struct Deque {
    int arr[MAX_SIZE];
    int front, rear;
    int size;
};

void initDeque(struct Deque *deque) {
    deque->front = -1;
    deque->rear = -1;
    deque->size = 0;
}

// Function to check if the deque is empty
int isEmpty(struct Deque *deque) {
    return (deque->size == 0);
}

// Function to check if the deque is full
int isFull(struct Deque *deque) {
    return (deque->size == MAX_SIZE);
}

// Function to add an element at the rear
void addRear(struct Deque *deque, int value) {
    if (isFull(deque)) {
        printf("Deque is full.\n");
    } else {
        if (deque->front == -1) {
            deque->front = 0;
        }
        deque->rear = (deque->rear + 1) % MAX_SIZE;
        deque->arr[deque->rear] = value;
        deque->size++;
    }
}

// Function to delete an element from the rear
void deleteRear(struct Deque *deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
    } else {
        printf("Number Deleted From Rear End = %d\n", deque->arr[deque->rear]);
        deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
        deque->size--;
        if (deque->size == 0) {
            deque->front = -1;
            deque->rear = -1;
        }
    }
}

// Function to add an element at the front
void addFront(struct Deque *deque, int value) {
    if (isFull(deque)) {
        printf("Deque is full.\n");
    } else {
        if (deque->front == -1) {
            deque->front = 0;
            deque->rear = 0;
        } else {
            deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
        }
        deque->arr[deque->front] = value;
        deque->size++;
    }
}

// Function to delete an element from the front
void deleteFront(struct Deque *deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
    } else {
        printf("Number Deleted From Front End = %d\n", deque->arr[deque->front]);
        deque->front = (deque->front + 1) % MAX_SIZE;
        deque->size--;
        if (deque->size == 0) {
            deque->front = -1;
            deque->rear = -1;
        }
    }
}

// Function to display the elements in the deque
void display(struct Deque *deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
    } else {
        int i, idx = deque->front;
        printf("Deque Elements: ");
        for (i = 0; i < deque->size; i++) {
            printf("%d ", deque->arr[idx]);
            idx = (idx + 1) % MAX_SIZE;
        }
        printf("\n");
    }
}

int main() {
    struct Deque deque;
    initDeque(&deque);
    int choice, value;

    for (;;) {
        printf("\n1. Add Rear\n");
        printf("2. Delete Rear\n");
        printf("3. Add Front\n");
        printf("4. Delete Front\n");
        printf("5. Display\n");
        printf("6. Exit\n");
        printf("Enter Choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter a number: ");
                scanf("%d", &value);
                addRear(&deque, value);
                break;

            case 2:
                deleteRear(&deque);
                break;

            case 3:
                printf("Enter a number: ");
                scanf("%d", &value);
                addFront(&deque, value);
                break;

            case 4:
                deleteFront(&deque);
                break;

            case 5:
                display(&deque);
                break;

            case 6:
                exit(0);
                break;

            default:
                printf("Wrong Choice\n");
        }
    }

    return 0;
}

输出

运行时案例

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 1
Enter a number: 10

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 3
Enter a number: 5

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 1
Enter a number: 20

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 5
Deque Elements: 5 10 20 

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 2
Number Deleted From Rear End = 20

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 4
Number Deleted From Front End = 5

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 5
Deque Elements: 10 

1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 6

下一主题C 语言编程测试

C 语言双端队列

双端队列操作

双端队列的添加尾部元素操作

双端队列的删除尾部元素操作

双端队列的添加头部元素操作

双端队列的删除头部元素操作

实现循环数组的双端队列程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言双端队列

双端队列操作

双端队列的添加尾部元素操作

双端队列的删除尾部元素操作

双端队列的添加头部元素操作

双端队列的删除头部元素操作

实现循环数组的双端队列程序

相关帖子

C 语言类型转换

如何在 C 语言中打印双引号

C 语言 nanosleep() 函数

C 语言锯齿数组或数组的数组

C 语言 fprintf() 和 fwrite() 函数的区别

C 语言尾调用优化

C 语言和 LISP 语言的区别

C 语言和 Dart 的区别

C 语言八进制数

C 语言 ftok() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器