Java數據結構與算法[原創]——棧

hiyang 發布于2019-08-19 10:42 / 685人閱讀

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。方法調用編寫的程序在進行方法函數調用時，會完成對方法的壓棧操作，等方法執行結束后，對應的會完成對方法的彈棧操作。

聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。

前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文介紹數據結構中的棧的概念、存儲結構、棧的特點以及棧的適用場景，另外會穿插介紹面試中的一些經典問題供讀者參考。

1.棧的相關概念

棧是一種有著特殊操作規則的數據結構——后進先出（LIFO，Last In First Out），這也是棧的最重要的一個特點。棧又叫做堆棧（Stack），這里說明一下不要講堆棧和堆（Heap）的概念混淆，事實上棧和堆是兩個不同的概念，后面的文章會介紹堆。一般來講，棧有兩個操作：一個是進棧（Push），也叫壓棧或入棧，另一個是出棧（Pop）或叫彈棧、退棧。

2.棧的存儲結構

棧一般使用一段連續的空間進行存儲，通常預先分配一個長度可以簡單的使用數組來實現，具體存儲結構如圖：

通過上圖可以看到只有一個方向可以對棧內元素進行操作，棧中最下面的元素位置叫棧底，通常定義為數組的第0個元素，最上面的元素叫棧頂。一般而言，定義一個棧需要聲明棧的促使容量，當放入的棧中的元素大于棧的容量時，就需要考慮擴容，否則溢出。

3.java代碼實現

以下是棧的java代碼，此處以整型元素為例。

import java.util.Arrays;

public class Stack {
    private int size = 0;  //棧頂位置
    private int[] array;
    
    public Stack(){
        this(10);
    }
    public Stack(int init) {   
        if(init <= 0){
            init = 10;
        }
        array = new int[init];
    }
    
    /**
     * 入棧操作
     * @param item 入棧的元素
     */
    public void push(int item){
        if(size == array.length){
            array = Arrays.copyOf(array, size*2);   //擴容操作
        }
        array[size++] = item;
    }
    
    /**
     * 獲取棧頂元素，但棧頂元素不出棧
     * @return 棧頂元素
     */
    public int peek(){
        if(size == 0){  //空棧
            throw new IndexOutOfBoundsException("棧是空的");
        }
        return array[size-1];
    }
    
    /**
     * 出棧，同時獲取棧頂元素
     * @return
     */
    public int pop(){
        int item = peek();  //獲取棧頂元素
        size--;  //直接使元素個數減1，不用清除元素，下次入棧會覆蓋舊元素的值
        return item;
    }
    
    /**
     * 判斷棧是否已滿
     * @return
     */
    public boolean isFull(){
        return size == array.length;
    }
    
    /**
     * 判斷棧是否為空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    
    public int getSize(){
        return size;
    }    
}

測試程序：

public class StackTest {
    public static void main(String[] args) {
        Stack s = new Stack(3);  //設置棧的初始容量為3
        s.push(2);
        s.push(5);
        s.push(7);
        s.push(10);    //此時擴容，自底向頂 2—>5->7->10
        System.out.println("棧頂位置是："+s.getTop()); //棧頂指針為4，數組長度為3*2=6        
        System.out.println("獲取棧頂元素："+s.peek());  //獲取但不彈棧
        System.out.println("彈出棧頂元素："+s.pop());//彈棧返回10,自底向頂 2—>5->7
        System.out.println("彈出棧頂元素："+s.pop());//彈棧返回7,自底向頂 2—>5
        s.push(66);   //入棧后，自底向頂 2—>5->66
        System.out.println("彈出棧頂元素："+s.pop());//彈棧返回66
        System.out.println("彈出棧頂元素："+s.pop());//彈棧返回5
        System.out.println("彈出棧頂元素："+s.pop());//彈棧返回2
        System.out.println("彈出棧頂元素："+s.pop());//拋出異常，提示為空棧
    }
}

4.棧的特點

棧的特點顯而易見，只能從一段進行元素的壓入和彈出，先進去的后出來。

5.棧的應用場景

根據棧先入后出的特點，以下場景的問題適合用棧來解決：

1）逆序輸出
將所有元素依次壓入棧中，然后依次彈出即可

2）編譯器的語法檢查
在大多數編程語言中，一般括號都是成對出現，遇到括號的左半部分，則進行入棧（push）操作，遇到括號右半部分則立即與棧頂（top）元素匹配，匹配成功則彈棧（pop），否則報錯。

3）數制轉換（10進制轉換任意進制）
數制轉換通常采用取余倒置，此處不再展開。

4）方法調用
編寫的程序在進行方法（函數）調用時，CPU會完成對方法的壓棧操作，等方法執行結束后，對應的CPU會完成對方法的彈棧操作。當然除此之外，cpu產生中斷后，首先進行壓棧操作，將打斷的程序運行數據一一入棧，中斷服務程序執行完后把入棧的運行數據按照相反的順序依次出棧，恢復中斷前的運行狀態，CPU 開始返回中斷前的地方繼續運行。

GPU云服務器云服務器機器算法與java 算法與數據結構數據結構與算法數據結構與算法教程

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76354.html

Java數據結構與算法[原創]——隊列

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。隊列和棧類似，也是一個遵循特殊規則約束的數據結構。將沒有元素的隊列稱之為空隊，往隊列中插入元素的過程稱之為入隊，從隊列中移除元素的過程稱之為出隊。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文介紹數據結構中的隊列（queue）的概念、存儲結構、隊列的特點...

韓冰 2019-08-19 10:43 評論0 收藏0
面試問我 Java 逃逸分析，瞬間被秒殺了。。

摘要：記得幾年前有一次棧長去面試，問到了這么一個問題中的對象都是在堆中分配嗎說明為什么當時我被問得一臉蒙逼，瞬間被秒殺得體無完膚，當時我壓根就不知道他在考什么知識點，難道對象不是在堆中分配嗎最后就沒然后了，回去等通知了。。記得幾年前有一次棧長去面試，問到了這么一個問題: Java中的對象都是在堆中分配嗎？說明為什么！當時我被問得一臉蒙逼，瞬間被秒殺得體無完膚，當時我壓根就不知道他在考什么...

CastlePeaK 2019-08-19 11:43 評論0 收藏0
剛寫完排序算法，就被開除了…

摘要：剛寫完這段代碼，就被開除了棧長前些天剛寫完上面這篇文章，沒幾天，又來一個悲劇。。。說到這個程序員，讓我想起了最近審查代碼時候的幾個坑，真是讓人哭笑不得。。。示例直接不行寫這么繞，還把邏輯寫錯了。剛寫完這段代碼，就被開除了…… 棧長前些天剛寫完上面這篇文章，沒幾天，又來一個悲劇。。。據說是一個月薪 9K 的 Java 程序員，因老板讓他寫一個排序算法，然后他就寫了一段屌炸天的休眠排序...

klivitamJ 2019-08-16 13:41 評論0 收藏0
java篇 - 收藏集 - 掘金

摘要：進階多線程開發關鍵技術后端掘金原創文章，轉載請務必將下面這段話置于文章開頭處保留超鏈接。關于中間件入門教程后端掘金前言中間件 Java 開發人員最常犯的 10 個錯誤 - 后端 - 掘金一、把數組轉成ArrayList 為了將數組轉換為ArrayList，開發者經常... Java 9 中的 9 個新特性 - 后端 - 掘金Java 8 發布三年多之后，即將快到2017年7月下一個版...

OpenDigg 2019-08-15 10:42 評論0 收藏0
長知識 - 收藏集 - 掘金

摘要：問題是這些服務都是第三方提供的，不能保證它們的響應時間，快的話美團點評分布式生成系統后端掘金背景在復雜分布式系統中，往往需要對大量的數據和消息進行唯一標識。 SpringBatch 讀取 txt 文件并寫入數據庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數據庫... Java 進階-多線程開發關鍵技術 - 后端 - 掘金原創文章，轉載請務必將下面這段話置于文章...

SimpleTriangle 2019-08-15 10:52 評論0 收藏0