棧的實(shí)現(xiàn)原理

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

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

目錄介紹

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

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

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

1.3 性能和局限性

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

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

2.2 第一種解決辦法

2.3 第二種解決辦法

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

2.5 性能和局限性

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

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

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

3.3 性能和局限性

04.Android棧Stack源碼分析

4.1 源碼展示

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

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

5.1 擴(kuò)容和泛型

好消息

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

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

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

棧系列文章

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

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

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

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

02.棧的常見操作

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

03.使用棧判斷括號(hào)是否匹配

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

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

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

05.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

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

06.棧的壓入、彈出序列

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

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

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

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

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

用數(shù)組實(shí)現(xiàn)棧，最主要的是要在類的內(nèi)部定義一個(gè)數(shù)組，并且這個(gè)數(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;//有一個(gè)初始值大小

    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)問題

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

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

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

1.3 性能和局限性

性能和局限性分析

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

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

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

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

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

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

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

2.2 第一種解決辦法

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

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

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

這樣做存在極大問題

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

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

2.3 第二種解決辦法

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

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

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

基于動(dòng)態(tài)數(shù)據(jù)實(shí)現(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個(gè)元素的棧，基于動(dòng)態(tài)數(shù)組的棧實(shí)現(xiàn)中，關(guān)于棧插入數(shù)據(jù)，取出數(shù)據(jù)的時(shí)間復(fù)雜度都是O(1)。

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

存在局限性

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

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

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

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

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

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

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) 讓這個(gè)新的node的next指向初始的head節(jié)點(diǎn) 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個(gè)元素，基于鏈表的棧實(shí)現(xiàn)中，關(guān)于棧插入元素和取出元素的時(shí)間復(fù)雜度是O(1)
數(shù)據(jù)入棧和出棧的時(shí)間復(fù)雜度都為O(1)，也就是說棧操作所耗的時(shí)間不依賴棧中數(shù)據(jù)項(xiàng)的個(gè)數(shù)，因此操作時(shí)間很短。而且需要注意的是棧不需要比較和移動(dòng)操作。

04.棧Stack源碼分析

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

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

        return item;
    }

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

        return obj;
    }

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

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

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

    /**
     * 返回對(duì)象位于此堆棧上的基于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)建加強(qiáng)版自定義棧

一個(gè)能自動(dòng)擴(kuò)容，第二個(gè)能存儲(chǔ)各種不同類型的數(shù)據(jù)，解決辦法如下：
public class ArrayStack {
    //存儲(chǔ)元素的數(shù)組,聲明為Object類型能存儲(chǔ)任意類型的數(shù)據(jù)
    private Object[] elementData;
    //指向棧頂?shù)闹羔?    private int top;
    //棧的總?cè)萘?    private int size;
     
     
    //默認(rèn)構(gòu)造一個(gè)容量為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){
        //是否需要擴(kuò)容
        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--;
    }
     
    /**
     * 是否需要擴(kuò)容，如果需要，則擴(kuò)大一倍并返回true，不需要?jiǎng)t返回false
     * @param minCapacity

     */
    public boolean isGrow(int minCapacity){
        int oldCapacity = size;
        //如果當(dāng)前元素壓入棧之后總?cè)萘看笥谇懊娑x的容量，則需要擴(kuò)容
        if(minCapacity >= oldCapacity){
            //定義擴(kuò)大之后棧的總?cè)萘?            int newCapacity = 0;
            //棧容量擴(kuò)大兩倍(左移一位)看是否超過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.開源項(xiàng)目匯總

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

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

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/77490.html

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

登陸后可評(píng)論

0條評(píng)論

soasme

男|高級(jí)講師

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

TA的文章

tensorflow

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

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

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

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

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

閱讀 1491·2021-08-11 11:20
css3 動(dòng)畫（二）貝塞爾曲線

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

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

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

棧的實(shí)現(xiàn)原理

相關(guān)文章

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

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

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

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

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

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

0條評(píng)論

soasme

男|高級(jí)講師

TA的文章

tensorflow

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

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

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

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

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

css3 動(dòng)畫（二）貝塞爾曲線

CSS雙飛翼布局

最新活動(dòng)

資訊專欄INFORMATION COLUMN

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

棧的實(shí)現(xiàn)原理

相關(guān)文章

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

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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