資料結構2 - 棧與隊列

常見問題：

堆與棧的不同是什麼
heap和stack的差別
解釋記憶體中的棧（stack）、堆（heap）和靜态區（static area）的用法
什麼是Java優先級隊列（Priority Queue）？

1. 棧

棧是一種特殊的線性表，棧的插入和删除隻允許在表的尾端進行。其中，棧中允許插入和删除操作的一端成為棧頂，另一端稱為棧底。

資料結構2 - 棧與隊列

棧在計算機應用中也到處可見，例如，浏覽器對使用者目前通路過位址的管理，鍵盤緩沖區中對鍵盤輸入資訊的管理等都采用了棧式結構。

棧的抽象資料類型描述：

public interface IStack {
    void clear();
    boolean isEmpty();
    int length();
    //取棧頂元素并傳回其值，若為空，則傳回null
    Object peek();
    //入棧
    void push(Object x) throws Exception;
    //出棧
    Object pop();
}

1.1 順序棧

與順序表一樣，順序棧也是用數組來實作的，假設數組名為stackElem。由于入棧和出棧操作隻能在棧頂進行，是以需加上一個變量top來訓示棧頂元素的位置。top有兩種定義方式，一種是将其設定為指向棧頂元素存儲位置的下一個存儲單元的位置，則空棧時，top = 0；另一種是将top設定為指向棧頂元素的存儲位置，則空棧時，top = -1。這裡用第一種方式。

順序棧類的描述為：

public class SqStack implements IStack {
    private Object[] stackElem;
    private int top;

    public SqStack(int maxSize){
        top = 0;
        stackElem = new Object[maxSize];
    }

    @Override
    public void clear() {
        top = 0;
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public int length() {
        return top;
    }

    /**
     * 取棧頂元素并傳回其值，若為空，則傳回null
     * */
    @Override
    public Object peek() {
        if(!isEmpty())
            return stackElem[top - 1];
        else
            return null;
    }

    /**
     * 入棧
     * */
    @Override
    public void push(Object x) throws Exception {
        if(top == stackElem.length)
            throw new Exception("棧滿！");
        else
            stackElem[top ++] = x;
    }

    /**
     * 出棧
     * */
    @Override
    public Object pop() {
        if(top == 0)
            return null;
        else
            return stackElem[--top];
    }

    @Override
    public void display() {
        for (int i = top - 1; i >= 0 ; i--) {
            System.out.print(stackElem[i].toString() + " ");
        }
    }
}

資料結構2 - 棧與隊列

1.2 鍊棧

資料結構2 - 棧與隊列

1.2.1 鍊棧類的描述：

public class LinkStack implements IStack {
    private Node top;

    @Override
    public void clear() {
        top = null;
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }

    /**
     * 求棧長度
     * */
    @Override
    public int length() {
        Node p = top;
        int length = 0;
        while (p != null){
            p = p.next;
            ++ length;
        }
        return length;
    }

    /**
     * 取棧頂元素
     * */
    @Override
    public Object peek() {
        if(top != null){
            return top.data;
        }else
            return null;
    }

    /**
     * 入棧
     * */
    @Override
    public void push(Object x) throws Exception {
        Node s = new Node(x);
        s.next = top;
        top = s;
    }

    /**
     * 出棧
     * */
    @Override
    public Object pop() {
        if(top == null){
            return null;
        }else {
            Node p = top;
            top = top.next;
            return p.data;
        }
    }

    @Override
    public void display() {
        Node p = top;
        while (p != null){
            System.out.print(p.data.toString()+" ");
            p = p.next;
        }
    }
}

1.2.2 小練習 - 棧與遞歸問題:程式設計實作漢諾塔(Hanoi)問題的求解。

n階漢諾塔問題:假設有3個分别命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同，且從小到大編号為1、2…n的圓盤。現要求将塔座X上的n個圓盤借助塔座Y移至塔座Z上，并仍按同樣順序疊排。圓盤移動時必須遵循下列規則:

(1)每次隻能移動一個圓盤。

(2)圓盤可以插在X、Y和Z中的任何一個塔座上。

(3)任何時刻都不能将一一個較大的圓盤壓在較小的圓盤之上。

public class Test_Hanoi {
    public static void main(String[] args) {
        Test_Hanoi test_hanoi = new Test_Hanoi();
        test_hanoi.hanoi(3,'x','y','z');
    }

    //計數，第幾次移動
    private int time = 0;
    //将塔座x上按直徑由小到大且自上而下的編号為1至n的n個圓盤按規則移到塔座z上，y作為輔助塔座
    public void hanoi(int n, char x, char y, char z){
        if(n == 1){
            move(x,1,z); //将編号為1的圓盤從x移動到z
        }else {
            hanoi(n-1,x,z,y); //将x上編号為1至n-1的圓盤移動到y上，z為輔助
            move(x,n,z); //将編号為n的圓盤從x移動到z
            hanoi(n-1,y,x,z); //将y上編号為1到n-1的圓盤移動到z，x為輔助
        }
    }
    private void move(char x, int n, char z) {
        System.out.println("第"+ ++time + "次移動："+ n + "号園盤，"+ x + "--->" + z);
    }
}

output：

第1次移動：1号園盤，x--->z
第2次移動：2号園盤，x--->y
第3次移動：1号園盤，z--->y
第4次移動：3号園盤，x--->z
第5次移動：1号園盤，y--->x
第6次移動：2号園盤，y--->z
第7次移動：1号園盤，x--->z

2. 隊列

隊列是另一種特殊的線性表，隻允許在表尾插入資料元素，在表頭删除資料元素。具有先進先出的特性。

資料結構2 - 棧與隊列

隊列的抽象資料類型描述：

public interface IQueue {
    void clear();
    boolean isEmpty();
    int length();
    //取隊首元素
    Object peek();
    //入隊
    void offer(Object x) throws Exception;
    //出隊
    Object poll();
}

2.1 順序隊列

如圖描述了一個從空隊列開始，先後經過A、B、C入隊列；A、B出隊列；E、F、G入隊列操作，隊列的順序存儲結構狀态。

資料結構2 - 棧與隊列

由圖可以看出，若此時還需要将資料元素H人隊，H應該存放于rear = 6的位置處，順序隊列則會因數組下标越界而引起“溢出”，但此時順序隊列的首部還空出了兩個資料元素的存儲空間。是以,這時的“溢出”并不是由于數組空間不夠而産生的溢出。這種因順序隊列的多次入隊和出隊操作後出現有存儲空間，但不能進行入隊操作的溢出現象稱為“假溢出”。

要解決“假溢出”問題，最好的辦法就是把順序隊列所使用的存儲空間看成是一個邏輯上首尾相連的循環隊列。當rear或front到達maxSize-1後，再加1就自動到0。這種轉換可利用Java語言中對整型資料求模(或取餘)運算來實作，即令rear == (rear+1)%maxSize。顯然，當rear = maxSize - 1時，rear加1後，rear的值就為0。這樣，就不會出現順序隊列數組的頭部有空的存儲空間，而隊尾卻因數組下标越界而引起的假溢出現象。

2.2 循環順序隊列

假設maxSize=6，循環順序隊列的初始化狀态如圖(1)所示，此時有 front == rear==0；當A、B、C、D、E、F分别入隊後，循環順序隊列為滿，如圖(2)所示，此時有front == rear；當A、B、C、D、E出隊，而G、H又人隊後，循環順序隊列的狀态如圖(3)所示，此時front=5，rear=2；再将F、G、H出隊後，循環順序隊列為空，如圖(4)所示，此時有front == rear。為此，在循環順序隊列中就引發出一個新的問題：無法區分隊空和隊滿的狀态，這是因為循環順序隊列的判空和判滿的條件都是front == rear。

資料結構2 - 棧與隊列

解決判斷問題的三個解決方案：

1）少用一個單元

當順序存儲空間的容量為maxSize時，隻允許最多存放maxSize -1 個資料元素。此時，隊空的判斷條件為: front == rear ，而隊滿的判斷條件為：front == (rear+ 1)% maxSize。

資料結構2 - 棧與隊列

2）設定一個标志變量

在程式設計過程中引進一個标志變量flag，其初始值置為0，每當入隊操作成功後就置flag=1；每當出隊操作成功後就置flag=0，則此時隊空的判斷條件為: front== rear && flag== 0，而隊滿的判斷條件為: front=rear && flag== 1。

3）設定一個計數器

在程式設計過程中引進一個計數變量num，其初始值置為0，每當入隊操作成功後就将計數變量num的值加1；每當出隊操作成功後就将計數變量num的值減1，則此時隊空的判斷條件為: num ==0。而隊滿的判斷條件為：num>0 && front == rear。

這裡采用第一種方法。

循環順序隊列類的描述：

public class CircleQueue implements IQueue {
    private Object[] queueElem;
    private int front;
    private int rear;

    public CircleQueue(int maxSize){
        front = rear = 0;
        queueElem = new Object[maxSize];
    }

    @Override
    public void clear() {
        front = rear = 0;

    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public int length() {
        return (rear - front + queueElem.length) % queueElem.length;
    }

    @Override
    public Object peek() {
        if(front == rear)
            return null;
        else
            return queueElem[front];
    }

    //入隊
    @Override
    public void offer(Object x) throws Exception {
        if((rear + 1) % queueElem.length == front)
            throw new Exception("隊列已滿");
        else{
            queueElem[rear] = x;
            rear = (rear + 1) % queueElem.length;
        }
    }

    //出隊
    @Override
    public Object poll() {
        if(front == rear)
            return null;
        else {
            Object t = queueElem[front];
            front = (front + 1) % queueElem.length;
            return t;
        }
    }

    public void display(){
        if(!isEmpty()){
            for (int i = front; i != rear; i = (i + 1)% queueElem.length)
                System.out.print(queueElem[i].toString()+" ");
        }else
            System.out.println("此隊列為空");

    }
}

2.3 鍊隊列

資料結構2 - 棧與隊列

2.3.1 鍊隊列的描述

public class LinkQueue implements IQueue {
    private Node front;
    private Node rear;

    public LinkQueue(){
        front = rear = null;
    }

    @Override
    public void clear() {
        front = rear = null;
    }

    @Override
    public boolean isEmpty() {
        return front == null;
    }

    @Override
    public int length() {
        Node p = front;
        int length = 0;
        while (p != null){
            p = p.next;
            ++ length;
        }
        return length;
    }

    @Override
    public Object peek() {
        if(front != null)
            return front.data;
        else
            return null;
    }

    /**
     * 入隊
     * */
    @Override
    public void offer(Object x) throws Exception {
        Node s = new Node(x);
        if(front != null){
            rear.next = s;
            rear = s;
        }else
            front = rear = s;

    }

    /**
     * 出隊
     * */
    @Override
    public Object poll() {
        if(front != null){
            Node p = front;
            front = front.next;
            if(p == rear)
                rear = null;
            return p.data;
        }else
            return null;
    }
}

2.4 優先級隊列

優先級隊列是一種帶有優先級的隊列，它有一個隊首和一個隊尾，也是從隊首删除資料元素，但不同的是優先級隊列中資料元素按關鍵字的值有序排列。由于很多情況下，需要通路具有最小關鍵字值的資料元素，是以，約定關鍵字最小的資料元素具有最高的優先級，并且總是排在隊首。是以插入資料元素時順序插入到隊列的合适位置，以確定隊列的優先級順序。

優先級隊列在很多地方都有用，例如：構造哈夫曼樹算法中就應用了優先級隊列；在搶先式多任務作業系統中，程式就被排列在優先級隊列中，這樣優先級最高的程式就會先得到時間片并得以運作。

2.4.1 優先級隊列類的描述：

通常以鍊式存儲結構實作優先級隊列。資料元素優先級别的高低依據優先數大大小來鑒定，優先數越小，優先級别越大。

優先隊列中結點data類描述如下：

public class PriorityData {
    public Object elem; //結點的資料元素值
    public int priority; //結點的優先數
    
    public PriorityData(Object elem, int priority){
        this.elem = elem;
        this.priority = priority;
    }
}

實作IQueue接口的類描述如下：

public class PriorityQueue implements IQueue {
    private Node front;
    private Node rear;

    public PriorityQueue(){
        front = rear = null;
    }

    @Override
    public void clear() {
        front = rear = null;

    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public int length() {
        Node p = front;
        int length = 0;
        while (p != null){
            p = p.next;
            ++ length;
        }
        return length;
    }

    /**
     * 讀取隊首元素
     * */
    @Override
    public Object peek() {
        if(front != null)
            return front.data;
        else
         return null;
    }

    /**
    * 入隊
    * */
    @Override
    public void offer(Object x) throws Exception {
        PriorityData pn = (PriorityData) x;
        Node s = new Node(pn);
        if(front == null)
            front = rear = s;
        else {
            Node p = front, q = front;
            while (p != null && pn.priority >= ((PriorityData)p.data).priority){
                q = p;
                p = p.next;
            }
            if(p == null){ //p為空，表示周遊到了隊列尾部
                rear.next = s;
                rear = s;
            }else if(p == front){ //p的優先級大于隊首結點的優先級
                s.next = front;
                front = s;
            }else {
                q.next = s;
                s.next = p;
            }
        }
    }

    /**
     * 出隊
     * */
    @Override
    public Object poll() {
        if(front != null){
            Node p = front;
            front = front.next;
            return p.data;
        }else
            return null;
    }

    public void display(){
        if(!isEmpty()){
            Node p = front;
            while (p != rear.next){
                PriorityData q = (PriorityData) p.data;
                System.out.println(q.elem + " "+q.priority);
                p = p.next;
            }
        }else
            System.out.println("此隊列為空");
    }
}

資料結構2 - 棧與隊列

1. 棧

1.1 順序棧

1.2 鍊棧

2. 隊列

2.1 順序隊列

2.2 循環順序隊列

2.3 鍊隊列

2.4 優先級隊列

繼續閱讀

[LeetCode]（面試題 17.21）直方圖的水量

集合練習題1

java 程式設計思想第四版學習随記

java之單使用者登入

HDU 4041 Eliminate Witches!

_stdcall和_cdecl

Java反射是什麼，為什麼要用反射

Double類parseDouble和valueOf方法的差別

java調用Windows指令行

第四章棧與隊列

java列印任意邊長的菱形

Rabbitmq指令行手動建立隊列

java 8 Lamda 求 List 中 Bigdecimal類型的各種值求最大值求最小值求和求平均值

筆試面試題目：滑動視窗(二)

回溯法迷宮求解

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？