数据结构之链表与数组(一)—数组实现队列
一、数组与链表简介
对于一组数据,在计算机的内存中的存储形式可以分为连续存储和离散存储两种,它们对应了我们通常所说的数组和链表。当内存空间中有足够大的连续空间时,可以把数据连续的存放在内存中,各种编程语言中的数组一般都是按这种方式存储的;当内存中只有一些离散的可用空间时,为了能把这些空间中存储的数据联系起来,需要在前一块数据的存储空间中记录下一块数据的地址,这样只要知道第一块内存空间的地址就能环环相扣地把数据集整体联系在一起了, 这便是链表存储数据的方式。
由于数组是连续存储的,在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据,但是如果要在数据组中任意位置上插入一个元素,就需要先把后面的元素集体向后移一位为其空出存储空间。与之相反,链表是离散存储的,所以在插入一个数据时只要申请一片新空间,然后将其中的连接关系做一个修改就可以,但是显然在链表上查找一个数据时就要逐个遍历了。考虑以上的总结可见,数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组;当对数据集中的数据进行添加或删除比较多时最好选择链表。
二、数组实现队列
下面通过数组对数据进行操作,主要功能有:
1、在队列末尾添加数据;
public void add(Object obj) { // 实例化一个新数组对象,其长度比原数组大一 Object[] arr2 = new Object[arr.length+1]; //将原来的数组复制到新的数组 for(int i=0;i<arr.length;i++){ arr2[i] = arr[i]; } //在arr2数组的最后添加obj arr2[arr.length-1] = obj; //覆盖原数组 arr = arr2; }
2、从队列中取指定位置的数据;
public Object get(int index) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ //提示错误 System.out.println("index= "+index+" 超出队列范围"); } //返回该数据 else{ return arr[index-1]; } }
3、删除队列中指定位置的数据,并且返回被指定删除的数据;
public Object remove(int index) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ //提示错误 System.out.println("index= "+index+" 超出队列范围"); } else{ //新建一个数组 Object[] arr2 = new Object[arr.length-1]; //将该数据保存 Object a = arr[index-1]; //把要删除的数据之前的数据复制到新数组 for(int i = 0 ; i < index; i++){ arr2[i] = arr[i]; } //将之后的数据复制到新数组 for(int i = index-1;i < arr2.length;i++){ arr2[i] = arr[i+1]; } //覆盖原数组 arr = arr2; //返回被删除的数据 return a; } }
4、插入数据到队列中的某个位置;
//将数据obj插入到队列的index位置 public void inser(int index, Object obj) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ System.out.println("index= "+index+" 超出队列范围"); } else{ Object[] arr2 = new Object[arr.length+1]; //复制index位置前的数据 for(int i = 0 ; i < index-2;i++){ arr2[i] = arr[i]; } //复制index位置后的数据 for(int i = index; i < arr.length;i++){ arr2[i] = arr[i]; } //插入新数据 arr2[index-1] = obj; //覆盖原数组 arr = arr2; } }
5、返回原队列中数据的长度;
public int size() { // TODO Auto-generated method stub return arr.length; }
以上为自己定义的数组实现队列,此外,我们仍可以使用Java中已定义好的ArrayList类来对队列数据进行操作,此处不详细介绍。
相关推荐
本篇文章将深入探讨如何用数组和链表两种数据结构来实现队列。 ### 数组实现队列 数组实现队列的优势在于访问速度快,因为数组是连续存储的,可以通过下标直接访问元素。但数组的大小是固定的,所以在创建时需要...
本话题主要探讨了两种常用的数据结构——数组和链表——在实现队列这一线性数据结构时的应用。队列是一种先进先出(First In First Out, FIFO)的数据结构,它的主要操作包括入队(enqueue)、出队(dequeue)以及...
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
### 循环链表队列与循环数组队列的代码实现解析 在计算机科学中,队列是一种重要的数据结构,遵循先进先出(FIFO)原则。队列可以使用多种方式实现,包括链表和数组。本文将深入探讨两种队列实现方式:循环链表队列...
数组、链表、队列、栈数据结构特点,各自优点和缺点 在计算机科学中,数据结构是指用于组织和存储数据的方式。常见的数据结构包括数组、链表、队列、栈等。每种数据结构都有其特点、优点和缺点,本文将对这些数据...
链表是一种线性数据结构,与数组不同,它的元素在内存中不是连续存储的。链表由一系列节点组成,每个节点包含数据和指向下一个节点的引用。链表分为单向链表、双向链表和循环链表等类型,它们各有优缺点,如单向链表...
这种数据结构通常用在需要频繁添加或删除元素的场景,例如在实现栈、队列或者在处理不确定数量的数据时。 在这个高效数据管理类中,可能采用了类似“动态数组”的机制,当链表节点数超过一定阈值时,会转换为数组...
"go语言通过数组和链表的方式实现队列" 从给定的文件信息中,我们可以生成以下知识点: 1.队列的定义:队列是一种特殊的线性表,只能在队列的尾部添加元素,在队列的头部删除元素,先进先出(FIFO)。 2.go语言中...
在队列的代码中,引用了链表的代码
在C语言中,数组形链表是一种特殊的数据结构,它结合了数组的高效访问和链表的灵活扩展性。这种数据结构通常用于处理动态数组,其中元素可以方便地添加或删除,而不需要像传统数组那样预先知道确切的大小。本文将...
在数据结构中,数组、链表、队列、栈是四种常用的数据结构,它们之间有着紧密的联系,但同时也存在着许多区别。本文将详细介绍数组、链表、队列、栈的区别和联系。 一、数组和链表的区别 数组和链表都是线性表数据...
本主题将深入探讨线性表、链表、队列、栈这四种基本的数据结构,并以C++语言为例,通过相关源代码(stringData.cpp、seqList.cpp、node.cpp、seqQueue.cpp、linkQueue.cpp、linkStack.cpp、seqStack.cpp)来解析其...
数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数据结构是计算机科学中的一门重要学科,它研究的是计算机中数据的组织、存储和处理方式。数据结构可以分为逻辑结构和物理结构两种。 逻辑结构是指...
2. **链表**(Linked List):链表是一种动态数据结构,每个元素(节点)包含数据和指向下一个节点的指针。链表分为单向链表和双向链表。单向链表只能按顺序访问,而双向链表支持前向和后向遍历。链表的优点在于可以...
队列和数组是另外两个重要的数据结构,队列是一种特殊的线性表,数组是一种常用的数据结构。队列的特点是先进先出(FIFO),数组是一种可以存储多个元素的数据结构。 栈、队列和数组是C语言数据结构中的三个基本...
链表还适用于实现某些特定的数据结构,如堆栈、队列和图形数据结构。 在编程语言中,数组通常被内置支持,易于理解和使用,而链表则通常需要通过指针和结构体等概念来实现,相对复杂。但考虑到其灵活性,链表在处理...
链表是一种线性数据结构,与数组不同,它不连续存储元素。每个元素称为节点,包含数据和指向下一个节点的引用(或指针)。链表有多种类型,如单向链表、双向链表和循环链表。在单向链表中,每个节点只能向前指向一个...
数组、链表、堆栈和队列是最基本的数据结构,任何程序都会涉及到其中的一种或多种。数据结构是指数据之间的相互关系,即组织形式,有逻辑结构和物理结构之分。逻辑结构有线性和非线性之分,而物理结构则是描述数据在...