詳解資料結構中堆疊的定義和操作-有解無憂

摘要：本文為大家詳解資料結構中堆疊的定義和操作，

本文分享自華為云社區《資料結構：詳細講解堆疊的定義、堆疊的操作》，作者：高彬滔，

1.堆疊的定義

堆疊（stack）：是只允許在一端進行插入或者洗掉操作的線性表（即后進先出，大概可以理解為吃飽了吐出來）

空堆疊：不含元素的空標配
堆疊頂：表尾端
堆疊底：表頭端

進堆疊順序：a1->a2->a3->a4->a5
出堆疊順序：a5->a4-a3->a2->a1

2.對比線性表和堆疊基本操作

2.1 線性表的基本操作

InitList(&L):初始化表，構造一個空的線性表L，分配記憶體空間
DestoryList(&L):銷毀操作，銷毀線性表，并且釋放線性表L所占用的空間
ListInsert(&L,i,e):插入操作，在表L中的第i個位置上插入指定元素e
ListDelete(&L,i,e):洗掉操作，洗掉表L中的第i個位置的元素，并且用e回傳洗掉元素的值
LocateElem(L,e):按值查找操作，在表L中查找具有給定關鍵字值的元素
GetElem(L,i):按位查找操作，獲取表L中第i個位置的元素的值

2.2 堆疊的基本操作

InitStack(&S):初始化堆疊，構造一個空堆疊S，分配記憶體空間
DestoryStack(&S):銷毀堆疊，銷毀并釋放堆疊S所占用的記憶體空間
Push(&S,x):進堆疊，若堆疊S未滿，則將x加入使之成為新的堆疊頂
Pop(&S,&x):出堆疊，若堆疊S非空，則彈出堆疊頂元素，并用x回傳
GetTop(S,&x):讀堆疊頂元素，若堆疊S非空，則用x回傳堆疊頂元素

其他常見操作： StackEmpty(S):判斷一個堆疊S是否為空，若S為空，則回傳true，否則回傳false

3.順序堆疊

3.1順序堆疊的定義

#define MaxSize 10           //定義堆疊中元素的最大個數 
typedef struct{
 ElemType data[MaxSize];   //靜態陣列存放堆疊中的元素
    int top;      //堆疊頂指標
}SqStack;         //結構體重命名

宣告一個順序堆疊后就會在記憶體中分配一整片連續的空間,其中記憶體大小為:MaxSize*sizeof(ELemType)

void testStack(){
 SqStack S; //宣告一個順序堆疊
}

3.2堆疊的初始化操作

由于堆疊頂指標top需要指向此時堆疊頂元素，所以讓top指向0是不合理的，可以初始化讓top指向-1;判斷一個堆疊是否為空，即判斷S.top是否等于-1

初始化堆疊：

void Inittack(SqStack){
 SqStack S;   //宣告一個順序堆疊
 S.top=-1;
}

判斷堆疊空：

bool StackEmpty(SqStack S){
    if(S.top==-1)      //堆疊空
        return true;
    else 
        return false;  //非空
}

3.3進堆疊操作

分析：

判斷堆疊是否為空
堆疊頂指標+1
新元素入堆疊

bool Push(SqStack &S,ElemType x){
 if(S.top==NaxSize-1)
        return false;
 S.top+=1;
 S.data[S.top]=x;
        return true;
}

3.4出堆疊操作

bool Push(SqStack &S,ElemType &x){
 if(S.top==-1)
        return false;
    x=S.data[S.top--];
        return true;
}

3.5讀堆疊頂元素操作

bool GetTop(SqStack &S,ElemType &x){
 if(S.top==-1)
        return false;
    x=S.data[S.top];
        return true;
}

4.共享堆疊

兩個堆疊共享同一片空間

#define MaxSize 10           //定義堆疊中元素的最大個數 
typedef struct{
 ElemType data[MaxSize];   //靜態陣列存放堆疊中的元素
    int top0;     //0號堆疊堆疊頂指標
    int top1;     //1號堆疊堆疊頂指標
}SqStack;         //結構體重命名
初始化堆疊：
void InitStack(ShStack &S){
 S.top0=-1;
 S.top1=MaxSize;
}

5.鏈堆疊的定義

進堆疊/出堆疊都只能在堆疊頂一段進行
鏈頭作為堆疊頂

typedef struct Linknode{
 ElemType data;           //資料域
    struct Linknode *next;   //指標域
}*LiStack                    //堆疊型別定義

點擊關注，第一時間了解華為云新鮮技術~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550662.html

標籤：其他

上一篇：數字先鋒 | 乘“云”之勢，天翼云助力長春市婦產醫院步入智慧醫療新時代！

下一篇：返回列表