數據結構導論(第三章棧)

来源:https://www.cnblogs.com/jalja/archive/2019/11/01/11779283.html

鏈棧的定義: 棧的鏈式存儲結構稱為鏈棧,它是運算受限的單鏈表, 插入和刪除操作僅限制在表頭位置上進行。棧頂指針就是鏈 表的頭指針 ...


一、棧

棧和隊列可看作是特 殊的線性表,它們是 運算受限的線性表

定義:棧是只能在表的一端(表尾)進行 插入和刪除的線性表

  • 允許插入及刪除的一端(表尾)稱為棧頂(Top); .
  • 另一端(表頭)稱為棧底(Bottom)。 .
  • 當表中沒有元素時稱為空棧
  • 進棧——在棧頂插入一元素;
  • 出棧——在棧頂刪除一元素

特點:後進先出

  棧中元素按a1,a2,a3,…an的次序進棧,出棧的第一個元素應 為棧頂元素。換句話說,棧的修改是按後進先出的原則進行的。 因此,棧稱為後進先出線性表(LIFO)。

棧的用途:常用於暫時保存有待處理的數據

棧的基本操作

  • (1)初始化棧:InitStack(S);
  • (2)判棧空:EmptyStack (S);
  • (3)進棧:Push (S,x);
  • (4)出棧:Pop (S);
  • (5)取棧頂: GetTop(S);

棧的分類:按照順序結構存儲是順序棧、按照鏈式結果存儲是鏈棧

二、順序棧

順序棧—— 即棧的順序實現;

棧容量——棧中可存放的最大元素個數;

棧頂指針 top——指示當前棧頂元素在棧中的位置;

棧空——棧中無元素時,表示棧空;

棧滿——數組空間已被占滿時,稱棧滿;

下溢——當棧空時,再要求作出棧運算,則稱“下溢”;

上溢——當棧滿時,再要求作進棧運算,則稱“上溢”。

 

1、順序棧的類型定義

const int maxsize=6;
typedef struct seqstack {
  DataType data[maxsize];
  int top;
}SeqStk;

SeqStk *s ; 定義一順序棧s
約定棧的第1個元素存在data[1]中,則
s->top==0 代表順序棧s為空;
s->top==maxsize-1 代表順序棧s為滿

2、初始化:

int Initstack(SeqStk *stk){
    stk->top=0;
    return 1;
}

3、判棧空(棧空時返回值為1,否則返回值為0)

int EmptyStack(SeqStk *stk){
    if(stk->top= =0) return 1;
    else return 0;
}

4、進棧

int Push(SeqStk *stk, DataType x){
    /*數據元素x進順序棧sq*/
    if(stk->top==maxsize -1) /*判是否上溢*/
    { error(“棧滿”);return 0;} /*上溢*/
    else {
        stk->top++;/*修改棧頂指針,指向新棧頂*/
        stk->data[stk->top]=x; /*元素x插入新棧頂中*/
        return 1;
    }
    }
}

 5、出棧

int Pop(SeqStk *stk){
    /*順序棧sq的棧頂元素退棧*/
    if(stk->top==0) /*判是否下溢*/
    { error(“棧空”);return 0;} /*下溢*/
    else {
    stk->top-- ; /*修改棧頂指針,指向新棧頂*/
    return 1;
    }
}/*Pop*/

6、取棧頂元素

DataType GetTop(SeqStk *stk)
{
if(EmptyStack(stk))
return NULLData;
else
return stk->data[stk->top];
}

三、鏈棧

鏈棧的定義: 棧的鏈式存儲結構稱為鏈棧,它是運算受限的單鏈表, 插入和刪除操作僅限制在表頭位置上進行。棧頂指針就是鏈 表的頭指針

 

 

 

 

1、初始化

void InitStack(LkStk *LS)
{
  LS=(LkStk *)malloc(sizeof(LkStk));
  LS->next=NULL;
}

2、判棧空

int EmptyStack(LkStk *LS)
{
    if(LS->next= =NULL) return 1;
    else return 0;
}

3、進棧——在棧頂插入一元素x

 

 

void Push (LkStk *LS, DataType x){ 
    LkStk *temp;
    temp= (LkStk *) malloc (sizeof (LkStk));
    temp->data=x;
    temp->next=LS->next;
    LS->next=temp;
}

4、出棧——在棧頂刪除一元素,並返回

 

 

int Pop (LkStk *LS)
{
    LkStk *temp;
    if (!EmptyStack (LS))
    {
        temp=LS->next;
        LS->next=temp->next;
        free(temp);
        return 1;
    }
    else return 0;
}

5、取棧頂元素

DataType GetTop(LkStk *LS)
{
    if (!EmptyStack(LS))
    return LS->next->data;
    else
    return NULLData;
}

 


您的分享是我們最大的動力!

更多相關文章
  • 本文由葡萄城技術團隊於博客園原創並首發 轉載請註明出處:葡萄城官網,葡萄城為開發者提供專業的開發工具、解決方案和服務,賦能開發者。 前端技術的發展日新月異,過一段時間就會出現新的框架、工具、插件,伴隨著十幾年的發展,前端領域已經告別了野蠻生長的時期,越發表現出成熟和現代化,引領了整個技術行業的潮流, ...
  • 網上查了很多圖片懶載入的內容, 但基本上都是jQuery實現的, 沒有說清楚其原理, 所以研究了一下 多的不說, 上代碼, 看不明白的建議看下我的上一篇文章<1. 圖解瀏覽器和用戶設備的寬高等屬性> HTML部分(圖片地址自己隨意) JS部分 雖然比較啰嗦, 但是內容詳細. 希望能幫到大家 最終效果 ...
  • 有一個單選下拉框要改成多選,裡面還有一個全部選項,當選擇全部時要全部勾選上,類似於樹形下拉框。效果如下: 傳到後臺的數據就根據自己的需要做修改了,當選擇全部時就只傳全部這一個值,但後臺查出來的數據是要滿足所有項的,當然取消全部時在查詢的時候也還是要滿足所有項。代碼如下: 添加fSelect.css, ...
  • 原創作品,轉載請註明來源, "sogeisetsu" ,我的csdn上也有這篇文章 "csdn" js屬性,封裝性,prototype綜合解析 用實例來解釋以下js的公有屬性,靜態屬性,實例屬性,prototype和封裝性 下麵是我在寫博客的源代碼,您可以先不要看他,先看下麵的文字部分 先搞清楚原型 ...
  • 當我們在組件間切換的時候,Angular都會銷毀上一個組件,並且創建一個新的組件。在大多數情況下,我們可能不想讓它這樣工作,因為每次載入一個組件,可能會有很多類似HTTP請求一樣的昂貴的操作。 這時候就需要RouteReuseStrategy了。 ...
  • 16個常見屬性 6個常見的瀏覽器窗體屬性 document.documentElement.clientWidth 瀏覽器可視區域寬度 document.documentElement.clientHeight 瀏覽器可視區域高度 document.documentElement.scrollWid ...
  • 最近做控制項遇到含有波浪圖的圖表,一開始用Echarts雖然很快完成了,但Echarts的波浪圖與其他圖表的響應式不同步,於是學習了D3js,D3js寫起來確實複雜一些,但能夠實現的效果也更豐富,做的時候查了不少資源,講真的,網上教程挺少的,很多都重覆,我分享下我的方法。 先看一下效果: 我只做了簡單 ...
  • 前言: 簡單的操作 1)可以通過審查元素的方法,來設置自己滿意的樣式。操作是F12。F12操作可以打開控制面板,具體的樣式可以直接在上面修改,然後把修改後的樣式保存下來。 2)保存後的樣式,複製到[ 管理 ] - [ 設置 ] - 頁面定製CSS代碼上面,然後[ 保存 ] 1、隱藏廣告 2、按鈕樣式 ...
一周排行
  • C 語法糖——持續更新 1. return的switch寫法 ...
  • 0. 前言 繼上一篇,以及上上篇,我們對SqlSugar有了一個大概的認識,但是這並不完美,因為那些都是理論知識,無法描述我們工程開發中實際情況。而這一篇,將帶領小伙伴們一起試著寫一個能在工程中使用的模板類。 1. 創建一個Client SqlSugar在操作的時候需要一個Client,用來管理數據 ...
  • 1 class Program 2 { 3 static void Main(string[] args) 4 { 5 //數組:長度不可變,類型單一 6 //ArrayList集合:長度可以任意改變,類型可以不單一 7 8 //創建一個ArrayList對象 9 ArrayList mylist ...
  • .NET 程式下銳浪報表 (Grid++ Report) 的綠色發佈指南 在銳浪報表官方為 CSharp 編寫的開發文檔:“在C#與VB.NET中開始使用說明.txt” 中,關於發佈項目是這麼描述的: ★發佈你的項目,用VS.NET製作安裝程式:1、先創建安裝項目:在解決方案資源管理器的根節點上點右 ...
  • 執行代碼清理時,可以點擊那個掃把小圖片,會按照預設的第一種配置文件來自動修複。也可以點擊下拉三角符合,選擇不同的配置文件,然後進行修複。或者快捷鍵Ctrl+K,Ctrl+E。 針對每一項配置的說明: 刪除不必要的using 儘可能將私有欄位設置為只讀 刪除不必要的類型轉換(針對強類型轉換),像Con ...
  • 1.概念簡述 (1)AR模型 AR 模型(auto regressive model)自回歸模型,模型參量法高解析度譜分析方法之一,也是現代譜估計中常用的模型。 用AR模型法求信具體作法是: ①選擇AR模型,在輸入是衝激函數或白雜訊的情況下,使其輸出等於所研究的信號,至少,應是對該信號的一個好的近似 ...
  • 4.元組 元組的主要特性為: 1.元組在創建之後,具有不可以更改的特性,因此不能直接給元組的元素賦值 2.元組的元素類型可以為任意類型,如字典、字元串、列表等 3.元組常用於在程式的整個生命周期中都不變的場景中 4.1 常用方法 元組大小和內容在定義賦值之後,就不可更改,常用的方法如下所示: cou ...
  • 老孟導讀:今天分享一個類似“孔雀開屏”的動畫效果,打開新的頁面時,新的頁面從屏幕右上角以圓形逐漸打開到全屏。 先來看下具體的效果 不知道這種效果大家叫什麼名字?如果有更合適的名字可以在評論處告訴我,下麵來說下如何實現此效果。 在使用Navigator進入一個新的頁面時,通常用法如下: 就包含了切換頁 ...
  • hashCode() 和equals() 方法的重要性體現在什麼地方? Java中的HashMap使用hashCode()和equals()方法設置值,根據鍵獲取值的時候也會用到這兩個方法。 怎樣 設置 的值? hashCode()獲得 hash值。而hash值用來確定hashmap中內部 Node ...
  • IDEA一些不錯的插件分享 目錄 IDEA一些不錯的插件分享 插件集合 CamelCase Translation LiveEdit MarkDown Navigator Jrebel CheckStyle IDEA Alibaba Java Coding Guidelines Ideavim Ma ...