簡單談談棧

王偉廷發布于2019-08-16 14:35 / 3352人閱讀

摘要：一前言計算機程序離不開算法和數據結構，數據結構這門學科就是為了讓計算機能夠以更加高效，簡單，便捷的方式來存儲和使用數據而產生的。返回一個布爾值，表示當前是否為空棧。

一、前言

計算機程序離不開算法和數據結構，數據結構這門學科就是為了讓計算機能夠以更加高效，簡單，便捷的方式來存儲和使用數據而產生的。本文簡單介紹棧(Stack)和隊列(Queue)的實現

二、圖解

三、線性表

1、順序存儲結構：用一段地址連續的存儲單元依次存儲線性表的數據元素
2、鏈式存儲結構：用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也可以不連續，空間與內存沒有線性關系

四、棧 棧

1、只允許在一端進行插入和刪除操作的線性表

2、實現的功能

push：在最頂層加入數據。

pop：返回并移除最頂層的數據。

peek：返回最頂層數據的值，但不移除它。

empty：返回一個布爾值，表示當前stack是否為空棧。

2-1、初始化

private int[] arr;
    //常量用大寫
    private final static int SIZE = 1;
    //棧的當前指針
    private int index;

    //構造器沒有參數的
    public StackDemo() {
        arr = new int[SIZE];
        index = -1;
    }

2-2、push

//入棧
private void push(int target){
    if (index == SIZE){
        throw  new  StackOverflowError();
    }else {
        //剛開始為-1，要前加
        arr[++index] = target;
    }
}

2-3、peek

//返回棧頂元素
private int peek(){
    if (index == -1){
        throw new StackOverflowError();
    }else {
        return arr[index];
    }
}

2-4、empty

    //判空
    private boolean empty(){
        if (index == -1){
            return true;
        }
        return false;
    }

3、代碼實現

import java.util.Arrays;

/**
 *
 * @author buer
 * @date 2019/1/20
 */
public class StackDemo {
    private int[] arr;
    //常量用大寫
    private final static int SIZE = 1;
    //棧的當前指針
    private int index;

    //構造器沒有參數的
    public StackDemo() {
        arr = new int[SIZE];
        index = -1;
    }

    //入棧
    private void push(int target){
        if (index == SIZE){
            throw  new  StackOverflowError();
        }else {
            //剛開始為-1，要前加
            arr[++index] = target;
        }
    }

    //出棧
    private int pop(){
        if (index == -1){
            throw new StackOverflowError();
        }else {
            return arr[index--];
        }
    }

    //返回棧頂元素
    private int peek(){
        if (index == -1){
            throw new StackOverflowError();
        }else {
            return arr[index];
        }
    }

    //判空
    private boolean empty(){
        if (index == -1){
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        StackDemo stackDemo = new StackDemo();
        stackDemo.push(1);
        System.out.println(stackDemo.toString());
        stackDemo.pop();
        System.out.println(stackDemo.toString());

    }

    @Override
    public String toString() {
        return "StackDemo{" +
                "arr=" + Arrays.toString(arr) +
                ", index=" + index +
                "}";
    }
}

應用

1、括號匹配

2、中綴表達式（人類的思考）和后綴表達式（計算機的計算）

3、遞歸

4、瀏覽器的前進后退功能

參考資料

https://zh.wikipedia.org
https://www.zhihu.com/question/21318658
http://www.ruanyifeng.com/blog/2013/11/stack.html

GPU云服務器云服務器談談談談域名來談談談談區塊鏈

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

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

談談javascript語法里一些難點問題（二）

摘要：講作用域鏈首先要從作用域講起，下面是百度百科里對作用域的定義作用域在許多程序設計語言中非常重要。原文出處談談語法里一些難點問題二 3) 作用域鏈相關的問題作用域鏈是javascript語言里非常紅的概念，很多學習和使用javascript語言的程序員都知道作用域鏈是理解javascript里很重要的一些概念的關鍵，這些概念包括this指針，閉包等等，它非常紅的另一個重要原因就...

Enlightenment 2019-08-21 10:27 評論0 收藏0
談談JavaScript的詞法環境和閉包（一）

摘要：換句話說，定義在閉包中的函數可以記憶它被創建時候的環境。詞法環境的概念定義摘自百科。一個詞法環境由一個環境記錄項和可能為空的外部詞法環境引用構成。中使用詞法環境管理靜態作用域。一個資深的同事在我出發去面試前告誡我，問JS知識點的時候千萬別主動提閉包，它就是一個坑啊！坑啊！啊！閉包確實是js的難點和重點，其實也沒那么可怕，關鍵是機制的理解，可以和函數一起單獨拿出來說說，其實關于閉包的...

AlphaWatch 2019-08-20 10:31 評論0 收藏0
談談Java引用和Threadlocal的那些事

摘要：容易導致內存泄漏。如果我們的強引用不存在的話，那么就會被回收，也就是會出現我們沒被回收，被回收，導致永遠存在，出現內存泄漏。緩存行和一次定位，不會有沖突由于使用數組，不會出現回收，沒被回收的尷尬局面，所以避免了內存泄漏。 1 背景某一天在某一個群里面的某個群友突然提出了一個問題:threadlocal的key是虛引用，那么在threadlocal.get()的時候,發生GC之后，ke...

justjavac 2019-08-16 15:31 評論0 收藏0
談談javascript語法里一些難點問題（一）

摘要：引子前不久我建立的技術群里一位問了一個這樣的問題，她貼出的代碼如下所示執行結果如下所示第一個第二個這是一個令人詫異的結果，為什么第一個彈出框顯示的是，而不是呢這種疑惑的原理我描述如下一個頁面里直接定義在標簽下的變量是全局變量即屬于對象的變量 1) 引子前不久我建立的技術群里一位MM問了一個這樣的問題，她貼出的代碼如下所示： var a = 1; function hehe...

huaixiaoz 2019-08-21 10:27 評論0 收藏0