線性表包括數(shù)組，鏈表（單鏈表，雙向鏈表，循環(huán)鏈表，雙向循環(huán)鏈表，靜態(tài)鏈表），棧（順序棧，鏈?zhǔn)綏＃?duì)列（普通隊(duì)列，雙端隊(duì)列，阻塞隊(duì)列，并發(fā)隊(duì)列，阻塞并發(fā)隊(duì)列）。

棧

棧是限定僅在表位進(jìn)行插入和刪除操作的線性表，棧只有兩種操作：入棧和出棧，LIFO (后進(jìn)先出)。
?？梢杂脭?shù)組來實(shí)現(xiàn)（順序棧）， 也可以用鏈表實(shí)現(xiàn)（鏈?zhǔn)綏＃?br> 入棧和出棧的代碼演示

package dataStructures;

public class Stack {
    private String[] items;
    private int size;
    private int count;

    public Stack(int size) {
        this.size = size;
        this.count = 0;
        items = new String[size];
    }

    public boolean push(String item) {
        if (count == size) return false;
        items[count] = item;
        ++count;
        return true;
    }

    public String pop() {
        if (count > 0) {
            String item = items[count];
            --count;
            return item;
        }
        return null;
    }
}

隊(duì)列

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。隊(duì)列是一種先進(jìn)先出（FIFO）的線性表，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。隊(duì)列也只有兩種操作入隊(duì)（enqueue）和出隊(duì)（dequeue）。隊(duì)列跟棧一樣，也可以由數(shù)組或鏈表實(shí)現(xiàn)，分別稱為順序隊(duì)列和鏈?zhǔn)疥?duì)列

package dataStructures;

public class ArrayQueue {
    private String[] items;
    private int size = 0;
    private int head = 0;
    private int tail = 0;

    public ArrayQueue(int size) {
        this.size = size;
        items = new String[size];
    }

    public boolean enqueue(String item) {
        if (tail == size) {//tail已經(jīng)超出數(shù)組空間了
            if (head == 0) return false;//隊(duì)列已滿
            for (int i = head; i < tail; ++i) {
                items[i - head] = items[i];
            }
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    public String dequeue() {
        if (head == tail) return null;
        String item = items[head];
        ++head;
        return item;
    }
}

上述隊(duì)列會(huì)發(fā)生數(shù)據(jù)搬移操作，所以多少會(huì)影響性能。
下面介紹循環(huán)隊(duì)列，所謂循環(huán)隊(duì)列，顧名思義，就是首尾相接的隊(duì)列。
當(dāng) head = tail 的時(shí)候說明隊(duì)列是空的，當(dāng) head 與 tail 相差為1是說明隊(duì)列已滿，但對(duì)于循環(huán)隊(duì)列來說 head 有時(shí)候會(huì)比 tail 大，有時(shí)會(huì)比 tail 小，所以我們用取模的形式（tail+1）%QueueSize = head 這是說明隊(duì)列已滿，由于此時(shí)tail還沒有插入值，所有對(duì)于循環(huán)隊(duì)列來說，總有一個(gè)是空的

package dataStructures;
//循環(huán)隊(duì)列
public class CircularQueue {
    private String items[];
    private int head = 0;
    private int tail = 0;
    private int queueSize = 0;

    public CircularQueue(int size) {
        this.queueSize = size;
        items = new String[size];
    }

    private boolean enqueue(String item) {
        //隊(duì)列已滿
        if ((tail + 1) % queueSize == head) return false;
        items[tail] = item;
        tail = (tail + 1) % queueSize;
        return true;
    }

    private String dequeue() {
        //隊(duì)列為空
        if (head == tail) return null;
        String value = items[head];
        head = (head + 1) % queueSize;
        return value;
    }
}