精华内容
下载资源
问答
  • 一、什么队列 队列是有次序的数据集合,其特征是: 新数据项的添加总发生在一端,...队列仅有一个出口和一个入口:不允许数据项直接插入队列中,也不允许从中间移除数据项。 生活中常见的队列:打印机的打印队列、进

    一、什么队列

    队列是有次序的数据集合,其特征是:

    • 新数据项的添加总发生在一端,通常称为“尾rear端”
    • 现存数据的一处总发生在另一端,通常称为“首front端”

    当数据项加入队列时,首先出现在队尾,随着队首数据项的移除,它逐渐接近队首。新加入的数据项必须在数据集的末尾等待,而等待时间最长的数据项则是队首,这种次序安排的原则称为FIFO(First-in-first-out),

    队列仅有一个出口和一个入口:不允许数据项直接插入队列中,也不允许从中间移除数据项

    生活中常见的队列:打印机的打印队列、进程调度等

    二、队列的操作

    抽象数据类型Queue有如下的操作定义:

    • Queue():创建一个空队列对象,返回值为Queue对象;
    • enqueue(item): 将数据项item添加到队尾,无返回值;
    • dequeue():从队首移除数据项,返回值为队首数据项,队列被修改;
    • isEmpty():测试是否空队列,返回值为布尔值;
    • size():返回队列中数据项的个数;

    三、代码实现

    class Queue():
        def __init__(self):
            self.items = []             #
    
        def isEmpty(self):
            return self.items == []
    
        def enqueue(self, item):
            self.items.insert(0, item)     # 复杂度为O(n)
    
        def dequeue(self):
            return self.items.pop()        # 复杂度为O(1)
    
        def size(self):
            return len(self.items)

     

    展开全文
  • 队列抽象数据类型

    2020-05-22 21:16:17
    元素具有相同的类型,相邻元素具有前驱和后继关系。 Operation InitQueue(*Q):初始化列表,建立一个空队列Q。 DestroyQueue(*Q):若队列Q存在,则销毁它。 ClearQueue(*Q):将队列Q清空。 QueueEmpty(Q):若队列为空,...
    ADT 队列(Queue)
    Date
    同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
    Operation
    InitQueue(*Q):初始化列表,建立一个空队列Q。
    DestroyQueue(*Q):若队列Q存在,则销毁它。
    ClearQueue(*Q):将队列Q清空。
    QueueEmpty(Q):若队列为空,则返回‘ture’。
    GetHead(Q,*e):若队列存在且非空,返回队列的头元素。
    EnQueue(*Q,e):将e插入到队列的队尾。
    DeQueue(*Q,*e):删除队列Q的头元素
    QueueLength(Q):返回队列Q的元素个数
    endDAT
    
    
    展开全文
  • 4.2.0 队列的定义和抽象数据类型

    千次阅读 2018-03-17 13:06:56
    概念 队列 ( queue ) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。...抽象数据类型 ADT 队列 (Queue) Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系 。 Operation ...

    概念

    队列 ( queue ) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
    队列是一种先进先出 (First In First Out) 的线性表,简称 FIFO。允许插入的一
    端称为队尾,允许删除的一端称为队头。
    这里写图片描述

    抽象数据类型

    ADT 队列 (Queue)
    Data
        同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系 。
    Operation
        InitQueue(*Q) :初始化操作,建立一个空队列Q。
        DestroyQueue(*Q) :若队列Q存在,则销毁它。
        ClearQueue(*Q) :将队列Q清空。
        QueueEmpty(Q) :若队列Q为空,返回true,否则返回false。
        GetHead(Q,*e) :若队列Q存在且非空,用e返回队列Q的队头元素。
        EnQueue(*Q,e) :若队列Q存在,插入新元素e到队列Q中并成为对尾元素 。
        DeQueue(*Q,*e) :删除队列Q中队头元素,并用e返回其值。
        QueueLength(Q) :返回队列Q的元素个数
    endADT
    展开全文
  • 队列(queue)是表。然而,使用队列时插入在一端进行而删除则在另一端进行。  队列模型 ...队列抽象模型: 队列的数组实现  如同栈的情形一样,对于队列而言任何的表的实现都是合法的。像栈一样,对于

      队列(queue)是表。然而,使用队列时插入在一端进行而删除则在另一端进行。 


    队列模型

      队列的基本操作enqueue(入队),它是在表的末端(叫做队尾(rear))插入一个元素 ,和dequeue(出队),它是删除并返回在表的开头(也叫队头(front))的元素。

    队列抽象模型:


    队列的数组实现

      如同栈的情形一样,对于队列而言任何的表的实现都是合法的。像栈一样,对于每一种操作,链表实现和数组实现都给出快速的O(1)运行时间。

      对于每一个队列数据结构,我们保留一个数组theArray以及位置front和back,它们代表队列的两端。我们还要记录存在于队列中的元素的个数currentSize。

      循环数组(circular array)实现:只要front或back到达数组的尾端,它就又绕回到开头。实现回绕所需要的附加代码是极小的(不过它可能使得运行时间加倍)。如果front或back增1导致超越了数组,那么其值就要重置到数组的第一个位置。


    在保证enqueue的次数不会大于队列容量的应用中,使用回绕是没有必要的。像栈一样,除非主调例程肯定非空,否则dequeue很少执行。


    队列的应用

      打印机任务排队;

      购票窗口排队;

      电话通话排队;

      等等。



    展开全文
  • 抽象数据类型ADT(栈与队列)

    千次阅读 2018-06-04 19:38:28
    抽象数据类型 abstract data type,ADT:指只通过接口进行访问的数据类型,我们将那些使用ADT的程序叫做客户,将那些确定数据类型的程序叫做实现。数据的表示和实现操作函数都在接口的实现里面,和客户完全分离。接口...
  • 堆栈、队列、树应该是三种经典抽象数据类型,下面介绍一下队列队列是一种先进先出的结构,就像食堂排队一样,最先排的人最先打到饭,新入队的人排在队伍的最后,画了一个简单的图,如果用数组来模拟堆栈和队列,...
  • 抽象数据类型-队列

    2018-06-10 16:44:55
    队列模型:1.在表的末端插入元素(入队),在表的开头删除元素(出队),表的末端又叫队尾,表的开头又叫队头队列实现:1.数组实现:使用循环数组的方式来实现队列的插入和删除,具体实现如下-- 1.1定义一个数组theArray...
  • 确立队列的存储结构,建立队列并完成队列的基本操作的实现。 本程序可以在98/2000/XP下运行,可以用VC++6.0执行
  • 第11&12章 数据结构和抽象数据类型(Data Structure & Abstract Data Type) 教学目标通过本章的学习同学们应该能够:定义数据结构了解其分类抽象数据类型的定义熟练掌握栈和队列的原理及应用广义表的定义及操作树与...
  • 根据栈和队列抽象数据类型的定义,按要求实现一个栈或一个队列。 要求: 1、 实现一个共享栈 2、 实现一个链栈 3、 实现一个循环队列 4、 实现一个链队列
  • 队列实现循环队列

    千次阅读 2018-04-20 21:53:40
    二、实验内容仿照资料中顺序循环队列的例子,设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括:初始化、入队列、出队列、判断队列是否非空。编写主函数,验证所设计的顺序循环队列的正确性...
  • 三个【抽象数据类型抽象数据类型(ADT)一、列表 ADT1. 实现列表ADT的两种数据结构:数组(array-based)和链表(linked list)2. 链表的结构3. 操作:二、栈 ADT1. 插入和删除都在同一个地方(在top),First In ...
  • 实现循环队列,适合数据结构的小白~
  • 数据结构与算法分析---------抽象数据类型队列
  • 常见抽象数据类型

    千次阅读 2019-03-27 15:48:25
    从队尾入队列,从队头出队列 2、双端队列 结构:队头、队尾 特点:队头队尾均可入队/出队 3、优先级队列 三、树 1、二叉树 2、AVL树 3、伸展树 4、(2,4)树 5、红黑树 四、图 五、映射 1、哈希表 2、跳跃表 ...
  • 人们在使用计算机解决客观世界中存在的具体问题时,通常过程如下:首先通过对客观世界的认知形成印象和概念从而得到了信息,在此基础上... 数据结构主要与在上述过程中从建立概念模型到实现模型转化并为后续程序设...
  • 队列抽象数据类型 队列抽象数据类型由下面的操作定义。队列是结构化,有序的数据集,前端删除数据,后端加入数据,保持FIFO属性: Queue() 定义一个空队列,无参数,返回值是空队列。 enqueue(item) ...
  • 队列的定义队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的...队列抽象数据类型C语言中的定义 InitQuene(*Q):初始化操作,建立一个空队列Q DestroyQueue(*Q):若队列Q存在,则销毁它。 ClearQueue
  • Java中数组、集合、链表、队列数据结构和优缺点和他们之间的区别 数组: 长度固定 可以存储基本类型,也可以存储引用类型 存储元素类型一致 数组可以在内存中连续存储多个元素的构造,在内存中的分配也是连续的 ...
  • 抽象数据类型(abstract data type, ADT)是指只通过接口进行访问的数据类型。我们将那些使用ADT的程序叫做客户,将那些确定数据类型的程序叫做实现。 客户程序除了通过接口中提供的那些操作外,并不访问任何数据...
  • 数据结构之抽象数据类型

    千次阅读 2017-01-11 18:04:31
    抽象数据类型(Abstract Data Type 简称ADT) 定义:一个数学模型以及定义在该模型上的一组操作。 作用:抽象数据类型可以使我们更容易描述现实世界。 关键:使用它的人可以只关心它的逻辑特征,不需要了解它...
  • 注:分为四个内容:顺序栈、链栈、循环队列、链队列。代码由C++程序设计语言编写,包含栈和队列的基本操作(栈:出、入、取、判空等|队列:出、入、取、打印...本资源适合数据结构初学者和期末复习等,代码仅供参考。
  • //队列的顺序存储(循环队列) #include<stdio.h> #include<stdlib.h> #define Maxsize 10 typedef struct{ int data[Maxsize]; int front,rear; }SqQueue; void InitQueue(SqQueue &Q){//初始化队列 ...
  • 抽象数据类型(abstract data type,ADT)是指一个数学模型以及定义在该模型上的一组操作。 ADT 抽象数据类型名{ 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> ...
  • 数据结构循环队列.CPP

    2020-12-24 13:02:43
    循环队列
  • 用C语言实现了常见的抽象数据类型线性表 栈 队列 二叉树 广义表 串 内部排序 二元组等,
  • 考研或自学数据结构1.11. 知识框架2. 什么是数据3. 数据结构基本概念3.1 数据元素、数据项3.2 数据结构、数据对象4.数据结构的三要素4.1 逻辑结构4.1.1 集合4.1.2 线性结构4.1.2 树形结构4.1.4 图结构4.2 数据的物理...
  • 数据元素,结点,数据类型,抽象数据类型抽象数据类型的实现、以及对新定义的数据结构的应用等 知识通过下述 java代码 的形式 串联起来 , 以从宏观上对数据结构有一个透彻的理解和认识。  我们要使用...
  • 抽象数据类型(ADT)

    千次阅读 2016-04-19 09:39:12
    一、什么是抽象数据类型?用来做什么? ADT是指一个数学模型以及定义在该模型上的操作(即数学模型+数学模型的操作)。难理解,那就先说说类型。一个类型指两类信息:一个属性集+一个操作集),比如,int类型的属性...
  • 通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 115,097
精华内容 46,038
关键字:

队列的抽象数据类型