队列与栈一

线性表是最基本的数据结构之一，其最终的物理结构不外乎两种，顺序表与链表。队列与栈都是线性表，只是其外在的逻辑表现形式不同而已。

顺序表

顺序表是一种在物理上连续存储的结构，也即顺序表的元素在内存空间里是物理上连续的。

digraph array_list{

bgcolor="#f7f7f7"

subgraph cluster_array {


    node [shape=record, fontcolor=black,width=4.75, fixedsize=true];
    pointers[] [label="<p0> A+0 | <p1> A+1 | <p2> A+2 | <p3> A+3 | <p4> A+4 | <p5> A+5 | <p6> A+6 | <p7> A+7", color=blue];
    values [label="<v0> A[0] | <v1> A[1] | <v2> A[2] | <v3> A[3] | <v4> A[4] | <v5> A[5] | <v6> A[6] | <v7> A[7]", color=blue, fillcolor=lightblue, style=filled];
    indices [label="0 | 1 | 2 | 3| 4 | 5 | 6 | 7", color="#f7f7f7"];

    node [shape=plaintext, fontcolor="black",width=1 fontsize=18,fixedsize=true];
    "Pointers:" -> "Values:" -> "Indices:"[color="#f7f7f7"];

    { rank=same; "Pointers:"; pointers }
    { rank=same; "Values:"; values }
    { rank=same; "Indices:"; indices }   
}

label = <<B>图 1.1 顺序表</B>>

}

链表

链表是一种在逻辑空间上连续，但是物理空间上离散的线性表。链表前后节点使用指针相连，因此与线性表相比，链表需要更多的存储空间，但是却能更有效的利用空间，因为顺序表对存储要求必须是物理上一整块的空间。

digraph list_linked {

bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    n0 [label="{<data>A[0]|<next>}" shape=record,color=blue,fillcolor=lightblue,style=filled]
    n1 [label="{<data>A[1]|<next>}" shape=record,color=blue,fillcolor=lightblue,style=filled]
    n2 [label="{<data>A[2]|<next>}" shape=record,color=blue,fillcolor=lightblue,style=filled]
    n3 [label="{<data>A[3]|<next>}" shape=record,color=blue,fillcolor=lightblue,style=filled]
    n4 [label="{<data>A[4]|<next>nil}" shape=record,color=blue,fillcolor=lightblue,style=filled]
 
    n0:next:0 -> n1:data [tailclip=false,solid=true]
    n1:next:0 -> n2:data [tailclip=false,solid=true]
    n2:next:0 -> n3:data [tailclip=false,solid=true]
    n3:next:0 -> n4:data [tailclip=false,solid=true]
}

label=<<B>图 2.1 链表</B>>

}

线性表接口

线性表的基本接口，主要定义常见的几种方法，弹出元素、添加元素、线性表大小、获取线性表第一个元素、获取线性表最后一个元素以及对线性表进行判空。

package com.lei.payment.java.base.algorithm.list.queue;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;

/**
 * 线性表
 */
public interface List<T> {
    /**
     * 弹出元素
     *
     * @return 弹出元素
     */
    T pop() throws AlgorithmException;

    /**
     * 添加元素
     *
     * @param t 添加元素
     */
    void push(T t) throws AlgorithmException;

    /**
     * 返回线性表大小
     *
     * @return 线性表大小
     */
    int size() throws AlgorithmException;

    /**
     * 返回第一个元素
     *
     * @return 第一个元素
     */
    T fist() throws AlgorithmException;

    /**
     * 返回最后一个元素
     *
     * @return 最后一个元素
     */
    T last() throws AlgorithmException;

    /**
     * 是否是空线性表
     *
     * @return 是否是空线性表
     * @throws AlgorithmException
     */
    boolean isEmpty() throws AlgorithmException;
}

抽象实现类

统一处理异常

package com.lei.payment.java.base.algorithm.list;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;
import com.lei.payment.java.base.algorithm.exception.ErrorCode4Algorithm;
import com.lei.payment.java.base.algorithm.list.queue.List;

public class AbstractList<T> implements List<T> {
    public T pop() throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }
    public void push(T t) throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }

    public int size() throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }

    public T fist() throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }

    public T last() throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }

    public boolean isEmpty() throws AlgorithmException {
        throw new AlgorithmException(ErrorCode4Algorithm.NOT_IMPLEMENT_EXCEPTION);
    }
}