数据结构（1）线性结构——数组、链表、堆栈、队列（介绍和JAVA代码实现）

矫情吗；* 2023-09-23 14:50 94阅读 0赞

**目录**

1.1.线性表

1.1.1.数组

1.逻辑简介

2.代码实现

1.1.2.链表

1.逻辑简介

2.代码实现

1.2.堆栈

1.2.1.逻辑简介

1.2.2.代码实现

1.3.队列

1.3.1.逻辑简介

1.3.2.代码实现

1.4.性能对比

--------------------

## 1.1.线性表 ##

线性表是指由同种元素构成的有序且线性的一种数据结构，由于其有序且线性的特点，可以抽象出对其的一个操作集：

ElementType findKth(int k)//查找位序为K的元素
    int find(ElementType e)//查找元素e出现的第一次位置
    void insert(ElementType e,int i)//在位序i前面插入一个元素
    void delete(int i)//删除位序i的元素
    int length()//返回线性表的长度

线性表的实现有两种：

*  数组
 *  队列

### 1.1.1.数组 ###

#### 1.逻辑简介 ####

数组操作中要注意的操作是在中间插入或者删除，要涉及元素的位移。

**在数组中间删除：**

删除数组中间某个位置的元素，为了保持连续，后面的元素要挨个前移。

![dd9156e36b7348438c2bfda3179da316.png][]

**在数组中间插入：**

在数组中间某个位置插入元素，首先要腾出位置，也就是说，该位置后面的元素要挨个后移

![c9a50f12f0674a50b64473f76c6c07be.png][]

#### 2.代码实现 ####

使用代码实现顺序表：

public class Array{
    	//数组
        private Object[] array;
        private int maxSize;
        //初始化一个空数组
        public void initArray(int maxSize){
            this.maxSize=maxSize;
            array=new Object[maxSize];
        }
        //查找位序为K的元素
        public  Object findKth(int K){
            return array[K];
        }
        //查找元素X第一次出现的位置
        public  int find(Object X){
            int i=0;
            while(!X.equals(array[i])){
                i++;
            }
            return i;
        }
        //查找最后一个非空元素位置的位序
        public int findLastTh(Object[] targetArray){
            int i=0;
            for (int j=0;j<targetArray.length;j++){
                if(array[j]!=null){
                    i=j;
                }
            }
            return i;
        }
        //在i位序插入一个元素
        public void insert(Object X,int i){
            System.out.println("当前数组的容量:"+array.length);
            //判断是否存满，是否需要追加空间。
            if(isFull()){
                newSpace();
            }
    
            //若插入位置上没有元素则直接插入
            if(array[i]==null){
                array[i]=X;
            }
            else
            //若插入位置上有元素则当前位置开始顺序后移一位
            {
                for (int j = findLastTh(array); j >= i; j--) {
                    array[j + 1] = array[j];
                }
                array[i] = X;
            }
        }
        //判断数组是否已经存满
        public boolean isFull(){
            return array[array.length-1]!=null ? true:false;
        }
        //为数组开辟新空间
        public void newSpace(){
            //copy原数组
            Object[] tempArry=this.array;
                //记录原数组
            //追加新空间,追加容量为初始化容量的一倍
            array=new Object[maxSize+maxSize];
            //将原数组元素，copy到新数组
            for (int i=0;i<=findLastTh(tempArry);i++){
                  array[i]=tempArry[i];
                }
            System.out.println("扩容后数组容量:"+array.length);
        }
    
        //打印表中所有元素
        public void print() {
            int i=0;
            String s="";
            while (i<=findLastTh(array)) {
                s=s+i+":"+array[i]+"\t";
                i++;
            }
            System.out.println(s);
        }
    }

### 1.1.2.链表 ###

#### 1.逻辑简介 ####

链表操作中要注意的操作是在中间插入或者删除，要涉及指针的操作。

**在链表中间删除：**

在链表中间删除一个元素，即将该元素前一个节点的指针指向要删除节点的下一个节点，即要删除节点的指针所指向的位置，然后将要删除的节点的指针指向空。

![f59581ab720347cb8cd65aae0b41a296.png][]

#### 2.代码实现 ####

链表中的每个节点：

public class Node{
            //数据域
            Object data;
            //指针域
            Node next;
    
            public Object getData() {
                return data;
            }
    
            public void setData(Object data) {
                this.data = data;
            }
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
    }

使用链表实现顺序表：

public class List {
        //节点
        public class Node{
            //数据域
            Object data;
            //指针域
            Node next;
    
            public Object getData() {
                return data;
            }
    
            public void setData(Object data) {
                this.data = data;
            }
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
        }
    
        //尾指针
        Node last;
    
        //遍历指针
        Node flag;
    
        //头节点
        Node header;
    
        //初始化头节点
        //初始化末尾指针
        public List(){
            this.header=new Node();
            this.header.setData("header");
            this.last=header;
        }
    
        //插入
        public void insert(Object data){
            Node newNode=new Node();
            newNode.setData(data);
            last.setNext(newNode);
            //指针后移
            last=newNode;
        }
    
        //指定位置插入
        //插入在指定节点的后面
        //header位序为0，依次类推
        //此方法无法实现直接挂在末尾，挂在末尾请用上面的无参insert()
        public void insert(int X,Object data){
            //遍历指针指向头节点
            this.flag=header;
            //计数器
            int i=0;
    
            Node newNode=new Node();
            newNode.setData(data);
    
            //查找动作
            while(i<X){
                flag=flag.getNext();
                i++;
            }
            //删除动作
            //后面节点挂在当前节点后
            newNode.setNext(flag.getNext());
            //当前节点挂在目标节点后
            flag.setNext(newNode);
        }
    
        //遍历打印链表
        public void printf(){
            //遍历指针指向头节点
            this.flag=header;
            //消息
            String message="";
            while (flag.getNext()!=null){
                message=message+flag.getData()+"—>";
                flag=flag.getNext();
            }
            //拼接最后一个节点
            message=message+flag.getData()+"—>";
    
            System.out.println(message);
        }
    
        //删除指定位序节点
        public void delete(int X){
            //遍历指针指向头节点
            this.flag=header;
            //计数器
            int i=0;
    
            //查找动作
            while(i<X-1){
                flag=flag.getNext();
                i++;
            }
    
            //删除动作
            flag.setNext(flag.getNext().getNext());
    
        }
    }

## 1.2.堆栈 ##

### 1.2.1.逻辑简介 ###

堆栈，一种后入先出（LIFO，last in frist out）或者叫先入后出（FILO，first in last out）的线性且有序的数据结构。

![3a26f7042a154f4a8d5ec0d8e262fe2a.png][]

堆栈的操作集可抽象为：

Boolean isFull();//判断堆栈是否已满
    Boolean isEmpty();//判断堆栈是否为空
    void push();//入栈
    void pop();//出栈

### 1.2.2.代码实现 ###

此处的代码实现以数组来存储数据，数组进行出入堆栈的时候会涉及位移操作，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。

public class Stack {
        //数据域
        Object[] stack;
        //头指针
        int first=0;
        //尾指针
        int last=-1;
    
        public Stack(int size){
            stack=new Object[size];
        }
    
        //判断堆栈是否已满
        public Boolean isFull(){
            return (stack.length-1)==last;
        }
    
        //判断堆栈是否为空
        public Boolean isEmpty(){
            return last==-1;
        }
    
        //入栈
        public void push(Object o){
            if(!isFull()) {
                stack[++last] = o;
            }
        }
    
        //出栈
        public Object pop(){
            Object data=null;
            if(!isEmpty()) {
                data=stack[last];
                stack[last] = null;
                last--;
            }
            return data;
        }

## 1.3.队列 ##

### 1.3.1.逻辑简介 ###

队列，一种先进先出（FIFO，first in first out）或者叫后进后出（LILO，last in last out）的线性且有序的数据结构。

队列的理解不难，就像我们生活中排队时的各种队列一样，就是先进先出，后进后出。

![48c2caf152ed4afc8b358ee57190d867.png][]

队列的操作集可抽象为：

Boolean isFull();//判断队列是否已满
    Boolean isEmpty();//判断队列是否为空
    void push();//入队
    void pop();//出队

### 1.3.2.代码实现 ###

此处的代码实现以数组来存储数据，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。

public class Queue {
        //数据域
        Object[] stack;
        //头指针
        int first=0;
        //尾指针
        int last=-1;
    
        public Queue(int size){
            stack=new Object[size];
        }
    
        public Boolean isFull(){
            return (stack.length-1)==last;
        }
    
        public Boolean isEmpty(){
            return last==-1;
        }
    
        public void push(Object o){
            if(!isFull()) {
                stack[++last] = o;
            }
        }
    
        public Object pop(){
            Object o=stack[first];
            //删除头元素，后续元素顺序前移
            stack[first]=null;
            if(!isEmpty()) {
                for (int i = 1; i <=last; i++) {
                    Object temp=stack[i];
                    stack[i-1]=temp;
                }
                stack[last--]=null;
            }
            return o;
        }
    }

## 1.4.性能对比 ##

从链表和数组的结构特点和使用过程中可以看到，数组和链表在增删改查各个场景中性能各有优劣：

*  查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
 *  增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。

[dd9156e36b7348438c2bfda3179da316.png]: https://img-blog.csdnimg.cn/dd9156e36b7348438c2bfda3179da316.png
[c9a50f12f0674a50b64473f76c6c07be.png]: https://img-blog.csdnimg.cn/c9a50f12f0674a50b64473f76c6c07be.png
[f59581ab720347cb8cd65aae0b41a296.png]: https://img-blog.csdnimg.cn/f59581ab720347cb8cd65aae0b41a296.png
[3a26f7042a154f4a8d5ec0d8e262fe2a.png]: https://img-blog.csdnimg.cn/3a26f7042a154f4a8d5ec0d8e262fe2a.png
[48c2caf152ed4afc8b358ee57190d867.png]: https://img-blog.csdnimg.cn/48c2caf152ed4afc8b358ee57190d867.png