堆疊也可以使用鏈表來實現，而不是只能使用數組來實現。鏈表動態可以分配記憶體。 然而，兩種情況下的時間複雜度對於所有操作是相同的，即推入，彈出和窺視。
在堆疊的鏈表實現中，節點在記憶體中非連續地維護。 每個節點都包含一個指向堆疊中直接後繼節點的指針。 如果記憶體堆中剩餘的空間不足以創建節點，則稱堆疊溢出。
堆疊中最頂層的節點的地址字段中始終包含null。 下麵來討論一下每個操作在堆疊的鏈表實現中執行的方式。
1. 將節點添加到堆疊(推送操作)
將節點添加到堆疊稱為推送操作。 在鏈表實現中將元素推送到堆疊不同於數組實現的元素。 為了將元素推入堆疊，涉及以下步驟。
- 首先創建一個節點並為其分配記憶體。
- 如果鏈表為空，則將資料項目作為鏈表的起始節點推入。 這包括將值分配給節點的數據部分，並將
null分配給節點的地址部分。 - 如果鏈表中已經有一些節點，那麼需要在鏈表的開頭添加新元素(不違反棧的屬性)。 為此，將起始元素的地址分配給新節點的地址字段，並創建新節點，即鏈表的起始節點。
時間複雜度： o(1)
C語言的代碼實現
void push ()
{
int val;
struct node *ptr =(struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed");
}
}
2. 從堆疊中刪除節點(彈出操作)
從堆疊頂部刪除節點稱為彈出操作。 從堆疊的鏈表實現中刪除節點與陣列實現中的節點不同。 要從堆疊中彈出元素，需要按照以下步驟操作：
- 檢查下溢情況 ：當嘗試從已經空的堆疊彈出時就會發生下溢情況。 如果鏈表的頭指針指向
null，則堆疊將為空。 - 相應地調整頭指針：在堆疊中，元素僅從一端彈出，因此，必須刪除存儲在頭指針中的值，並且必須釋放節點。 頭節點的下一個節點現在成為頭節點。
時間複雜度：o(n)
C語言代碼實現
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
3. 顯示節點(遍曆)
顯示堆疊的所有節點需要遍曆以堆疊形式組織的鏈表的所有節點。 為此，需要遵循以下步驟。
- 將頭指針複製到臨時指針中。
- 將臨時指針移動到鏈表的所有節點，並列印附加到每個節點的值。
時間複雜度：o(n)
C語言的代碼實現
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
C語言完整的代碼實現如下
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main()
{
int choice = 0;
printf("*********Stack operations using linked list*********\n");
printf("----------------------------------------------\n");
while (choice != 4)
{
printf("Chose one from the below options...\n");
printf("1.Push\n2.Pop\n3.Show\n4.Exit");
printf("Enter your choice \n");
scanf("%d", &choice);
switch (choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d", &val);
if (head == NULL)
{
ptr->val = val;
ptr->next = NULL;
head = ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head = ptr;
}
printf("Item pushed");
}
}
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr = head;
if (ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while (ptr != NULL)
{
printf("%d\n", ptr->val);
ptr = ptr->next;
}
}
}