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

推送操作

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

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

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

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

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

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

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

彈出操作

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

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

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

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

彈出操作

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

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

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

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

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

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

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

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

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

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

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

插入和刪除

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

沒有內(nèi)存浪費

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

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

內(nèi)存使用情況

需要更多的內(nèi)存來存儲鏈表中的元素，因為鏈表中的每個節(jié)點都包含一個指針，并且它本身需要額外的內(nèi)存。

遍歷

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

反向移動

使用鏈表在堆棧實現(xiàn)中反向遍歷非常棘手，因為反向指針需要額外的內(nèi)存，因此會浪費內(nèi)存。

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