棧的實現原理

soasme 發布于2019-08-19 11:35 / 3457人閱讀

摘要：使用棧實現字符串逆序將字符串反轉用兩個棧實現隊列用兩個棧來實現一個隊列，完成隊列的和操作。假設棧中有個元素，基于簡單數組實現的棧。可以看到棧是實現，其實底層也是用數組來實現的。移除此堆棧頂部的對象，并將該對象作為此函數的值返回。

目錄介紹

01.棧由簡單數據實現

1.1 簡單數組代碼實現

1.2 可能出現問題

1.3 性能和局限性

02.棧由動態數組實現

2.1 基于簡單數組存在問題

2.2 第一種解決辦法

2.3 第二種解決辦法

2.4 動態數組實現棧代碼

2.5 性能和局限性

03.棧由鏈表實現

3.1 使用鏈表的優勢

3.2 鏈表實現棧代碼

3.3 性能和局限性

04.Android棧Stack源碼分析

4.1 源碼展示

4.2 為何選用數組實現棧

05.創建加強版自定義棧

5.1 擴容和泛型

好消息

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

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

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

棧系列文章

00.?；A介紹

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

01.棧的實現原理

棧由簡單數據實現，棧由動態數組實現，棧由鏈表實現，創建加強版自定義棧，以及幾種不同實現棧的方式比較。

02.棧的常見操作

棧的順序存儲結構及實現，棧的鏈式存儲結構及實現，兩種棧形式比較

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

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

04.使用棧實現字符串逆序

將字符串“how are you”反轉

05.用兩個棧實現隊列

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

06.棧的壓入、彈出序列

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

07.使用棧解析計算器數學公式

解析一般數學算式，實現簡單的帶括號的加減乘除運算。

01.棧由簡單數組實現 1.1 簡單數組代碼實現

首先看一下實現的代碼

用數組實現棧，最主要的是要在類的內部定義一個數組，并且這個數組要具有一定的大小，要在定義棧的時候定義好。

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("小楊逗比，棧已經滿了！");
        top++;
        contents[top] = obj;
        return top;
    }

    public Object pop() throws Exception{
        if (top == bottom) throw new Exception("小楊逗比，棧已經空了！");
        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 可能出現問題

可能會出現的問題

當數組棧存滿了元素的時候，如果執行插入數據，將會拋出棧滿異常。

當數組棧沒有元素的時候，如果執行出棧數據，將會拋出棧空異常。

1.3 性能和局限性

性能和局限性分析

棧的最大空間必須提前聲明，而且關鍵是大小還不能改變，這就蛋疼了。所以會出現執行入?；蛘叱鰲２僮鲿r會出現異常。那么解決異常就是每次入棧判斷棧是否存儲滿，每次出棧判斷棧是否為空。

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

02.棧由動態數組實現 2.1 基于簡單數組存在問題

基于簡單數組的棧實現方法中，采用一個下標變量top，它始終指向棧中最新插入元素的位置。

當插入元素時，會增加top值，并且會在數組該下標的位置存儲新的元素。

當刪除元素時，先獲取下標變量top位置的元素，然后減小變量top的值。

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

2.2 第一種解決辦法

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

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

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

這樣做存在極大問題

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

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

2.3 第二種解決辦法

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

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

2.4 動態數組實現棧代碼

基于動態數據實現棧的代碼如下所示

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 性能和局限性

性能

假設有n個元素的棧，基于動態數組的棧實現中，關于棧插入數據，取出數據的時間復雜度都是O(1)。

可能導致的性能問題：倍增太多可能導致內存溢出。

存在局限性

是用數組實現棧，在定義數組類型的時候，也就規定了存儲在棧中的數據類型，那么同一個棧能不能存儲不同類型的數據呢？（聲明為Object）？

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

03.棧由鏈表實現 3.1 使用鏈表的優勢

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

3.2 鏈表實現棧代碼

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

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節點 head變為(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 性能和局限性

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

04.棧Stack源碼分析

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

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

        return item;
    }

    /**
     * 移除此堆棧頂部的對象，并將該對象作為此函數的值返回。
     */
    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.創建加強版自定義棧

一個能自動擴容，第二個能存儲各種不同類型的數據，解決辦法如下：
public class ArrayStack {
    //存儲元素的數組,聲明為Object類型能存儲任意類型的數據
    private Object[] elementData;
    //指向棧頂的指針
    private int top;
    //棧的總容量
    private int size;
     
     
    //默認構造一個容量為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;
        //如果當前元素壓入棧之后總容量大于前面定義的容量，則需要擴容
        if(minCapacity >= oldCapacity){
            //定義擴大之后棧的總容量
            int newCapacity = 0;
            //棧容量擴大兩倍(左移一位)看是否超過int類型所表示的最大范圍
            if((oldCapacity<<1) - Integer.MAX_VALUE >0){
                newCapacity = Integer.MAX_VALUE;
            }else{
                newCapacity = (oldCapacity<<1);//左移一位，相當于*2
            }
            this.size = newCapacity;
            int[] newArray = new int[size];
            elementData = Arrays.copyOf(elementData, size);
            return true;
        }else{
            return false;
        }
    }
}
```



其他介紹
01.關于博客匯總鏈接

1.技術博客匯總

2.開源項目匯總

3.生活博客匯總

4.喜馬拉雅音頻匯總

5.其他匯總


02.關于我的博客

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...

泡在網上的日子：http://www.jcodecraeer.com/me...

郵箱：yangchong211@163.com
阿里云博客：https://yq.aliyun.com/users/a... 239.headeruserinfo.3.dT4bcV
segmentfault頭條：https://segmentfault.com/u/xi...

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

云服務器 GPU云服務器棧的實現與應用隊列實現原理 cdn實現原理 webrtc實現原理

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

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

實現一個前端路由，如何實現瀏覽器的前進與后退？

摘要：執行過程如下實現瀏覽器的前進后退第二個方法就是用兩個棧實現瀏覽器的前進后退功能。我們使用兩個棧，和，我們把首次瀏覽的頁面依次壓入棧，當點擊后退按鈕時，再依次從棧中出棧，并將出棧的數據依次放入棧。 showImg(https://segmentfault.com/img/bVbtK6U?w=1280&h=910); 如果要你實現一個前端路由，應該如何實現瀏覽器的前進與后退？ 2. 問題...

劉東 2019-08-23 18:01 評論0 收藏0
javasctipt 工作原理之調用棧

摘要：譯者注翻譯一個對新手比較友好的工作原理解析系列文章注意以下全部是概念經驗豐富的老鳥可以離場啦正文從這里開始隨著的流行團隊們正在利用來支持多個級別的技術棧包括前端后端混合開發嵌入式設備以及更多這篇文章旨在成為深入挖掘和實際上他是怎么工作的系列譯者注翻譯一個對新手比較友好的 JavaScript 工作原理解析系列文章注意: 以下全部是概念,經驗豐富的老鳥可以離場啦正文從這里開始隨...

Pines_Cheng 2019-08-23 10:38 評論0 收藏0
【協程原理】 - 為什么greenlet的狀態無法被保存

摘要：特別是最火的協程框架也無法保存狀態，讓人非常惋惜。但是因為棧的本身無法持久化，所以也就無法持久化。其難度在于，假設整個要持久化的調用棧全部都是內的，比如純的。采取的是暴力地把整個棧區域拷貝到上的方式來保存其狀態。 python主流的協程實現有五種： cPython的generator cPython的greenlet cPython的fibers stackless python ...

verano 2019-07-24 17:43 評論0 收藏0
學習數據結構與算法之棧與隊列

摘要：于是翻出了機房里的這本學習數據結構與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現各種數據結構和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算...

pingan8787 2019-08-20 18:37 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0