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

来源: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;
}

 


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

更多相關文章
  • 前段時間公司根據要求需要將聚石塔上伺服器從杭州整體遷移到張家口,剛好趁這次機會將這些亂七八糟的伺服器做一次梳理和整合,斷斷續續一個月遷移完 成大概優化掉了1/3的機器,完成之後遇到了一些問題,比如曾今零零散散部署在生產上一些可視化UI:apollo,kibana,grafana,jenkins 等等 ...
  • 1. Self Encapsulate Field(自封裝值域) 你直接訪問一個值域,但與值域之間的耦合關係逐漸變得笨拙。為這個值域建立取值/設值函數(get/set),並且只以這些函數來訪問值域。 應用場景:如果你想訪問superclass中的一個值域,卻又想在subclass中將[對這個變數的訪 ...
  • 場景 Ubuntu Server 16.04 LTS上怎樣安裝下載安裝Nginx並啟動: https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/102828075 Nginx的配置文件位置以及組成部分結構講解: https://blog. ...
  • 添加依賴 <dependency> <groupId>io.netty</groupId> <artifactId>netty-all</artifactId> <version>4.1.2.Final</version> </dependency> <dependency> <groupId>or ...
  • 場景 Ubuntu Server 16.04 LTS上怎樣安裝下載安裝Nginx並啟動: https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/102828075 Nginx的配置文件位置以及組成部分結構講解: https://blog. ...
一周排行
x