使用鏈表實(shí)現(xiàn)堆棧的過程

推送操作

在 Stack 中添加新節(jié)點(diǎn)稱為推送操作。

在鏈表中壓入一個(gè)節(jié)點(diǎn)與在數(shù)組中插入一個(gè)元素是完全不同的。使用鏈表實(shí)現(xiàn)堆棧推送操作涉及幾個(gè)步驟：

首先創(chuàng)建一個(gè)節(jié)點(diǎn)并為其分配內(nèi)存。

如果列表為空，則該節(jié)點(diǎn)作為鏈表的第一個(gè)節(jié)點(diǎn)被推送。這個(gè)操作給節(jié)點(diǎn)的數(shù)據(jù)部分賦值，給節(jié)點(diǎn)的地址部分賦NULL。

如果某些節(jié)點(diǎn)已經(jīng)在鏈表中，那么我們必須在鏈表的開頭添加一個(gè)新節(jié)點(diǎn)，以免違反 Stack 的屬性。為此，將元素分配給新節(jié)點(diǎn)的地址字段并創(chuàng)建一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)將成為列表的起始節(jié)點(diǎn)。

如果堆棧已滿，當(dāng)我們嘗試推送操作時(shí)會(huì)發(fā)生溢出情況。

空推（）
{
 整數(shù)值；
 結(jié)構(gòu)節(jié)點(diǎn) *ptr1 = (結(jié)構(gòu)節(jié)點(diǎn)*)malloc(sizeof(結(jié)構(gòu)節(jié)點(diǎn)));
 如果（ptr1 == NULL）
 {
  print("無法推送節(jié)點(diǎn)");
 }
 別的
 {
 printf("輸入值");
 scanf(“%d”, &值);
 如果（開始== NULL）
{
 ptr1 -> 值 = 值；
 ptr1 -> 下一個(gè) = NULL；
 開始= ptr1；
 }
別的
{
 ptr1 -> 值 = 值；
 ptr1 -> next = 開始；
 開始= ptr1；
}
 print("數(shù)據(jù)元素被壓入");
}
}

彈出操作

從堆棧中刪除節(jié)點(diǎn)稱為彈出操作。

鏈表中的彈出節(jié)點(diǎn)不同于數(shù)組中的彈出元素。執(zhí)行彈出操作涉及以下步驟：

在 Stack 中，節(jié)點(diǎn)從鏈表的末尾移除。因此，必須刪除存儲(chǔ)在頭指針中的值，并且該節(jié)點(diǎn)必須得到釋放。下面的鏈接節(jié)點(diǎn)現(xiàn)在將成為頭節(jié)點(diǎn)。

當(dāng)我們嘗試在 Stack 已經(jīng)為空時(shí)彈出操作時(shí)，會(huì)發(fā)生下溢情況。如果列表的頭指針指向 NULL，則 Stack 將毫無意義。

彈出操作

從堆棧中刪除節(jié)點(diǎn)稱為彈出操作。

鏈表中的彈出節(jié)點(diǎn)不同于數(shù)組中的彈出元素。執(zhí)行彈出操作涉及以下步驟：

在 Stack 中，節(jié)點(diǎn)從鏈表的末尾移除。因此，必須刪除存儲(chǔ)在頭指針中的值，并且該節(jié)點(diǎn)必須得到釋放。下面的鏈接節(jié)點(diǎn)現(xiàn)在將成為頭節(jié)點(diǎn)。

當(dāng)我們嘗試在 Stack 已經(jīng)為空時(shí)彈出操作時(shí)，會(huì)發(fā)生下溢情況。如果列表的頭指針指向 NULL，則 Stack 將毫無意義。

空彈出（）
{
 整數(shù)數(shù)據(jù)；
 結(jié)構(gòu)節(jié)點(diǎn) *ptr1;
 如果（開始== NULL）
{
 printf(“下溢條件”);
}
別的
{
 數(shù)據(jù) = 開始 -> 值；
 ptr1 = 開始；
 開始 = 開始 -> 下一步；
 免費(fèi)（ptr1）；
 printf("dta 元素彈出");
}
}

空白打印
{
 詮釋 x;
 結(jié)構(gòu)節(jié)點(diǎn) *ptr1;
 ptr1 ==開始；
 如果（ptr1 == NULL）
{
 printf("空棧");
}
 別的
{
 printf(“顯示堆棧元素”);
 同時(shí)（ptr1！= NULL）
{
 printf(“%d”, ptr1 -> 值);
 ptr1 = ptr1 -> 下一個(gè)；
}
}
}

使用鏈表實(shí)現(xiàn)堆棧的優(yōu)缺點(diǎn)

使用鏈表的堆棧實(shí)現(xiàn)有一些優(yōu)點(diǎn)和缺點(diǎn)：

使用鏈表實(shí)現(xiàn)堆棧的優(yōu)點(diǎn)

動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，因此它可以在運(yùn)行時(shí)通過分配和釋放內(nèi)存來增長和收縮。

插入和刪除

與數(shù)組不同，我們不必在插入和刪除內(nèi)容后移動(dòng)元素。通過更新節(jié)點(diǎn)的下一個(gè)指針中存在的地址，鏈表中的插入和刪除相對容易。

沒有內(nèi)存浪費(fèi)

在鏈表中，可以在運(yùn)行時(shí)增加和減少大小，從而不會(huì)浪費(fèi)內(nèi)存。

使用鏈表的堆棧實(shí)現(xiàn)的缺點(diǎn)

內(nèi)存使用情況

需要更多的內(nèi)存來存儲(chǔ)鏈表中的元素，因?yàn)殒湵碇械拿總€(gè)節(jié)點(diǎn)都包含一個(gè)指針，并且它本身需要額外的內(nèi)存。

遍歷

鏈表中的節(jié)點(diǎn)遍歷非常棘手。比如我們要訪問位置n的節(jié)點(diǎn)，那么就得遍歷它之前的所有節(jié)點(diǎn)。所以訪問一個(gè)節(jié)點(diǎn)所需的時(shí)間很大。

反向移動(dòng)

使用鏈表在堆棧實(shí)現(xiàn)中反向遍歷非常棘手，因?yàn)榉聪蛑羔樞枰~外的內(nèi)存，因此會(huì)浪費(fèi)內(nèi)存。

至此，我們使用鏈表文章完成了堆棧實(shí)現(xiàn)。