目錄

1->棧的概念和結(jié)構(gòu)

1.1棧的概念

?1.2棧的結(jié)構(gòu)

?2->棧的實(shí)現(xiàn)

2.1定義關(guān)于棧的結(jié)構(gòu)體和各種函數(shù)

2.2棧的初始化?STInit 函數(shù)

2.3棧的銷(xiāo)毀?STDestroy 函數(shù)

2.4棧的插入操作?STPush 函數(shù)?

2.5棧的判斷是否為空操作?STEmpty 函數(shù)?

2.6棧的刪除操作?STPop 函數(shù)

2.7棧的取棧頂元素操作?STTop 函數(shù)

2.8求棧的大小即有效元素的個(gè)數(shù)?STSize 函數(shù)

3->測(cè)試下我們自己寫(xiě)的棧

4->您的專(zhuān)屬鼓勵(lì)師

---

1->棧的概念和結(jié)構(gòu)

1.1棧的概念

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

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

?1.2棧的結(jié)構(gòu)

?

?2->棧的實(shí)現(xiàn)

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小.

使用數(shù)組模擬原理:

?使用鏈表模擬原理:

?

// 下面是定長(zhǎng)的靜態(tài)棧的結(jié)構(gòu)，實(shí)際中一般不實(shí)用，所以我們主要實(shí)現(xiàn)下面的支持動(dòng)態(tài)增長(zhǎng)的棧
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 棧頂
}Stack;

2.1定義關(guān)于棧的結(jié)構(gòu)體和各種函數(shù)

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef struct Stack
{int* _arr;//開(kāi)辟在堆區(qū)上存儲(chǔ)數(shù)據(jù)的數(shù)組int _top;//棧頂?shù)南乱粋€(gè)位置int _capacity;//棧的容量
}ST;//1.棧初始化
void STInit(ST* pst);
//2.棧的銷(xiāo)毀
void STDestroy(ST* pst);
//3.棧的插入操作
void STPush(ST* pst, int x);
//4.棧的刪除操作
void STPop(ST* pst);
//5.取棧頂元素
int STTop(ST* pst);
//6.判斷棧是否為空,空為true,非空為false
bool STEmpty(ST* pst);
//7.求棧的大小即有效元素的個(gè)數(shù)
int STSize(ST* pst);

2.2棧的初始化?STInit 函數(shù)

//1.棧初始化
void STInit(ST* pst)
{assert(pst);pst->_arr = NULL;pst->_capacity = 0;pst->_top = 0;//指向棧頂元素的下一個(gè)位置,類(lèi)似于//之前寫(xiě)的順序表中的_size,指向未使用位置
}

2.3棧的銷(xiāo)毀?STDestroy 函數(shù)

//2.棧的銷(xiāo)毀
void STDestroy(ST* pst)
{assert(pst);free(pst->_arr);//清理位于堆上的數(shù)組pst->_arr = NULL;pst->_capacity = pst->_top = 0;
}

2.4棧的插入操作?STPush 函數(shù)?

//3.棧的插入操作
void STPush(ST* pst, int x)
{assert(pst);//插入數(shù)據(jù)之前判斷一下容量是否足夠,不夠就擴(kuò)容if (pst->_top == pst->_capacity)//容量滿(mǎn)了,擴(kuò)容{//剛開(kāi)始插入給4個(gè)空間,否則就2倍擴(kuò)容int newcapacity = (pst->_capacity == 0 ? 4 : pst->_capacity * 2);int* newarr = (int*)realloc(pst->_arr, newcapacity * sizeof(int));if (newarr == NULL){perror("realloc failed");return;}pst->_arr = newarr;pst->_capacity = newcapacity;}//有容量了,插入數(shù)據(jù)pst->_arr[pst->_top] = x;pst->_top++;
}

2.5棧的判斷是否為空操作?STEmpty 函數(shù)?

//4.判斷棧是否為空,空為true,非空為false
bool STEmpty(ST* pst)
{assert(pst);return pst->_top == 0;
}

2.6棧的刪除操作?STPop 函數(shù)

//5.棧的刪除操作
void STPop(ST* pst)
{//首先你得有元素才能刪除對(duì)吧assert(pst);assert(!STEmpty(pst));pst->_top--;
}

2.7棧的取棧頂元素操作?STTop 函數(shù)

//6.取棧頂元素
int STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->_arr[pst->_top - 1];
}

2.8求棧的大小即有效元素的個(gè)數(shù)?STSize 函數(shù)

//7.求棧的大小即有效元素的個(gè)數(shù)
int STSize(ST* pst)
{assert(pst);return pst->_top;
}

3->測(cè)試下我們自己寫(xiě)的棧

#include "Stack.h"//1.測(cè)試棧插入,刪除,取棧頂元素
void testStack1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d : ",STTop(&st));STPop(&st);}STDestroy(&st);}int main()
{testStack1();return 0;
}

運(yùn)行,看控制臺(tái)輸出:歐耶,我們自己寫(xiě)的?？梢哉＿\(yùn)行

4->您的專(zhuān)屬鼓勵(lì)師

????????有些事情，你永遠(yuǎn)都沒(méi)有辦法做到“頂尖”，因?yàn)橹橇Ω簧?但是所有的事情，你都可以做到“高段”，因?yàn)樗枰氖菚r(shí)間的累積和精力的打磨.不聰明與聰明之間的區(qū)別，是很微妙的.有時(shí)候我們只會(huì)通過(guò)一次兩次的結(jié)果，來(lái)判斷整個(gè)人、整件事，其實(shí)這是不明智的.從小，鄰居和親戚在談?wù)撐业臅r(shí)候，都會(huì)覺(jué)得我很聰明。但是只有我自己知道，我從來(lái)沒(méi)有聰明過(guò)，只是看上去比較聰明而已.

????????修行之路確實(shí)枯燥,但是我們把問(wèn)題搞懂以后就發(fā)現(xiàn)他是那樣的美妙!一遍學(xué)不會(huì)沒(méi)關(guān)系吖,多看幾遍,我也是學(xué)了好多遍呢,小伙伴們肯定學(xué)的又快又好!!!最后希望寫(xiě)的內(nèi)容對(duì)小伙伴們有所幫助,我寫(xiě)的如果有哪里不對(duì)的地方請(qǐng)?jiān)谠u(píng)論區(qū)或者私信指出來(lái)哦!讓我們一起進(jìn)步吖,任何疑問(wèn)包括心情不好都可以找我聊聊,我很樂(lè)意當(dāng)你的傾聽(tīng)者吖.???