本文首發(fā)于 個(gè)人博客
我們都知道函數(shù)都是存放在棧上棍掐，由系統(tǒng)幫我們管理，那么棧到底是一種什么樣的數(shù)據(jù)結(jié)構(gòu)呢龄砰？他是如何管理數(shù)據(jù)的伞广？ 日常開(kāi)發(fā)中我們或許并沒(méi)有直接的用上棧這種數(shù)據(jù)結(jié)構(gòu)拥知，但是它卻能幫我們解決一些很棘手的問(wèn)題，這篇文章主要分享一下個(gè)人對(duì)棧的理解以及如何用 c去實(shí)現(xiàn)一個(gè)棧的結(jié)構(gòu)态罪。本文涉及的代碼可以前往 示例代碼 處查看黎茎。
棧結(jié)構(gòu)
我們知道棧其實(shí)也是一種線性結(jié)構(gòu)，接下來(lái)我們從兩種邏輯來(lái)實(shí)現(xiàn)它炉峰，順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 畏妖。
順序棧
順序存儲(chǔ)通常都要借助于數(shù)組，因?yàn)閿?shù)組中的數(shù)據(jù)在內(nèi)存中都是連續(xù)的疼阔，為了方便我們對(duì)于棧的查詢(xún)以及遍歷戒劫，我們加入一個(gè)指向棧頂?shù)脑?top, 那么其數(shù)據(jù)結(jié)構(gòu)應(yīng)該是這樣：
typedef int Status;
typedef int Data;
typedef struct {
Data data[MAXSIZE];
int top;
}Stack;
其結(jié)構(gòu)很簡(jiǎn)單半夷，用一個(gè)數(shù)組能保存棧中每個(gè)位置的數(shù)據(jù)，然后用一個(gè) top 來(lái)記錄當(dāng)前棧的頂位于何處谱仪，這樣我們就能通過(guò)一系列的方法對(duì)棧進(jìn)行操作玻熙。
// 初始化空棧
Status InitStack (Stack *S) {
S->top = -1;
return SUCCESS;
}
// 清空棧
Status ClearStack (Stack *S) {
S->top = -1;
return SUCCESS;
}
// 判斷是否為空棧
bool IsEmpty(Stack S) {
if (S.top == -1) {
return true;
} else {
return false;
}
}
// 返回棧長(zhǎng)度
int StackLength(Stack s) {
return s.top+1;
}
// 獲取棧頂元素
Status GetStackTop(Stack S,Data *data) {
if (S.top == -1)return ERROR;
*data = S.data[S.top];
return SUCCESS;
}
// 入棧
Status PushData(Stack *S,Data data) {
if (S->top == MAXSIZE-1) return ERROR;
int top = S->top+1;
S->data[top] = data;
S->top++;
return SUCCESS;
}
// 出棧
Status Pop(Stack *S,Data *data) {
if (S->top == -1) return ERROR;
*data = S->data[S->top];
S->top--;
return SUCCESS;
}
// 從棧底到棧頂打印棧
Status PrintStack(Stack S) {
if (S.top == -1) {
printf("空棧 \n");
return ERROR;
}
for (int i = 0; i <= S.top; i ++) {
printf("%d--",S.data[i]);
}
printf("\n");
return SUCCESS;
}
驗(yàn)證
int main(int argc, const char * argv[]) {
// insert code here...
Stack S;
InitStack(&S);
for (int i = 0; i < 10; i ++) {
PushData(&S, i);
}
PrintStack(S);
Data data;
Pop(&S, &data);
PrintStack(S);
printf("出棧的數(shù)據(jù)是： %d \n",data);
GetStackTop(S, &data);
printf("棧頂?shù)臄?shù)據(jù)是： %d \n",data);
return 0;
}
------------------------打印數(shù)據(jù)
棧中數(shù)據(jù)是：0--1--2--3--4--5--6--7--8--9--
棧中數(shù)據(jù)是：0--1--2--3--4--5--6--7--8--
出棧的數(shù)據(jù)是： 9
棧頂?shù)臄?shù)據(jù)是： 8
有幾個(gè)小細(xì)節(jié)點(diǎn)需要我們注意：
- 線性棧的置空不用清空每個(gè)位置的數(shù)據(jù)，只需要修改 top 即可
- 返回棧的長(zhǎng)度不用判斷 top = -1 的情況疯攒，因?yàn)?-1+1 = 0 其最終結(jié)果是一樣的
其實(shí)通過(guò)上述實(shí)現(xiàn)我們可以發(fā)現(xiàn)嗦随，棧的處理核心邏輯在于 top 的處理。
鏈?zhǔn)綏?/h2>
分析了順序棧之后我們?cè)賮?lái)看看鏈?zhǔn)綏＞闯撸櫭剂x枚尼，鏈?zhǔn)綏Ｓ玫慕Y(jié)構(gòu)就是鏈?zhǔn)酱鎯?chǔ)，內(nèi)部必不可少的用到指針砂吞，其在內(nèi)存中不是連續(xù)的署恍，靠的是指針的指向，所以其數(shù)據(jù)結(jié)構(gòu)可以是這樣：
// 棧中每個(gè)位置的數(shù)據(jù)
typedef struct Node {
Data data;
Node *next;
} Node;
// 棧的結(jié)構(gòu)
typedef struct {
Node *top; // 棧頂節(jié)點(diǎn)
int count; // 棧的數(shù)據(jù)量
} Stack;
這里的鏈?zhǔn)綏５慕Y(jié)構(gòu)就由一個(gè)指向棧頂?shù)闹羔?和 其數(shù)據(jù)長(zhǎng)度構(gòu)成蜻直，棧的指針指向棧頂盯质，由上往下通過(guò) next 指針相連，看起來(lái)應(yīng)該是這樣：
根據(jù)前面鏈表的相關(guān)內(nèi)容概而，我們很容易寫(xiě)出它的相關(guān)方法：
// 創(chuàng)建一個(gè)空棧
Status InitStack(Stack *S) {
S->top = (Node *)malloc(sizeof(Node));
if (!S->top) return ERROR;
S->top = NULL;
S->count = 0;
return SUCCESS;
}
// 入棧
Status PushData(Stack *S, Data data) {
if (!S) return ERROR;
Node *newTop = (Node *)malloc(sizeof(Node));
newTop->data = data;
newTop->next = S->top;
S->top = newTop;
S->count++;
return SUCCESS;
}
// 出棧
Status Pop(Stack *S,Data *data) {
if (!S) return ERROR;
Node *temp = S->top;
S->top = temp->next;
S->count--;
*data = temp->data;
free(temp);
return SUCCESS;
}
// 獲取棧頂元素
Status GetTop(Stack S,Data *data) {
if (S.count == 0) return ERROR;
*data = S.top->data;
return SUCCESS;
}
// 清空棧
Status ClearStack(Stack *S) {
Node *temp = S->top;
while (temp) {
Node *target = temp;
temp = temp->next;
free(target);
}
S->top = NULL;
S->count = 0;
return SUCCESS;
}
// 從棧頂?shù)綏５状蛴?Status PrintStack(Stack S) {
if (S.count <= 0) return ERROR;
printf("棧的數(shù)據(jù)從頂?shù)降资牵?);
Node *temp = S.top;
while (temp) {
printf("%d - ",temp->data);
temp = temp->next;
}
printf("\n");
return SUCCESS;
}
驗(yàn)證
int main(int argc, const char * argv[]) {
// insert code here...
Stack S;
InitStack(&S);
if (InitStack(&S) == SUCCESS) {
for (int i = 1; i < 10; i++) {
PushData(&S, i);
}
}
PrintStack(S);
Data data;
Pop(&S, &data);
PrintStack(S);
printf("出棧的元素是: %d \n",data);
GetTop(S, &data);
printf("棧頂?shù)脑厥? %d \n",data);
return 0;
}
--------------------- 打印數(shù)據(jù)
棧的數(shù)據(jù)從頂?shù)降资牵? - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 -
棧的數(shù)據(jù)從頂?shù)降资牵? - 7 - 6 - 5 - 4 - 3 - 2 - 1 -
出棧的元素是: 9
棧頂?shù)脑厥? 8
總結(jié)
這篇文章主要講述了棧的結(jié)構(gòu)以及棧的 順序存儲(chǔ)實(shí)現(xiàn) 和 鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn) 呼巷，希望能夠講述明白。
