棧的實現(xiàn)原理

soasme 發(fā)布于2019-08-19 11:35 / 3469人閱讀

摘要：使用棧實現(xiàn)字符串逆序?qū)⒆址崔D(zhuǎn)用兩個棧實現(xiàn)隊列用兩個棧來實現(xiàn)一個隊列，完成隊列的和操作。假設(shè)棧中有個元素，基于簡單數(shù)組實現(xiàn)的棧。可以看到棧是實現(xiàn)，其實底層也是用數(shù)組來實現(xiàn)的。移除此堆棧頂部的對象，并將該對象作為此函數(shù)的值返回。

目錄介紹

01.棧由簡單數(shù)據(jù)實現(xiàn)

1.1 簡單數(shù)組代碼實現(xiàn)

1.2 可能出現(xiàn)問題

1.3 性能和局限性

02.棧由動態(tài)數(shù)組實現(xiàn)

2.1 基于簡單數(shù)組存在問題

2.2 第一種解決辦法

2.3 第二種解決辦法

2.4 動態(tài)數(shù)組實現(xiàn)棧代碼

2.5 性能和局限性

03.棧由鏈表實現(xiàn)

3.1 使用鏈表的優(yōu)勢

3.2 鏈表實現(xiàn)棧代碼

3.3 性能和局限性

04.Android棧Stack源碼分析

4.1 源碼展示

4.2 為何選用數(shù)組實現(xiàn)棧

05.創(chuàng)建加強版自定義棧

5.1 擴容和泛型

好消息

博客筆記大匯總【16年3月到至今】，包括Java基礎(chǔ)及深入知識點，Android技術(shù)博客，Python學(xué)習(xí)筆記等等，還包括平時開發(fā)中遇到的bug匯總，當(dāng)然也在工作之余收集了大量的面試題，長期更新維護(hù)并且修正，持續(xù)完善……開源的文件是markdown格式的！同時也開源了生活博客，從12年起，積累共計N篇[近100萬字，陸續(xù)搬到網(wǎng)上]，轉(zhuǎn)載請注明出處，謝謝！

鏈接地址：https://github.com/yangchong2...

如果覺得好，可以star一下，謝謝！當(dāng)然也歡迎提出建議，萬事起于忽微，量變引起質(zhì)變！

棧系列文章

00.?；A(chǔ)介紹

什么是棧？棧的使用場景？異常？棧的效率探索？

01.棧的實現(xiàn)原理

棧由簡單數(shù)據(jù)實現(xiàn)，棧由動態(tài)數(shù)組實現(xiàn)，棧由鏈表實現(xiàn)，創(chuàng)建加強版自定義棧，以及幾種不同實現(xiàn)棧的方式比較。

02.棧的常見操作

棧的順序存儲結(jié)構(gòu)及實現(xiàn)，棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)，兩種棧形式比較

03.使用棧判斷括號是否匹配

利用棧實現(xiàn)判斷字符串中的括號是否都是配對的，注意：“{[()]}”類似的可以匹配，“{(}}”類似的無法匹配。

04.使用棧實現(xiàn)字符串逆序

將字符串“how are you”反轉(zhuǎn)

05.用兩個棧實現(xiàn)隊列

用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。隊列中的元素為int類型。

06.棧的壓入、彈出序列

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。

07.使用棧解析計算器數(shù)學(xué)公式

解析一般數(shù)學(xué)算式，實現(xiàn)簡單的帶括號的加減乘除運算。

01.棧由簡單數(shù)組實現(xiàn) 1.1 簡單數(shù)組代碼實現(xiàn)

首先看一下實現(xiàn)的代碼

用數(shù)組實現(xiàn)棧，最主要的是要在類的內(nèi)部定義一個數(shù)組，并且這個數(shù)組要具有一定的大小，要在定義棧的時候定義好。

public class ArrayStack{
    private static final String TAG = "ArrayStack";
    private Object[] contents;
    private int top = -1;
    private int bottom = -1;
    private int SIZE = 10;//有一個初始值大小

    public ArrayStack(){
        contents = new Object[SIZE];
        top = -1;
    }

    public int push(Object obj) throws Exception {
        if (top > SIZE) throw new Exception("小楊逗比，棧已經(jīng)滿了！");
        top++;
        contents[top] = obj;
        return top;
    }

    public Object pop() throws Exception{
        if (top == bottom) throw new Exception("小楊逗比，棧已經(jīng)空了！");
        Object obj = contents[top];
        contents[top] = null;
        top--;
        return obj;
    }

    public boolean isEmpty(){
        return top == bottom;
    }

    public int getSize(){
        return top + 1;
    }

    public void display() throws Exception{
        if (getSize() == 0) throw new Exception("空棧!");
        for (int i=getSize()-1;i>=0;i--){
            System.out.print(contents[i].toString() + "->");
        }
        System.out.println("");
    }
} 


public void test{
    ArrayStack as = new ArrayStack();
    //as.display();
    as.push("小楊逗比");
    as.push("瀟湘劍雨");
    as.push("yc");
    as.push("逗比");
    as.push("aaa");
    as.push("ertte");
    as.push("hello");
    as.display();
    as.pop();
    System.out.println(as.getSize());
    as.pop();
    as.display();
}

1.2 可能出現(xiàn)問題

可能會出現(xiàn)的問題

當(dāng)數(shù)組棧存滿了元素的時候，如果執(zhí)行插入數(shù)據(jù)，將會拋出棧滿異常。

當(dāng)數(shù)組棧沒有元素的時候，如果執(zhí)行出棧數(shù)據(jù)，將會拋出?？债惓！?/p>

1.3 性能和局限性

性能和局限性分析

棧的最大空間必須提前聲明，而且關(guān)鍵是大小還不能改變，這就蛋疼了。所以會出現(xiàn)執(zhí)行入棧或者出棧操作時會出現(xiàn)異常。那么解決異常就是每次入棧判斷棧是否存儲滿，每次出棧判斷棧是否為空。

假設(shè)棧中有m個元素，基于簡單數(shù)組實現(xiàn)的棧。棧的出棧，入棧，判空，獲取大小等時間復(fù)雜度都是O(1)。

02.棧由動態(tài)數(shù)組實現(xiàn) 2.1 基于簡單數(shù)組存在問題

基于簡單數(shù)組的棧實現(xiàn)方法中，采用一個下標(biāo)變量top，它始終指向棧中最新插入元素的位置。

當(dāng)插入元素時，會增加top值，并且會在數(shù)組該下標(biāo)的位置存儲新的元素。

當(dāng)刪除元素時，先獲取下標(biāo)變量top位置的元素，然后減小變量top的值。

當(dāng)top下標(biāo)變量為-1時，表示棧是空的。但是存在問題是：在固定大小的數(shù)組中，如何處理所有空間都已經(jīng)保存棧元素這種情況？？？

2.2 第一種解決辦法

可能首先會想到，每次將數(shù)組大小增加1或者減小1，將會怎么樣？

插入元素，棧的空間大小增加1

刪除元素，棧的空間大小減去1

這樣做存在極大問題

頻繁增加數(shù)組大小的方法開銷很大。為什么這樣說呢？

當(dāng)n=3時，執(zhí)行push插入元素操作，當(dāng)插入第四條元素時，會新建一個大小為4的數(shù)組，然后復(fù)制原數(shù)組中所有的元素到新的數(shù)組中，然后在新的數(shù)組中的末尾添加插入元素。以此類推，每次插入數(shù)據(jù)，都會重新創(chuàng)建一個新的數(shù)組對象，然后拷貝舊的數(shù)組數(shù)據(jù)到新的數(shù)組中來，然后在末尾添加新元素，這樣做實在不好。

2.3 第二種解決辦法

在第一種解決辦法中改造。比如我們經(jīng)常聽到ArrayList集合動態(tài)擴容，先指定數(shù)組的長度，如果數(shù)組空間已滿，則新建一個比原數(shù)據(jù)大一倍[或者n倍]的新數(shù)組，再然后復(fù)制元素。

采用這種方式，插入元素操作，開銷相對來說要小很多。

2.4 動態(tài)數(shù)組實現(xiàn)棧代碼

基于動態(tài)數(shù)據(jù)實現(xiàn)棧的代碼如下所示

class DynArrayStack{
    private int top;
    private int capacity;
    private int[] array;
 
    private void doubleStack(){
        int[] newArray=new int[capacity*2];
        System.arraycopy(array,0,newArray,0,capacity);
        capacity=capacity*2;
        array=newArray;
    }
 
    public DynArrayStack(){
        top=-1;
        capacity=1;
        array=new int[capacity];
    }
 
    public boolean isEmpty(){
        return (top==-1);
    }
 
    public boolean isStackFull(){
        return (top==capacity-1);
    }
 
    public void push(int date){
        if(isStackFull()){
            doubleStack();
        }
        array[++top]=date;
    }
 
    public int pop(){
        if(isEmpty()){
            System.out.println("Stack Empty");
            return 0;
        }else {
            return array[top--];
        }
    }
 
    public void deleteStack(){
        top=-1;
    }
}
 
public class Main {
 
    public static void main(String[] args) {
        // write your code here
        DynArrayStack dynArrayStack=new DynArrayStack();
        dynArrayStack.push(1);
        dynArrayStack.push(2);
        dynArrayStack.push(3);
        System.out.println(dynArrayStack.pop());
        System.out.println(dynArrayStack.pop());
        System.out.println(dynArrayStack.pop());
    }
}

2.5 性能和局限性

性能

假設(shè)有n個元素的棧，基于動態(tài)數(shù)組的棧實現(xiàn)中，關(guān)于棧插入數(shù)據(jù)，取出數(shù)據(jù)的時間復(fù)雜度都是O(1)。

可能導(dǎo)致的性能問題：倍增太多可能導(dǎo)致內(nèi)存溢出。

存在局限性

是用數(shù)組實現(xiàn)棧，在定義數(shù)組類型的時候，也就規(guī)定了存儲在棧中的數(shù)據(jù)類型，那么同一個棧能不能存儲不同類型的數(shù)據(jù)呢？（聲明為Object）？

棧需要初始化容量，而且數(shù)組實現(xiàn)的棧元素都是連續(xù)存儲的，那么能不能不初始化容量呢？（改為由鏈表實現(xiàn)）？

03.棧由鏈表實現(xiàn) 3.1 使用鏈表的優(yōu)勢

棧規(guī)模的增加和減小都很簡潔，而且每個操作都是常數(shù)時間開銷，每個操作都要使用額外的空間和時間開銷來處理指針。

3.2 鏈表實現(xiàn)棧代碼

入棧的順序是：1 2 3 4 5，那么保證出棧的順序是5 4 3 2 1，以此類推讓head節(jié)點指向棧頂節(jié)點保證讓其倒序輸出。

public class MyStack {
    private T data;
    private MyStack next;
 
    public MyStack(T data, MyStack next) {
        this.data = data;
        this.next = next;
    }
 
    public T getData() {
        return data;
    }
 
    public void setData(T data) {
        this.data = data;
    }
 
    public MyStack getNext() {
        return next;
    }
 
    public void setNext(MyStack next) {
        this.next = next;
    }
}

public class LinkStack {
 
    private MyStack head;
    private MyStack tail;
    private Integer size=0;
 
    public MyStack getHead() {
        return head;
    }
 
    public void setHead(MyStack head) {
        this.head = head;
    }
 
    public MyStack getTail() {
        return tail;
    }
 
    public void setTail(MyStack tail) {
        this.tail = tail;
    }
 
    public Integer getSize() {
        return size;
    }
 
    public void setSize(Integer size) {
        this.size = size;
    }
 
    public void addStack(N data){
        MyStack node = new MyStack<>(data,null);
        if(headIsNull()){
            head = node;
            tail = node;
            size++;
        }else{
            //新加入的node是:(data,null) 讓這個新的node的next指向初始的head節(jié)點 head變?yōu)?data,head))
            node.setNext(head);
            head = node;
            size++;
        }
    }
 
    public N outStack(){
        if(size>0){
            N outData = head.getData();
            head = head.getNext();
            return outData;
        }else{
            throw new RuntimeException("棧里無元素!");
        }
    }
 
    public boolean headIsNull(){
        if(head == null){
            return true;
        }
        return false;
    }
}

測試一下

public void test() {
    LinkStack linkStack = new LinkStack<>();
    linkStack.addStack(1);
    linkStack.addStack(2);
    linkStack.addStack(3);
    linkStack.addStack(4);
    linkStack.addStack(5);

    for(int i=0;i


3.3 性能和局限性

假設(shè)棧中有n個元素，基于鏈表的棧實現(xiàn)中，關(guān)于棧插入元素和取出元素的時間復(fù)雜度是O(1)
數(shù)據(jù)入棧和出棧的時間復(fù)雜度都為O(1)，也就是說棧操作所耗的時間不依賴棧中數(shù)據(jù)項的個數(shù)，因此操作時間很短。而且需要注意的是棧不需要比較和移動操作。

04.棧Stack源碼分析

在Android中，對于activity使用棧stack進(jìn)行管理的，下面看看棧源代碼。
可以看到棧stack是實現(xiàn)vector，其實底層也是用數(shù)組來實現(xiàn)的。
public class Stack extends Vector {
    /**
     * 創(chuàng)建一個空的棧對象
     */
    public Stack() {
    }

    /**
     * 將對象推送到此堆棧的頂部。
     */
    public E push(E item) {
        addElement(item);

        return item;
    }

    /**
     * 移除此堆棧頂部的對象，并將該對象作為此函數(shù)的值返回。
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * 查看此堆棧頂部的對象，而不將其從堆棧中移除。
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * 判斷是否是空棧
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 返回對象位于此堆棧上的基于1的位置。
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    private static final long serialVersionUID = 1224463164541339165L;
}

05.創(chuàng)建加強版自定義棧

一個能自動擴容，第二個能存儲各種不同類型的數(shù)據(jù)，解決辦法如下：
public class ArrayStack {
    //存儲元素的數(shù)組,聲明為Object類型能存儲任意類型的數(shù)據(jù)
    private Object[] elementData;
    //指向棧頂?shù)闹羔?    private int top;
    //棧的總?cè)萘?    private int size;
     
     
    //默認(rèn)構(gòu)造一個容量為10的棧
    public ArrayStack(){
        this.elementData = new Object[10];
        this.top = -1;
        this.size = 10;
    }
     
    public ArrayStack(int initialCapacity){
        if(initialCapacity < 0){
            throw new IllegalArgumentException("棧初始容量不能小于0: "+initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.top = -1;
        this.size = initialCapacity;
    }
     
     
    //壓入元素
    public Object push(Object item){
        //是否需要擴容
        isGrow(top+1);
        elementData[++top] = item;
        return item;
    }
     
    //彈出棧頂元素
    public Object pop(){
        Object obj = peek();
        remove(top);
        return obj;
    }
     
    //獲取棧頂元素
    public Object peek(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return elementData[top];
    }
    //判斷棧是否為空
    public boolean isEmpty(){
        return (top == -1);
    }
     
    //刪除棧頂元素
    public void remove(int top){
        //棧頂元素置為null
        elementData[top] = null;
        this.top--;
    }
     
    /**
     * 是否需要擴容，如果需要，則擴大一倍并返回true，不需要則返回false
     * @param minCapacity

     */
    public boolean isGrow(int minCapacity){
        int oldCapacity = size;
        //如果當(dāng)前元素壓入棧之后總?cè)萘看笥谇懊娑x的容量，則需要擴容
        if(minCapacity >= oldCapacity){
            //定義擴大之后棧的總?cè)萘?            int newCapacity = 0;
            //棧容量擴大兩倍(左移一位)看是否超過int類型所表示的最大范圍
            if((oldCapacity<<1) - Integer.MAX_VALUE >0){
                newCapacity = Integer.MAX_VALUE;
            }else{
                newCapacity = (oldCapacity<<1);//左移一位，相當(dāng)于*2
            }
            this.size = newCapacity;
            int[] newArray = new int[size];
            elementData = Arrays.copyOf(elementData, size);
            return true;
        }else{
            return false;
        }
    }
}
```



其他介紹
01.關(guān)于博客匯總鏈接

1.技術(shù)博客匯總

2.開源項目匯總

3.生活博客匯總

4.喜馬拉雅音頻匯總

5.其他匯總


02.關(guān)于我的博客

github：https://github.com/yangchong211

知乎：https://www.zhihu.com/people/...

簡書：http://www.jianshu.com/u/b7b2...

csdn：http://my.csdn.net/m0_37700275

喜馬拉雅聽書：http://www.ximalaya.com/zhubo...

開源中國：https://my.oschina.net/zbj161...

泡在網(wǎng)上的日子：http://www.jcodecraeer.com/me...

郵箱：[email protected]
阿里云博客：https://yq.aliyun.com/users/a... 239.headeruserinfo.3.dT4bcV
segmentfault頭條：https://segmentfault.com/u/xi...

掘金：https://juejin.im/user/593943...

云服務(wù)器 GPU云服務(wù)器棧的實現(xiàn)與應(yīng)用隊列實現(xiàn)原理 cdn實現(xiàn)原理 webrtc實現(xiàn)原理

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

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

發(fā)表評論

登陸后可評論

0條評論

soasme

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow

閱讀 3578·2023-04-26 02:05
GDI繪制Winform工作流組件、具有獨立圖層的增刪處理、防PPT效果

閱讀 2022·2021-11-19 11:30
外貿(mào)網(wǎng)站如何選擇服務(wù)器?外貿(mào)網(wǎng)站服務(wù)器價格多少錢?

閱讀 4233·2021-09-30 09:59
新型硅陽極電池走向市場，有望改變電子設(shè)備和電動汽車市場

閱讀 3185·2021-09-10 10:51
安科視頻監(jiān)控產(chǎn)品中的遠(yuǎn)程代碼執(zhí)行漏洞允許黑客入侵設(shè)備

閱讀 2615·2021-09-01 10:30
raksmart：韓國獨立服務(wù)器測評（大陸優(yōu)化線路）

閱讀 1497·2021-08-11 11:20
css3 動畫（二）貝塞爾曲線

閱讀 2626·2019-08-30 15:54
CSS雙飛翼布局

閱讀 572·2019-08-30 10:49

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

棧的實現(xiàn)原理

相關(guān)文章

實現(xiàn)一個前端路由，如何實現(xiàn)瀏覽器的前進(jìn)與后退？

javasctipt 工作原理之調(diào)用棧

【協(xié)程原理】 - 為什么greenlet的狀態(tài)無法被保存

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列

學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一）：棧與隊列

發(fā)表評論

0條評論

soasme

男|高級講師

TA的文章

tensorflow

GDI繪制Winform工作流組件、具有獨立圖層的增刪處理、防PPT效果

外貿(mào)網(wǎng)站如何選擇服務(wù)器?外貿(mào)網(wǎng)站服務(wù)器價格多少錢?

新型硅陽極電池走向市場，有望改變電子設(shè)備和電動汽車市場

安科視頻監(jiān)控產(chǎn)品中的遠(yuǎn)程代碼執(zhí)行漏洞允許黑客入侵設(shè)備

raksmart：韓國獨立服務(wù)器測評（大陸優(yōu)化線路）

css3 動畫（二）貝塞爾曲線

CSS雙飛翼布局

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

棧的實現(xiàn)原理

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！