成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Java數(shù)據(jù)結(jié)構(gòu)與算法[原創(chuàng)]——棧

hiyang / 695人閱讀

摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。方法調(diào)用編寫的程序在進(jìn)行方法函數(shù)調(diào)用時(shí)，會(huì)完成對(duì)方法的壓棧操作，等方法執(zhí)行結(jié)束后，對(duì)應(yīng)的會(huì)完成對(duì)方法的彈棧操作。

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的棧的概念、存儲(chǔ)結(jié)構(gòu)、棧的特點(diǎn)以及棧的適用場(chǎng)景，另外會(huì)穿插介紹面試中的一些經(jīng)典問題供讀者參考。

1.棧的相關(guān)概念

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

2.棧的存儲(chǔ)結(jié)構(gòu)

棧一般使用一段連續(xù)的空間進(jìn)行存儲(chǔ)，通常預(yù)先分配一個(gè)長(zhǎng)度可以簡(jiǎn)單的使用數(shù)組來實(shí)現(xiàn)，具體存儲(chǔ)結(jié)構(gòu)如圖：

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

3.java代碼實(shí)現(xiàn)

以下是棧的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);   //擴(kuò)容操作
        }
        array[size++] = item;
    }
    
    /**
     * 獲取棧頂元素，但棧頂元素不出棧
     * @return 棧頂元素
     */
    public int peek(){
        if(size == 0){  //空棧
            throw new IndexOutOfBoundsException("棧是空的");
        }
        return array[size-1];
    }
    
    /**
     * 出棧，同時(shí)獲取棧頂元素
     * @return
     */
    public int pop(){
        int item = peek();  //獲取棧頂元素
        size--;  //直接使元素個(gè)數(shù)減1，不用清除元素，下次入棧會(huì)覆蓋舊元素的值
        return item;
    }
    
    /**
     * 判斷棧是否已滿
     * @return
     */
    public boolean isFull(){
        return size == array.length;
    }
    
    /**
     * 判斷棧是否為空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    
    public int getSize(){
        return size;
    }    
}

測(cè)試程序：

public class StackTest {
    public static void main(String[] args) {
        Stack s = new Stack(3);  //設(shè)置棧的初始容量為3
        s.push(2);
        s.push(5);
        s.push(7);
        s.push(10);    //此時(shí)擴(kuò)容，自底向頂 2—>5->7->10
        System.out.println("棧頂位置是："+s.getTop()); //棧頂指針為4，數(shù)組長(zhǎng)度為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.棧的特點(diǎn)

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

5.棧的應(yīng)用場(chǎng)景

根據(jù)棧先入后出的特點(diǎn)，以下場(chǎng)景的問題適合用棧來解決：

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

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

3）數(shù)制轉(zhuǎn)換（10進(jìn)制轉(zhuǎn)換任意進(jìn)制）
數(shù)制轉(zhuǎn)換通常采用取余倒置，此處不再展開。

4）方法調(diào)用
編寫的程序在進(jìn)行方法（函數(shù)）調(diào)用時(shí)，CPU會(huì)完成對(duì)方法的壓棧操作，等方法執(zhí)行結(jié)束后，對(duì)應(yīng)的CPU會(huì)完成對(duì)方法的彈棧操作。當(dāng)然除此之外，cpu產(chǎn)生中斷后，首先進(jìn)行壓棧操作，將打斷的程序運(yùn)行數(shù)據(jù)一一入棧，中斷服務(wù)程序執(zhí)行完后把入棧的運(yùn)行數(shù)據(jù)按照相反的順序依次出棧，恢復(fù)中斷前的運(yùn)行狀態(tài)，CPU 開始返回中斷前的地方繼續(xù)運(yùn)行。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76354.html

相關(guān)文章

  • Java數(shù)據(jù)結(jié)構(gòu)與算法[原創(chuàng)]——隊(duì)列

    摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。隊(duì)列和棧類似，也是一個(gè)遵循特殊規(guī)則約束的數(shù)據(jù)結(jié)構(gòu)。將沒有元素的隊(duì)列稱之為空隊(duì)，往隊(duì)列中插入元素的過程稱之為入隊(duì)，從隊(duì)列中移除元素的過程稱之為出隊(duì)。 聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列（queue）的概念、存儲(chǔ)結(jié)構(gòu)、隊(duì)列的特點(diǎn)...

    韓冰 評(píng)論0 收藏0

  • 面試問我 Java 逃逸分析，瞬間被秒殺了。。

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

    CastlePeaK 評(píng)論0 收藏0

  • 剛寫完排序算法，就被開除了…

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

    klivitamJ 評(píng)論0 收藏0

  • java篇 - 收藏集 - 掘金

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

    OpenDigg 評(píng)論0 收藏0

  • 長(zhǎng)知識(shí) - 收藏集 - 掘金

    摘要：?jiǎn)栴}是這些服務(wù)都是第三方提供的，不能保證它們的響應(yīng)時(shí)間，快的話美團(tuán)點(diǎn)評(píng)分布式生成系統(tǒng)后端掘金背景在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。 SpringBatch 讀取 txt 文件并寫入數(shù)據(jù)庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數(shù)據(jù)庫... Java 進(jìn)階-多線程開發(fā)關(guān)鍵技術(shù) - 后端 - 掘金原創(chuàng)文章，轉(zhuǎn)載請(qǐng)務(wù)必將下面這段話置于文章...

    SimpleTriangle 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<