计算机中两种基本的数据结构式数组及链表，前者是在自然顺序的内存中存储数据，而后者是通过其基本单元——节点的数据域和指针域来存储数据和记录数据间的相对位置，概括地说：数组中的数据位置是连续的，链表中的数据位置是离散的。
这就决定了，在数组中找一个数据很容易（只需知道数组首地址及数据在数组中的位置）；而在链表中改变数据的相对位置很容易（只需改变个别节点的指针域就行）。他们各有优势，也各有劣势，并且优势与劣势恰好相反。
正是这一不同决定了用他们来实现队列时，队列的优势与劣势。
队列的特点是可以改变长度（存储数据的个数），是一种比较理想的数据结构。我们常常要对它进行“增删查改”的工作，或者更根本地说是“找”与“变”的工作。“找”就是找到索引位置的数据，数组队列非常擅长，
“变”就是改变数据间的相对位置关系，链表队列非常擅长。而当我们“变”数组队列时，往往要频繁地新建数组并逐个赋值；当我们“查”链表队列中的数据时，往往要遍历队列，工作量很大。
总之两者各有千秋，适合用于各自擅长的场合，使用时要根据情况灵活选取
传上我的队列实现代码：
/**
* 队列的接口，定义一些使用方法
* @author 朱凌峰
*
* @param <E> 泛型
*/
public interface MyQueue<E> {
//在队列末尾加上一个数据
public void add(E e);
//在队列中指定位置插入一个数据
public void insert(E e,int index);
//取出指定位置的一个数据
public E get(int index);
//删除指定位置的一个数据
public void remove(int index);
//改变指定位置的数据
public void set(E e,int index);
//获取队列长度
public int size();
//按顺序打印队列中的每个数据
public void printQueue();
//检验索引位置是否越界，如越界，则抛出异常
public boolean judgeIndex(int index);
}
/**
* 定义我自己的数组队列
*
* @author 朱凌峰
*
*/
public class MyArrayList<E> implements MyQueue<E> {
private Object[] dataArray;// 用于存储数据的数组
int lengthIncreaseStep;// 每次数组长度增加的步长
int countData = 0;// 数据个数计数器
/**
* 默认构造方法 默认数组初始长度为10，每次数组长度增加的步长为10
*/
public MyArrayList() {
this(10, 10);
}
/**
* 设定数组初始长度的构造方法
*
* @param initLength
* 数组的初始长度
*/
public MyArrayList(int initLength) {
this(initLength, 10);
}
/**
* 设定数组初始长度和每次数组长度增加的步长的构造方法
*
* @param initLength
* 数组初始长度
* @param lengthIncreaseStep
* 数组长度增加的步长
*/
public MyArrayList(int initLength, int lengthIncreaseStep) {
this.lengthIncreaseStep = lengthIncreaseStep;
this.dataArray = new Object[initLength];
}
/**
* 添加一个数据到队列的末尾
*
* @param msAdd
* 要添加的数据
*/
@Override
public void add(E e) {
// 如果数据个数等于当前数组长度
if (countData == dataArray.length) {
// 新建加长长度的数组
Object[] lengthenedArray = new Object[this.dataArray.length
+ this.lengthIncreaseStep];
// 将原有数组里的数据从后往前逐个加入到新的数组中
for (int i = 0; i < dataArray.length; i++) {
lengthenedArray[i] = dataArray[i];
}
// 将添加的数据加入到新建数组中
lengthenedArray[dataArray.length] = e;
// 将新建数组指向原数组
dataArray = lengthenedArray;
} else {
dataArray[countData] = e;
}
countData++;
}
/**
* 在索引位置前面一个位置插入数据(若要插在最后一个数据后面，则用add方法)
*/
public void insert(E e, int index) {
if(this.judgeIndex(index)){
//将原来队列的最后一个数据添加到队列末尾
this.add(this.get(this.size()-1));
//将原来最后第二个数据至index向后移动一位
for(int i =this.size()-3 ;i >=index;i--){
this.set(this.get(i), i+1);
}
//将index位置设置为新插入的数据
this.set(e, index);
}
}
/**
* 获取队列中指定位置的数据
*
* @param index
* 数据在队列中的位置
* @return 指定位置的数据
*/
public E get(int index) {
// 检查index是否有效
if (judgeIndex(index)) {
return (E) dataArray[index];
}
return null;
}
/**
* 移除索引位置对应的数据
* @param index 索引位置
*/
public void remove(int index) {
if(this.judgeIndex(index)){
for (int i = index; i < this.size()-1; i++) {
dataArray[i]=dataArray[i+1];
}
this.countData--;
}
}
/**
*设置索引位置的数据值
*@param e 数据值
*@param index 索引位置
*/
public void set(E e, int index) {
// 检查index是否有效
if (judgeIndex(index)) {
this.dataArray[index] = e;
}
}
/**
* 获取队列的长度
*
* @return 一个整数表示队列长度
*/
public int size() {
return countData;
}
/**
* 按顺序打印队列中的每个数据，若队列为空则抛出异常
*/
public void printQueue() {
if(this.size()==0)
throw new java.lang.RuntimeException("队列为空");
else {
for (int i = 0; i < this.size(); i++) {
System.out.println("队列中第"+i+"个数据为："+this.get(i));
}
}
}
/**
* 判断索引位置是否有效,若索引位置有效，则返回true,否则抛出异常
*
* @param index
* 索引位置
* @return 若索引位置有效，则返回true
*/
@Override
public boolean judgeIndex(int index) {
// 判断索引位置是否有效
if (index < 0 || index >= this.size()) {
throw new java.lang.RuntimeException("索引位置" + index + "越界："
+ ",当前队列大小为：" + this.size());
}
return true;
}
/**
* 将一个队列添加到当前队列的末尾
* @param arrayList 要添加到末尾的队列
*/
public void addAll(MyArrayList<E> arrayList){
//新建一个长度为当前队列和要添加到末尾的队列长度之和的数组
Object[] tempArray=new Object[this.size()+arrayList.size()];
//将当前队列的每个数据一次添加到临时数组中
for (int i = 0; i < this.size(); i++) {
tempArray[i]=dataArray[i];
}
//将 要添加到末尾的队列中的每个每个数据添加到临时数组中
for (int i = 0; i < arrayList.size() ; i++) {
tempArray[i+this.size()]=arrayList.get(i);
}
//将原有数组指向临时数组
dataArray=tempArray;
//重新设置数据个数
countData=this.size()+arrayList.size();
}
}
/**
* 链表的节点类
* @author 朱凌峰
*
* @param <E>
*/
public class LinkNode<E> {
//节点的数据
private E data;
//当前节点的子节点
private LinkNode<E> child;
private LinkNode<E> parent;//当前节点的父节点
/**
* 带参构造器
* @param data 创建对象时赋予的初始参数
*/
public LinkNode(E data){
this.data=data;
}
/**
* 获取当前节点的数据
* @return
*/
public E getData(){
return this.data;
}
/**
* 重新赋予节点数据的值
* @param data 重新赋予的值
*/
public void setData(E data){
this.data=data;
}
/**
* 设置父节点
* @param parent
*/
public void setParent(LinkNode<E> parent){
this.parent=parent;
}
/**
* 设置子节点
* @param child
*/
public void setChild(LinkNode<E> child){
this.child=child;
}
/**
* 获取当前节点的付节点
* @return
*/
public LinkNode<E> getParent(){
return this.parent;
}
/**
* 获取当前节点的子节点
* @return
*/
public LinkNode<E> getChild(){
return this.child;
}
}
package LinkNode20130717;
import zlfsQueue20130714and0716and0722.MyQueue;
/**
* 用链表实现队列
* @author 朱凌峰
*
*/
public class LinkQueue<E> implements MyQueue<E>{
//根节点
private LinkNode<E> root;
//最后一个节点
private LinkNode<E> last;
/**
* 在队列末尾添加一个数据
* @param e 要添加的数据
*/
public void add(E e){
//新建一个节点
LinkNode<E> tempNode=new LinkNode<E> (e);
//如果队列中还没有节点，则新建一个根节点
if(root==null){
root=tempNode;
//此时最后一个节点即为根节点
last=root;
}else{
last.setChild(tempNode);//该节点为上一个节点的子节点
tempNode.setParent(last);
//该节点成为当前的最后一个节点
last=tempNode;
}
}
/**
* 获取指定位置节点的数据
* @param index 数据所在位置，根节点的位置为0
* @return
*/
public E get(int index){
LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
return nodeOfIndex.getData();
}
/**
* 获取链表队列的大小，即数据个数
* @return
*/
public int size(){
int count=0;
LinkNode<E> tempNode=root;
while(tempNode!=null){
count++;
tempNode=tempNode.getChild();
}
return count;
}
/**
* 删除指定位置的数据
* @param index
*/
public void remove(int index){
LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
//如果删除根节点
if(index==0){
//获取索引位置的节点的子节点
LinkNode<E> tempChild=nodeOfIndex.getChild();
root=tempChild;
}
//如果删除最后一个节点
else if(index==this.size()-1){
//获取索引位置的节点的父节点
LinkNode<E> tempParent=nodeOfIndex.getParent();
tempParent=last;
}
else {
//获取索引位置的节点的父节点和子节点
LinkNode<E> tempParent=nodeOfIndex.getParent();
LinkNode<E> tempChild=nodeOfIndex.getChild();
//重新设置父子关系
tempParent.setChild(tempChild);
tempChild.setParent(tempParent);
}
}
/**
* 重新设置指定位置的数据值
* @param e
* @param index
*/
public void set(E e,int index){
LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
nodeOfIndex.setData(e);
}
/**
* 获取索引位置对应的节点
* @param index 索引位置
* @return 索引位置对应节点
*/
private LinkNode<E> getNodeOfIndex(int index){
if(this.judgeIndex(index)){
//找到索引位置对应的节点
int count = 0;
LinkNode<E> tempNode=root;
while(count!=index){
tempNode=tempNode.getChild();
count++;
}
return tempNode;
}
return null;
}
/**
* 依次打印队列中每个数据
*/
public void printLinkQueue(){
if(root==null){
throw new java.lang.RuntimeException("队列为空");
}
else{
int count = 0;
LinkNode<E> tempNode=root;
while(tempNode!=null){
System.out.println("队列中第"+count+"个数据为："
+tempNode.getData());
tempNode=tempNode.getChild();
count++;
}
}
}
/**
* 插入一个数据到索引位置前面一个位置
* @param e 要插入的数据
* @param index 索引位置
*/
public void insert(E e, int index) {
if (judgeIndex(index)) {
// 新建临时节点保存要插入的数据
LinkNode<E> tempNode=new LinkNode<E>(e);
if(index==0){
// 设置当前根节点和临时节点的父子关系
root.setParent(tempNode);
tempNode.setChild(root);
// 根节点为临时节点
root=tempNode;
}
else {
tempNode.setChild(this.getNodeOfIndex(index));
tempNode.setParent(this.getNodeOfIndex(index-1));
this.getNodeOfIndex(index).setParent(tempNode);
this.getNodeOfIndex(index-1).setChild(tempNode);
}
}
}
/**
* 按顺序打印队列中的每个数据，若队列为空则抛出异常
*/
public void printQueue() {
if(this.size()==0)
throw new java.lang.RuntimeException("队列为空");
else {
for (int i = 0; i < this.size(); i++) {
System.out.println("队列中第"+i+"个数据为："+this.get(i));
}
}
}
/**
* 将一个队列添加到当前队列末尾
* @param linkQueue 要添加到末尾的队列
*/
public void addAll(LinkQueue<E> linkQueue) {
this.last.setChild(linkQueue.root);
linkQueue.root.setParent(this.last);
}
/**
* 判断索引位置是否有效
* @param index 索引位置
* @return 若索引位置有效，则返回true
*/
public boolean judgeIndex(int index) {
//判断索引位置是否有效
if(index<0 || index>=this.size()){
throw new java.lang.RuntimeException("索引位置越界："+index
+",当前队列大小为："+this.size());
}
return true;
}
}
相关推荐
数据结构课程设计中，主题是实现一个基于数组链表的数据结构来统计文本中特定单词的出现次数和位置。这个程序被称为“文学研究助手”，旨在帮助研究人员统计英文小说中指定单词的频率及其在文中的位置。以下是对这个...
本话题主要探讨了两种常用的数据结构——数组和链表——在实现队列这一线性数据结构时的应用。队列是一种先进先出（First In First Out, FIFO）的数据结构，它的主要操作包括入队（enqueue）、出队（dequeue）以及...
今天，我们将讨论如何使用数组来模拟链表，并实现链表的插入和遍历操作。 首先，我们需要了解链表的基本结构。链表是一种动态的数据结构，每个结点都包含两个部分：数据域和指针域。数据域存储当前结点的值，而指针...
"go语言通过数组和链表的方式实现队列" 从给定的文件信息中，我们可以生成以下知识点： 1.队列的定义：队列是一种特殊的线性表，只能在队列的尾部添加元素，在队列的头部删除元素，先进先出（FIFO）。 2.go语言中...
本资料包“数据结构的学习——数组和链表.zip”着重讲解了两种基本的数据结构：数组和链表，它们在编程中扮演着核心角色，特别是在处理大量数据时。 数组是一种线性数据结构，其中的元素存储在内存中的连续位置。...
队列可以使用数组或者链表来实现，队列的应用场景非常广泛，如购物队列、打印队列等。 线性表是具有n个数据元素的有限序列，線性表的数据元素可以由若干个数据项组成。線性表有顺序存储结构和非顺序存储结构两种...
本篇文章将深入探讨如何用数组和链表两种数据结构来实现队列。 ### 数组实现队列 数组实现队列的优势在于访问速度快，因为数组是连续存储的，可以通过下标直接访问元素。但数组的大小是固定的，所以在创建时需要...
队列可以使用数组或链表实现，数组实现的队列可以快速地随机访问元素，而链表实现的队列可以快速地插入或删除元素。 栈是一种后进先出（Last-In-First-Out，LIFO）的数据结构，元素的添加和删除都是从栈顶进行的。...
在计算机科学中，大数（Big Number）是指那些超过普通整型或浮点型...无论是链表还是数组，实现大数运算都需要对位操作、进位/借位规则以及数据结构的特性有深刻理解。这不仅是理论知识的运用，也是编程技巧的实践。
本文将深入探讨Java中实现动态数组链表的关键概念、操作以及其实现方式。 首先，数组是一种线性数据结构，其中元素存储在连续的内存位置，可以通过索引来访问。然而，数组的大小在创建时通常是固定的，如果需要添加...
* 复杂性：动态数组链表的实现较为复杂，需要考虑到数组的扩展和缩小、链表的插入和删除等操作。 * 空间浪费：虽然动态数组链表可以避免空间浪费，但是在实际应用中可能会出现空间浪费的情况。 应用场景 动态数组...
在Python中，列表是使用链表结构实现的，但是在某些情况下，也可以使用数组结构来实现。那么，为什么Python列表要使用链表结构，而不使用数组结构呢？ 在讨论这个问题之前，我们需要了解什么是数据结构和具体数据...
本篇文章主要探讨的是两种基本的数据结构——数组与链表。通过对比它们的特点、优缺点以及适用场景，帮助读者更好地理解何时选择哪种数据结构更为合适。 #### 数组与链表概述 **数组**是一种常见的数据结构，它是...
在Java中，HashMap的实现方式有多种，本文将介绍使用数组和链表的方式简单实现HashMap的增删改功能。 HashMap的数据结构 HashMap的数据结构主要由三个部分组成：数组、链表和红黑树。数组用于存储键值对，链表用于...
数组、链表、队列、栈数据结构特点，各自优点和缺点 在计算机科学中，数据结构是指用于组织和存储数据的方式。常见的数据结构包括数组、链表、队列、栈等。每种数据结构都有其特点、优点和缺点，本文将对这些数据...
超级数组和链表及栈队列
下面我们将详细介绍数组和链表的基本组成部分、特点和Java实现。 一、数组 数组是最常用的线性数据结构，数组中的元素类型是一样的，并且有序的。数组的特点是： * 数据是连续的 * 随机访问速度快 在Java中，...
在C++中，循环队列可以使用数组或者链表来实现，这两种方式各有优缺点。下面我们将详细探讨这两种实现方式及其基本功能。 首先，我们来看数组实现的循环队列。数组是最基础的数据结构，它的优点是访问速度快，空间...