数据结构--双端队列

这篇具有很好参考价值的文章主要介绍了数据结构--双端队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构–双端队列

双端队列(Double-ended Queue,简称Deque)是一种具有队列和栈特性的数据结构,可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作,因此可以称为“两端都可以进出的队列”。

双端队列的特点包括:

  1. 可以在队列的头部和尾部进行插入和删除操作。
  2. 元素的插入和删除操作可以分别称为入队和出队操作。
  3. 可以实现先进先出(FIFO)和后进先出(LIFO)两种操作方式。
  4. 可以用于实现栈、队列以及其他需要在两端进行插入和删除操作的场景。

双端队列的常见操作包括:

  1. 在队列头部插入元素(头部入队):将元素插入到队列头部。
  2. 在队列尾部插入元素(尾部入队):将元素插入到队列尾部。
  3. 从队列头部删除元素(头部出队):删除队列头部的元素并返回。
  4. 从队列尾部删除元素(尾部出队):删除队列尾部的元素并返回。
  5. 获取队列头部的元素:返回队列头部的元素,但不删除。
  6. 获取队列尾部的元素:返回队列尾部的元素,但不删除。
  7. 判断队列是否为空:判断队列中是否有元素。
  8. 获取队列中的元素个数:返回队列中元素的个数。

双端队列的实现方式有多种,包括使用数组、链表等数据结构。具体的实现方式可以根据不同的需求和场景选择合适的方式。文章来源地址https://www.toymoban.com/news/detail-721776.html

常用操作代码实现

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

// 定义双端队列节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域,指向下一个节点
} Node;

// 定义双端队列结构体
typedef struct Deque {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} Deque;

// 初始化双端队列
Deque* initializeDeque() {
    Deque* deque = (Deque*)malloc(sizeof(Deque));
    deque->front = NULL;
    deque->rear = NULL;
    return deque;
}

// 判断双端队列是否为空
int isEmpty(Deque* deque) {
    return (deque->front == NULL);
}

// 在队头插入元素
void insertFront(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        newNode->next = deque->front;
        deque->front = newNode;
    }
}

// 在队尾插入元素
void insertRear(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        deque->rear->next = newNode;
        deque->rear = newNode;
    }
}

// 从队头删除元素
int deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->front->data;
    Node* temp = deque->front;
    deque->front = deque->front->next;

    if (deque->front == NULL) {
        deque->rear = NULL;
    }

    free(temp);
    return value;
}

// 从队尾删除元素
int deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->rear->data;
    Node* temp = deque->rear;
    Node* current = deque->front;

    while (current->next != deque->rear) {
        current = current->next;
    }

    deque->rear = current;
    deque->rear->next = NULL;
    free(temp);
    return value;
}

// 获取队头元素
int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->front->data;
}

// 获取队尾元素
int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->rear->data;
}

// 打印双端队列元素
void printDeque(Deque* deque) {
    Node* current = deque->front;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

int main() {
    Deque* deque = initializeDeque();

    insertFront(deque, 1);  // 队头插入元素1
    insertFront(deque, 2);  // 队头插入元素2
    insertRear(deque, 3);   // 队尾插入元素3

    printDeque(deque);      // 输出:2 1 3

    deleteFront(deque);     // 从队头删除元素
    printDeque(deque);      // 输出:1 3

    deleteRear(deque);      // 从队尾删除元素
    printDeque(deque);      // 输出:1

    printf("Front element: %d\n", getFront(deque));  // 输出队头元素:1
    printf("Rear element: %d\n", getRear(deque));    // 输出队尾元素:1

    return 0;
}

知识点回顾与重要考点

双端队列,408数据结构,数据结构,c语言,c++,算法,双端队列

到了这里,关于数据结构--双端队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【“栈、队列”的应用】408数据结构代码

    王道数据结构强化课——【“栈、队列”的应用】代码,持续更新

    2024年02月07日
    浏览(43)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(60)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(162)
  • 【C/C++数据结构与算法】C语言栈与队列

    目录 一、栈 二、队列 三、循环队列 特性: 顺序存储,后进先出 优点是可随机访问,尾部增删效率高 缺点是可能会浪费空间,不知道头部增删 特性: 链式存储,先进先出 优点是无空间浪费,头部增删效率高 缺点是不能随机访问,尾部增删效率低 特性: 顺序存储,先进先

    2024年02月09日
    浏览(62)
  • C数据结构与算法——队列 应用(C语言纯享版 迷宫)

    实验任务 (1) 掌握顺序循环队列及其C语言的表示; (2) 掌握入队、出队等基本算法的实现; (3) 掌握顺序循环队列的基本应用(求解迷宫通路)。 实验内容 使用C语言实现顺序循环队列的类型定义与算法函数; 编写main()函数并根据需要修改、补充相关的类型定义与函数,以实

    2024年02月15日
    浏览(56)
  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(50)
  • 【数据结构与算法分析】使用C语言实现队列的两种(带头结点与不带头结点)链式存储,并且给出一种循环队列的设计思想

      当我们编写程序时,经常需要处理各种数据结构。队列是一种常见的数据结构,它有着广泛的应用场景。队列的基本操作包括入队和出队,应用于模拟等待队列、消息队列、计算机缓存等场合。   在实际编程中,我们可以用不同的数据结构来实现队列。本文主要介绍了

    2024年02月08日
    浏览(118)
  • 【数据结构和算法】--队列的特殊结构-循环队列

    循环队列是队列的一种特殊结构,它的 长度是固定的 k ,同样是 先进先出 ,理论结构是 首尾相连的环形循环结构 。其理论结构大致如下: 具体结构描述可以参考 LeetCode : 622. 设计循环队列的题目要求,大致如下: 设计你的循环队列实现。 循环队列是一种 线性数据结构 ,

    2024年02月04日
    浏览(49)
  • 数据结构——队列(C语言)

    本篇文章将解决一下几个问题: 队列是什么? 如何实现一个队列? 什么场景下会用队列? 队列:一种只允许一端进行插入数据操作,在另一端进行删除操作的特殊线性表。队列具有先进先出(FIFO)入队列:进行插入操作的一端称为队尾,出队列的一端叫做队头。  队列也

    2024年02月11日
    浏览(44)
  • 【数据结构和算法】--队列

    队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 先进先出 FIFO(First In First Out) 的原则。 入队列 :进行 插入操作的一端称为队尾 。 出队列 :进行 删除操作的一端称为队头 。 队列结构联想起来也非常简单,如其名,队列就相当于

    2024年02月05日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包