棧和隊列的學習（Java實作）

包括棧的實作，使用棧進行編譯器檢查，使用棧結合逆波蘭法和中綴到字尾的轉換進行電腦計算。也介紹了棧幀，此外還有隊列的簡要介紹

3.6 棧ADT

3.6.1 棧模型

棧是限制插入和删除隻能在一個位置上的表，該位置是表的末端，叫做棧的頂。對棧的基本操作有push和pop,前者相當于插入，後者則是删除最後插入的元素。最後插入的元素可以通過使用top例程在執行pop前進行考察。對空棧進行pop或者top是棧ADT中的一個錯誤，當運作push時空間用盡不認為是錯誤，而是實作限制。

3.6.2 棧的實作

棧有時又叫做LIFO(後進先出)表。由于棧是一個表，是以任何實作表的方法都能實作棧。ArrayList和LinkedList都支援棧操作。

棧的連結清單實作。棧的第一種實作方法是實作單連結清單。通過在表的頂端插入來push,通過删除表的頂端元素來pop,top隻是用來查詢頂端的值
棧的數組實作。模仿ArrayList的add操作。與每個棧相關的操作是theArray和topOfStack，對于空棧他是-1（也就是初始化操作）。為了将某個元素x推入棧中，我們讓topOfStack增1然後置theArray[topOfStack]=x。為了彈出棧元素，我們置傳回值為theArray[topOfStack],然後使topOfStack-1

/**
    * 棧的數組實作
    * @param <T>
    */
    public class MyStack<T> {
        private static final int DEFAULT_CAPACITY=10;
        private T[] elements;
        private int topOfStack;
        public MyStack(){
            clear();
            ensureCapacity(DEFAULT_CAPACITY);
        }

        /**
        * 數組擴容
        * @param newSize
        */
        private void ensureCapacity(int newSize){
            if(newSize<topOfStack){
                return;
            }
            T[] olds=elements;
            elements=(T[])new Object[newSize];
            for(int i=0;i<topOfStack;i++){
                elements[i]=olds[i];
            }
        }

        /**
        * 初始化棧頂為-1
        */
        private void clear(){
            topOfStack=-1;
        }

        public void push(T newElement){
            elements[++topOfStack]=newElement;
        }

        public T pop(){
            T element=elements[topOfStack];
            topOfStack--;
            return element;

        }

        public T top(){
            return elements[topOfStack];
        }
    }
    /*
    *棧的測試類
    */
    @Test
    public void stackTest(){
        MyStack<Integer> myStack=new MyStack<>();
        myStack.push(123);
        myStack.push(125);
        myStack.push(44);
        myStack.push(79);
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
    }

3.6.3 棧的應用

1、檢查完整性

平衡符号：例如括号是成對出現的，檢查是不是有一對等，常用在編譯器檢查錯誤上。
算法描述：做一個空棧。讀入字元直到結尾。如果字元是一個開放符号，則将其推入棧中，如果字元是一個封閉符号，則當棧空時報錯。否則，将棧元素彈出。如果彈出符号不是對應的開放符号，則報錯，在檔案結尾，如果棧非空，則報錯。

/*
    *為了獲得最終的棧的大小，我把棧的大小公開了
    */
    @Test
    public void stackAppCheckPair(){
        MyStack<String> myStack=new MyStack<>();
        String checkStr="ddd{AAA0(})";

        Single<String> pair1=new Single<>("(",")");
        Single<String> pair2=new Single<>("{","}");
        MyArrayList<Single<String>> pairList=new MyArrayList<Single<String>>();
        pairList.add(pair1);
        pairList.add(pair2);
        for(int i=0;i<checkStr.length();i++){
            String c=String.valueOf(checkStr.charAt(i));
            for(Single<String> pair:pairList){
                if(c.equals(pair.first)){
                    myStack.push(c);
                }else if(c.equals(pair.end)){
                    if(myStack.top().equals(pair.first)){
                        myStack.pop();
                    }else {
                        System.out.println("Error");
                        return;
                    }
                }
            }
        }
        if(myStack.topOfStack!=-1){
            System.out.println("Error");
        }else {
            System.out.println("Success");
        }
    }

    private class Single<T>{
        public Single(T first, T end) {
            this.first = first;
            this.end = end;
        }
        public T first;
        public T end;
    }

2、字尾表達式計算

采用逆波蘭法（字尾）法計算字元串方程
算法描述：遇見一個數就把他推入棧中，遇見一個運算符就把兩個數彈出來，用運算符計算，再壓棧

例子：12 * 3 + 21 + 6 * 2 = 按照逆波蘭法，則記為 12 3 * 21 + 6 2 * +

計算：“6523+8*+3+*”

@Test
    public void stackAppCalcuator(){
        MyStack<String> myStack=new MyStack<>();
        List<String> toolList=new ArrayList<>();
        toolList.add("+");
        toolList.add("-");
        toolList.add("*");
        toolList.add("/");
        String str="6523+8*+3+*";
        for(int i=0;i<str.length();i++){
            String element=String.valueOf(str.charAt(i));
            if(toolList.contains(element)){

                int result=0;
                int num1=Integer.valueOf(myStack.pop());
                int num2=Integer.valueOf(myStack.pop());
                if(element.equals("+")){
                    result=num1+num2;
                }else if(element.equals("-")){
                    result=num2-num1;
                }else if(element.equals("*")){
                    result=num2*num1;
                }else if(element.equals("/")){
                    result=num2/num1;
                }
                myStack.push(String.valueOf(result));
            }else{
                myStack.push(element);
            }
        }
        System.out.println(myStack.pop());

    }

3、将中綴表達式轉為字尾表達式

中綴表達式就是标準的表達式:12 * 3 + 21 + 6 * 2 =

例子：a+b*c+(d*d+f)*g 轉化為字尾表達式為abc*+de*f+g*+

下面時算法思路

當讀到一個操作數的時候，立即把他放在輸出中。操作符不立即輸出，将讀到的操作符推入棧中。
當遇到左圓括号的時候我們也要将其推入棧中。從計算一個空棧開始。
當遇到一個右括号，那麼就将棧元素彈出，将彈出的符号寫出，直到遇見一個對應的左括号，但是這個左括号隻被彈出并不被輸出
如果見到任何其他符号 +，*，(,那麼我們從棧中彈出棧元素直到發現更低的元素為止。有一個例外，除非在處理一個)的時候，否則絕不從棧中移走(，對于這種操作，+的優先級最低而(的優先級最高。當從棧彈出元素的工作完成後，我們再把操作符壓入棧中。
如果讀到輸入的末尾，我們将棧元素彈出直到該棧變成空棧，将符号寫到輸出中

這個算法的想法是，當看到一個操作符的時候，把他放入棧中。棧代表挂起的操作符，然而，棧中有些具有高優先級的操作符現在知道當他們不再被挂起時要完成做使用，應該被彈出，這樣，在把目前操作符放入棧中之前，那些在棧中并在目前操作符之前完成使用的操作符被彈出

/**
     *中綴到字尾轉換
     */
    @Test
    public void infixTest(){
        MyStack<String> myStack=new MyStack<>();
        List<String> toolList=new ArrayList<>();
        toolList.add("+");
        toolList.add("-");
        toolList.add("*");
        toolList.add("/");
        toolList.add("(");
        toolList.add(")");
        List<String> numberList=new ArrayList<>();
        numberList.add("a");
        numberList.add("b");
        numberList.add("c");
        numberList.add("d");
        numberList.add("e");
        numberList.add("f");
        numberList.add("g");

        String str="a+b*c+(d*e+f)*g";
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<str.length();i++){
            String element=String.valueOf(str.charAt(i));
            if(numberList.contains(element)){
                sb.append(element);
            }else if(toolList.contains(element)){
                int stackSize=myStack.topOfStack+1;
                if(stackSize==0){
                    myStack.push(element);
                }else {

                    String currElement=element;
                    for (int j=0;j<stackSize;j++){
                        String prevElement=myStack.top();//擷取棧頂
                        if(prevElement==null){
                            break;
                        }
                        if(currElement.equals("+")||currElement.equals("-")){//如果目前讀是+和-,那麼沒有比他們優先級更低的了，除非遇到(，否則全部彈出
                            if(prevElement.equals("(")){
                                myStack.push(currElement);//壓入棧
                                j=stackSize;//壓入之後結束周遊
                            }else {
                                sb.append(myStack.pop());//這裡還需要判斷一下是否全部彈完了，全談完之後要把剛才新的元素壓入
                                if(j==stackSize-1){
                                    myStack.push(currElement);
                                }
                            }
                        }else if(currElement.equals("*")||currElement.equals("/")){//如果是*或者/,那麼優先級位于(和+，-之間,遇到同級的則彈出原來的元素再壓入
                            if(prevElement.equals("(")){
                                myStack.push(currElement);//壓入棧
                                j=stackSize;//壓入之後結束周遊
                            }else if(prevElement.equals("+")||prevElement.equals("-")){
                                myStack.push(currElement);//壓入棧
                                j=stackSize;//壓入之後結束周遊
                            }else{
                                sb.append(myStack.pop());
                            }

                        }else if(currElement.equals("(")) {// （的優先級是最高的，是以直接壓入就行
                            myStack.push(currElement);//壓入棧
                            j=stackSize;//壓入之後結束周遊
                        }else {//最後，目前元素為)時，彈到（為止
                            if(prevElement.equals("(")){
                                myStack.pop();
                                j=stackSize;
                            }else {
                                sb.append(myStack.pop());
                            }

                        }
                    }
                }



            }

        }
        while ((myStack.topOfStack)!=-1){//最後把棧中的運算符全部彈出
            sb.append(myStack.pop());
        }
        System.out.println(sb.toString());

    }

把中綴表達式轉為字尾表達式之後，再進行計算即可，實作簡單的電腦

4、方法調用

當存在方法調用的時候，需要存儲的所有的重要資訊，例如寄存器的值（對應變量的名字）和傳回位址（它可以從程式計數器中得到，一般情況下是在一個寄存器中）等，都要以抽象的方式存在一張紙上，并被置于一個堆的頂部。然後控制轉移到新的方法，該方法自由的使用他的一些值代替這些寄存器。如果他又存在其他調用，也遵循這樣的方式，當方法傳回時，他檢視堆頂部的那些紙，并且複原所有寄存器，然後進行傳回轉移。

這些所有的工作都可以由一個棧來完成，而這正是實作遞歸的每一種程式設計語言實際發生的事實。所有存儲的資訊稱為活動記錄,或者叫做棧幀。在實際的計算機中的棧常常是從記憶體分區的高端向下增長，很多非Java系統是不檢測溢出的，由于可能有很多同時運作的方法，是以棧空間用盡是有可能的。在正常情況下一般不會越出棧空間，發生這種情況常常是由于失控遞歸造成的。

一般不要使用尾遞歸（在函數的最後一行遞歸）

/**
     * 尾遞歸的不當使用，有N個元素就會導緻有N個棧幀
     * @param list
     */
    public void printList(Iterator<String> list){
        if(!list.hasNext()){
            return;
        }else {
            System.out.println(list.next());
            printList(list);
        }
    }

    /**
     * 不用遞歸列印一個連結清單,沒有用到棧幀
     * @param list
     */
    public void printList(Iterator<String> list){
        while (true){
            if(!list.hasNext()){
                return;
            }
            System.out.println(list.next());
        }
    }

3.7 隊列ADT

3.7.1 隊列模型

像棧一樣，隊列也是表。然而隊列的插入和删除不在同一端進行(FIFO先進先出)

隊列的基本操作是enqueue(在尾部插入)和dequeue（在頭部删除）

3.7.2 隊列的數組實作

實作思路

對于每一個隊列的資料結構，我們保留一個數組theArray以及位置front和back,他們代表隊列的兩端，還要記錄實際存在于隊列中元素的個數currentSize和back增1，然後theArray[back]=x,如果讓元素出棧，則置傳回值為theArray[front],currentSize–,front++;

為了解決出隊問題，使用循環數組解決。當front和back到達數組的尾端，他就又繞回開頭

棧和隊列的學習（Java實作）棧和隊列的學習（Java實作）

棧和隊列的學習（Java實作）

3.6 棧ADT

3.6.1 棧模型

3.6.2 棧的實作

3.6.3 棧的應用

3.7 隊列ADT

3.7.1 隊列模型

3.7.2 隊列的數組實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

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

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

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

Linux裝置模型（中）之上層容器