Hello,米娜桑們，這里是君兮_，我們繼續(xù)來學習初階數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，今天我們要講的是棧與隊列部分的內(nèi)容，這篇博客先講棧，隊列我們放到下次再講
好了，廢話不多說，開始今天的學習吧！—

一.棧

1.棧的概念及結(jié)構(gòu)

• 棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。

• 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
  出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
  

• 無論是入棧還是出棧，都遵循后進先出原則。

2.棧的實現(xiàn)方式

• 棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的不需要付出很大的代價。
  
• 如果使用鏈表方式實現(xiàn)的話，會出現(xiàn)一個問題，我們的棧實際上是通過尾插實現(xiàn)入棧的，也就是說在入棧時我們每一次都需要通過遍歷的方式找尾，或者使用雙頭循環(huán)鏈表的方式找尾，但是由于數(shù)組的連續(xù)性和支持隨機訪問，對比于鏈表無疑是更加方便的。因此，接下來內(nèi)容中的棧結(jié)構(gòu)我們就通過數(shù)組的方式實現(xiàn)。

3.棧的分類

• 棧分為靜態(tài)棧和動態(tài)棧

靜態(tài)棧

// 下面是定長的靜態(tài)棧的結(jié)構(gòu)，實際中一般不實用
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType a[N];
int _top; // 棧頂
int _capacity; // 容量
}Stack;

動態(tài)棧

• 動態(tài)棧是通過動態(tài)內(nèi)存開辟的方式實現(xiàn)的，由于支持動態(tài)內(nèi)存的變化，因此在實際應用中動態(tài)棧無疑是更好的選擇

typedef int STDataType;//方便以后修改棧中存儲的數(shù)據(jù)類型
typedef struct Stack
{
    STDataType* a;//數(shù)組
    int top;//存放棧中有效元素的個數(shù)
    int capacity;//棧的容量大小
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
bool StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);
//獲取棧底元素
STDataType StackTail(Stack* ps);

4.動態(tài)棧的實現(xiàn)

棧的初始化函數(shù) StackInit

• 無論是什么數(shù)據(jù)結(jié)構(gòu)，我們都得先初始化

// 初始化棧
void StackInit(Stack* ps)
{
    assert(ps);//斷言
    ps->a = NULL;//數(shù)組中還沒有元素
    //容量和有效元素都為0
    ps->capacity = 0;
    ps->top = 0;
}

入棧函數(shù) StackPush

// 入棧
void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    //判斷是否還有空間
    if (ps->capacity == ps->top)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//通過容量判斷此時棧中有沒有元素，如果沒有元素就申請4個字節(jié)的空間，如果有容量，但容量不夠時就把容量變?yōu)橹暗?倍
        STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType));
        if (tmp == NULL)//判讀開辟空間是否成功
        {
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;//成功了就把這個新的空間給我們的a數(shù)組
        ps->capacity = newCapacity;//容量也要做相應的動態(tài)變化
    }
    ps->a[ps->top] = data;//往棧中存元素
    ps->top++;//有效元素++
}

• 這里可能有些人對于動態(tài)內(nèi)存管理的內(nèi)容不夠了解，可以看看我這篇博客：【C語言進階】那些你必須掌握的C/C++要點——動態(tài)內(nèi)存管理(1)
• 這里還有一點要提，這里為什么用realloc開辟空間而不是使用malloc呢？
• 這里就涉及一些realloc的進階玩法
• 我們知道realloc是用來修改動態(tài)開辟的內(nèi)存大小，但是當我們給它傳入的是一個空指針，它的功能與malloc就是相同的。

出棧的函數(shù) StackPop

// 出棧
void StackPop(Stack* ps)
{
    assert(ps);
    --ps->top;
}

• 出棧就非常簡單啦，我們直接讓top減1就行，由于我們的數(shù)組是通過下標的方式訪問數(shù)組成員的，top只有減少就無法在找到相應的元素啦
  

獲取棧頂元素的函數(shù) StackTop

// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    //有效元素為top，數(shù)組的下標得-1
    return ps->a[ps->top-1];
}

• 我們棧中的元素是尾插的，因此最后一個元素就是我們的棧頂元素

獲取棧底元素 StackTail

• 需要棧底的情況其實并不常見，我們會在某些特別情況下才會用到（比如我們之后會帶大家寫的oj題）

STDataType StackTail(Stack* ps)
{
   assert(ps);
   return ps->a[0];
}

• 我們的元素是尾插進數(shù)組的，因此我們的首元素就是我們的棧底元素。

獲取棧中有效元素的個數(shù)的函數(shù) StackSize

// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}

• 我們在之前無論是入棧還是出棧都變化了我們的有效元素top，因此返回的top就是我們的有效元素個數(shù)。

判斷棧是否為空的函數(shù) StackEmpty

// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}

• top存著我們的有效元素，因此可以通過判斷top是否為0來判斷棧是否為空

銷毀棧的函數(shù)

// 銷毀棧
void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->a);//free掉動態(tài)開辟的數(shù)組
    ps->a = NULL;//置空
    ps->top = ps->capacity = 0;//把有效元素和容量全部清空
}

• 我們的內(nèi)存是通過動態(tài)開辟出來的，因此當我們使用完后就必須把我們的申請的內(nèi)存給free掉防止內(nèi)存泄漏。

5.測試棧

• 我們來試試的效果

void TestStack1()
{
    Stack ST;
    StackInit(&ST);
    StackPush(&ST, 10);
    StackPush(&ST, 20);
    StackPush(&ST, 30);
    while (!StackEmpty(&ST))
    {
        printf("%d ", StackTop(&ST));
        StackPop(&ST);
}
    
    StackDestroy(&ST);
   

}
int main()
{
    
    TestStack1();
    return 0;
}

總結(jié)

• 今天的內(nèi)容到這里就結(jié)束了，如果你能理解之前講過的順序表，鏈表等，棧的內(nèi)容其實非常的簡單，想學好的話，一定要自己動手試試哦！！
• 好了，如果你有任何疑問歡迎在評論區(qū)或者私信我提出，大家下次再見啦！

新人博主創(chuàng)作不易，如果感覺文章內(nèi)容對你有所幫助的話不妨三連一下這個新人博主再走唄。你們的支持就是我更新的動力?。?！

文章來源地址http://www.zghlxwxcb.cn/news/detail-638246.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】帶你圖文結(jié)合深入棧和隊列，并具體分步實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！