1、 计算机中的存储方式可以大致分为两类：离散存储、有序存储。
其中的典型代表为链表和数组。
2、 数组的定义格式： 数据类型【】 数组名=new 数据类型【数组长度】；
数据类型【】 数组名={元素表}；
数据类型 数组名【】={元素表}；
java中的数组为定长，即在定义时必须给定数组的长度。
由于数组是按顺序存储，所以查找时可以直接根据数组中元素的下标获得所需数据。
3、 链表就像一条隐形的链子，一环扣一环。链表的基本单位是结点，每个结点包括两个部分：该结点中的存储的数据，以及所连接的下个结点。
链表中数据的查找则必须从头开始，依次通过每个结点获得它所连接的下个结点。
一个简单链表的实现可以用如下代码
//首先定义一个结点类
public class Node{
Object data;
Node next;
}
//通过结点的依次添加和连接获得一个链表
Node n1=new Node();
n1.data=所附的值；
Node n2=new Node();
n2.data=所附的值；
Node n3=new Node();
n3.data=所附的值；
... ...
n1.next=n2;
n2.next=n3;
... ...
由以上可以看出，如果使用链表直接存储数据，数据的添加过程将是一个非常繁琐的过程。但是使用队列优化后的链表使用起来就可以非常简单。
4、 队列也是一个存放东西的容器。但队列的使用比数组、链表更加灵活。一个完善的队列可以很方便的实现添加、删除、更改、获得长度、插入、查找等操作。因此通过把数组和链表转化为队列，可以实现对数组和链表的优化，增强其实用性。
以下是分别是用链表和数组实现队列的程序
/**
* 定义一个结点类
* @author 陈琳
* @param <E> 泛型标识，便于使用者向链表中传入不同类型的数据
*/
public class ListNode<E> {
private E data;
private ListNode<E> next;
/**
* 设置结点中所存储的数据
* @param e 要存入的数据
*/
public void setData(E e){
this.data=e;
}
/**
* 设置结点所连接的下个结点
* @param next 结点所连接的下个结点
*/
public void setNext(ListNode next){
this.next=next;
}
/**
* 获得结点中所存储的数据
* @return 结点中所存储的数据
*/
public E getData(){
return data;
}
/**
* 获得结点所连接的下个结点
* @return 结点所连接的下个结点
*/
public ListNode getNext(){
return next;
}
}
/**
* 定义一个以链表为基础的队列
* @author 陈琳
* @param <E>
*/
public class SingleLinkList<E> {
/**
* 用root表示链表上的第一个结点，last表示链表上的最后一个结点
*/
ListNode root;
private ListNode last;
/**
* 设置根节点
* @param e将根节点设置成的内容
*/
public void setRoot(ListNode e){
root=e;
}
/**
* 向链表中添加元素
* @param e添加的元素对象
*/
public void add(E e){
if(root==null){
root=new ListNode<E>();
root.setData(e);
last=root;
}else{
ListNode<E> tem=new ListNode<E>();
tem.setData(e);
last.setNext(tem);
last=tem;
}
}
/**
* 获得链表的长度
* @return 链表的长度
*/
public int size(){
if(root!=null) {
int t=1;
ListNode<E> tem=root.getNext();
while(tem!=null){
tem=tem.getNext();
t++;
}
return t;
}
return 0;
}
/**
* 根据索引值获得结点
* @param index 索引值
* @return 索引值所对应的结点
*/
public ListNode<E> getNode(int index){
if(this.size()<index||index<0){
System.out.println("下标越界");
return null;
}else{
ListNode<E> tem=root;
for(int i=1;i<index;i++){
tem=tem.getNext();
}
return tem;
}
}
/**
* 由节点中数据的值获得此结点所在的位置
* @param e 指定的结点的数据域的值
* @return 指定的结点在链表中的额位置
*/
public int getIndex(E e){
ListNode<E> tem=root;
int i=1;
for(;i<this.size();i++){
tem=tem.getNext();
while(tem.getData().equals(e)){
break;
}
}
return i;
}
/**
* 在指定位置插入结点
* @param index 链表中指定的位置
* @param e 插入的结点的数据域的值
*/
public void insert(int index,E e){
ListNode<E> newNode=new ListNode<E>();
if(index==1){
newNode.setData(e);
newNode.setNext(root);
root=newNode;
}else{
ListNode<E> tem=root;
for(int i=2;i<index;i++){
tem=tem.getNext();
}
newNode.setData(e);
newNode.setNext(tem.getNext());
tem.setNext(newNode);
}
}
/**
* 删除指定位置的结点
* @param index 指定的位置的索引值
*/
public void delete(int index){
if(index==1) root=root.getNext();
else{
ListNode<E> tem=root;
for(int i=2;i<index;i++){
tem=tem.getNext();
}
tem.setNext(tem.getNext().getNext());
}
}
/**
* 更改指定位置的结点的值
* @param index 指定结点的位置
* @param e 结点数据域的值需改为的值
*/
public void update(int index,E e){
ListNode<E> aimNode=this.getNode(index);
aimNode.setData(e);
}
/**
* 输出链表中各结点数据域的值
* @param root 根节点
*/
public void printSingleLinkList(ListNode<E> root){
ListNode<E> tem=root;
if(tem==null) return;
System.out.println(tem.getData()+" ");
tem=tem.getNext();
printSingleLinkList(tem);
}
}
/**
* 定义一个数组转化为的队列
* @author 陈琳
*/
public class ArrayQueue<E> {
private int initLength=100;
private int increaseLength=10;
static int count=0;
/**
* 用于传递数组初始长度和每次增加长度的构造器
* @param initLength 数组初始长度
* @param increaseLength 每次增加的长度
*/
public ArrayQueue(int initLength,int increaseLength){
this.initLength=initLength;
this.increaseLength=increaseLength;
}
/**
* 用于传递数组初始长度的构造器
* @param initLength 数组初始长度
*/
public ArrayQueue(int initLength){
this.initLength=initLength;
}
/**
* 不用传递任何数据的构造器
*/
public ArrayQueue(){
}
//初始化数组
Object[] initstr = new Object[initLength];
/**
* 向数组中添加元素
* @param e所添加的数据
*/
public void add(E e){
count++;
if(count>initstr.length){
Object[] temstr = new Object[initstr.length+increaseLength];
for(int i=0;i<initstr.length;i++){
temstr[i]=initstr[i];
}
initstr=temstr;
}
initstr[count-1]=e;
}
/**
* 获得数组中数据的个数
* @return 数据个数
*/
public int size(){
return count;
}
/**
* 通过索引值获得数组中的数据
* @param index 索引值
* @return 数组中的数据
*/
public E get(int index){
if(index<0||index>initstr.length){
System.out.println("下标越界");
return null;
}
return (E) initstr[index];
}
/**
* 向数组中插入元素
* @param index 插入的位置
* @param e 插入的数据
*/
public void insert(int index,E e){
if(index>count||index<0){
System.out.println("下角标越界");
return;
}
if(count>initstr.length){
Object[] temstr = new Object[initstr.length+increaseLength];
for(int i=0;i<initstr.length;i++){
temstr[i]=initstr[i];
}
initstr=temstr;
}
for(int i=count-1;i>=0;i--){
if(i!=index-1){
initstr[i+1]=initstr[i];
continue;
}
initstr[index]=e;
count++;
return;
}
}
/**
* 删除数组中指定的元素
* @param index 要删除的元素的位置
*/
public void delete(int index){
if(index>count||index<0){
System.out.println("下角标越界");
return;
}
for(;index<initstr.length-1;index++){
initstr[index]=initstr[index+1];
}
Object[] temstr = new Object[initstr.length-1];
for(int i=0;i<temstr.length;i++){
temstr[i]=initstr[i];
}
initstr=temstr;
count--;
}
/**
* 更改数组中的元素
* @param index 要更改的元素的位置
* @param e 要更改为的对象
*/
public void update(int index,E e){
initstr[index]=e;
}
/**
* 遍历并打印数组
*/
public void printArray(){
for(int i=0;i<count;i++){
System.out.print("initstr["+i+"]="+initstr[i]+", ");
if((i+1)%5==0)
System.out.println("");
}
System.out.println(""+"\n");
}
}
分享到：
相关推荐
本话题主要探讨了两种常用的数据结构——数组和链表——在实现队列这一线性数据结构时的应用。队列是一种先进先出（First In First Out, FIFO）的数据结构，它的主要操作包括入队（enqueue）、出队（dequeue）以及...
数组、链表、队列、栈的区别和联系 在数据结构中，数组、链表、队列、栈是四种常用的数据结构，它们之间有着紧密的联系，但同时也存在着许多区别。本文将详细介绍数组、链表、队列、栈的区别和联系。 一、数组和...
在队列的代码中，引用了链表的代码
数组、链表、队列、栈数据结构特点，各自优点和缺点 在计算机科学中，数据结构是指用于组织和存储数据的方式。常见的数据结构包括数组、链表、队列、栈等。每种数据结构都有其特点、优点和缺点，本文将对这些数据...
### 循环链表队列与循环数组队列的代码实现解析 在计算机科学中，队列是一种重要的数据结构，遵循先进先出（FIFO）原则。队列可以使用多种方式实现，包括链表和数组。本文将深入探讨两种队列实现方式：循环链表队列...
"go语言通过数组和链表的方式实现队列" 从给定的文件信息中，我们可以生成以下知识点： 1.队列的定义：队列是一种特殊的线性表，只能在队列的尾部添加元素，在队列的头部删除元素，先进先出（FIFO）。 2.go语言中...
本篇文章将深入探讨如何用数组和链表两种数据结构来实现队列。 ### 数组实现队列 数组实现队列的优势在于访问速度快，因为数组是连续存储的，可以通过下标直接访问元素。但数组的大小是固定的，所以在创建时需要...
虽然题目要求分析链表队列的实现，但给定的代码片段实际上是实现了基于数组的优先队列，而不是链表队列。这里简单分析一下这段代码的主要部分： #### 1. 基础函数定义 - `FixUp`: 调整堆使之满足大顶堆的性质。 - ...
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的，遵循先进先出原则的线性表。 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。 分解代码没有包含在内的代码如下： #include #...
- 队列：一种先进先出（FIFO）的数据结构，适用于任务调度等场景。 - 链表：如单向链表、双向链表和循环链表等。 - 栈：一种后进先出（LIFO）的数据结构，用于表达式求值、函数调用栈等。 #### 二、非线性结构 ...
- **链表的优势**：适合需要频繁进行插入和删除操作的应用场景，如任务队列管理等。 - **链表的劣势**：查询效率低，不适合需要频繁查询数据的场景。 #### 关于顺序表的改进 对于基于数组的顺序表，可以通过引入...
这种基于数组的队列虽然在空间效率上比链表实现的队列更优，但在动态扩展时可能涉及数组复制，性能相对较差。 在实际应用中，我们需要根据具体需求选择合适的数据结构。例如，对于大量并发插入和删除的操作，`...
* 链式存储结构：使用链表来存储队列的元素，不在本文中讨论。 3. 队列的实现： * 构造函数（MyQueue）：初始化队列，分配内存空间。 * 析构函数（~MyQueue）：释放队列占用的内存空间。 * 将队列置空...
数组、链表、堆栈和队列、线性表和顺序表 数组、链表、堆栈和队列是最基本的数据结构，任何程序都会涉及到其中的一种或多种。数据结构是指数据之间的相互关系，即组织形式，有逻辑结构和物理结构之分。逻辑结构有...
常见的数据结构（栈、队列、数组、链表和红黑树） 数组和链表.pdf
数据结构学习代码，内容包括：稀疏数组、队列、链表、栈、递归的使用、排序算法、查找算法、哈希表、树结构_DataStructure
队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，只允许在表的后端（rear）进行插入操作,下面介绍一下java使用数组和链表实现队列的示例