棧和隊列，隊列

棧和隊列，隊列

一、棧

1．棧的定義

     棧是一種線性表，一種抽象數據類型，它只允許在一端進行插入或刪除操作。又叫做LIFO（後進先出）線性表。

     棧的基本操作有入棧push和出棧pop，棧頂top指的是進行操作的一端。如圖，只有棧頂元素可以訪問。進棧次序為a₁、a₂、a₃、a₄、a₅，出棧次序為a₅、a₄、a₃、a₂、a₁

2．棧的實現

     棧是受限的線性表，因此任何實現表的方法都能實現棧，主要就是順序棧和鏈棧。

2.1 順序棧

     使用數組存放棧的數據元素，設有一個頭指針top執行棧頂，初始時為top=0，順序棧的實現代碼：

進棧：先放在top+1

public void push(T item){
    if(top >= capacity) return;
    items[top] = item;
    top ++;
}

出棧：先top-1再取

public T pop(){
    if(top < 0) return null;
    return (T) items[--top];
}

2.2 鏈棧

     通常采用單鏈表實現，所有的操作都在表頭進行。棧節點為：

private class Node{
    T item;
    Node next;
}

     鏈棧的實現代碼，有一個頭指針top，只能用top指針執行push、pop（插入刪除）

進棧：頭插法

public void push(T item){
    Node old = top;
    top = new Node();
    top.item = item;
    top.next = old;
    count++;
}

出棧：取時只需把top節點指向下個節點即可

public T pop(){
    T item = top.item;
    top = top.next;
    count--;
    return item;
}

二、隊列

1．隊列

     只在一端插入，另一端刪除的線性表，類似於日常的排隊，特性是先進先出FIFO。其中有兩個指針，頭指針head和尾指針tail，在tail插入，在head讀取。

2．隊列的實現

2.1 順序存儲

      使用數組，初始狀態時，head=tail=0；當tail==MaxSize時，並不能說明隊列滿了，當head指針為tail的前一個位置，此時隊列中只有一個元素，但沒滿，這時入隊出現上溢出，這時一種假溢出。

2.1.1 循環隊列

      也稱環形隊列，環形緩沖區，臆造一個環狀的空間，當隊頭或隊首指針達到最大時，重置為零，可以使用取余運算實現，（也能不用取余）。

取余運算：

初始時，head = tail = 0;
隊首加1，head = (head + 1) % MaxSize;
隊尾加1，tail = (tail + 1) % MaxSize;
隊列長度，(tail + MaxSize - head) % MaxSize;

不使用取余：

     以RingBuffer環形緩沖區為例，具體代碼在GitHub，其中入隊和出隊的代碼如下，沒使用取模運算，（對計算機來說，加1減1比取模簡單）

入隊：

public boolean put(T item){
    int next = tail + 1;
    if(next >= bufferSize){
        next = 0;
    }
    if(next == head){
        lost++;
        return false;
    }
    rBuffer[next] = item;
    tail = next;
    return true;
} 

出隊：

public T get(){
    if(head == tail){
        return null;
    }
    @SuppressWarnings("unchecked")
    T item = (T) rBuffer[head];
    rBuffer[head] = null;
    
    if(++head >= bufferSize){
        head = 0;
    }
    return item;
}

2.2鏈式存儲

鏈隊列，使用一個帶有隊頭head和隊尾tail指針的單鏈表，在head讀取，在tail插入。節點類型如下：

private Node head; // 隊頭
private Node tail; // 隊尾
private class Node{ // 節點
    T item;
    Node next;
}

入隊：

public void enqueue(T item){
    Node old = tail;
    tail = new Node();
    tail.item = item;
    tail.next = null;
    if(isEmpty()){
        head = tail;
    } else {
        old.next = tail;
    }
    count++;
}

出隊：

public T dequeue(){
    T res = head.item;
    head = head.next;
    if(isEmpty()){
        tail = null;
    }
    count--;
    return res;
}

源碼地址：https://github.com/cyhe/algorithm/tree/master/src/algo/linearlist/stack