栈的链表实现

除了使用数组, 我们还可以使用链表来实现堆栈。链表动态分配内存。但是, 对于所有操作（即推, 弹出和查看）, 两种情况下的时间复杂度都是相同的。

在堆栈的链表实现中, 节点不连续地保存在内存中。每个节点在堆栈中都包含一个指向其直接后继节点的指针。如果内存堆中剩余的空间不足以创建节点, 则称堆栈溢出。

堆栈中最顶层的节点在其地址字段中始终包含null。让我们讨论在堆栈的链表实现中执行每个操作的方式。

将节点添加到堆栈（推送操作）

将节点添加到堆栈称为推入操作。在链表实现中将元素推送到堆栈与数组实现不同。为了将元素推入堆栈, 需要执行以下步骤。

1. 首先创建一个节点并为其分配内存。
2. 如果列表为空, 则将该项目作为列表的起始节点进行推送。这包括将值分配给节点的数据部分, 并将null分配给节点的地址部分。
3. 如果列表中已经有一些节点, 那么我们必须在列表的开头添加新元素（以免违反堆栈的属性）。为此, 请将起始元素的地址分配给新节点的地址字段, 并使新节点成为列表的起始节点。

Time Complexity : o(1)





C implementation :

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”); } }

Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :

1. 检查下溢条件：当我们尝试从已经空的堆栈中弹出时, 发生下溢条件。如果列表的头指针指向空, 则堆栈将为空。
2. 相应地调整头指针：在堆栈中, 仅从一端弹出元素, 因此, 必须删除头指针中存储的值, 并且必须释放节点。头节点的下一个节点现在成为头节点。

Time Complexity : o(n)

C implementation

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”); } }

Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps.

1. 将头指针复制到一个临时指针。
2. 在列表的所有节点之间移动临时指针, 并打印附加到每个节点的value字段。

Time Complexity : o(n)

C Implementation

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; } } }

Menu Driven program in C implementing all the stack operations using linked list :

#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(“\n*********Stack operations using linked list*********\n”); printf(“\n———————————————-\n”); while(choice != 4) { printf(“\n\nChose one from the below options…\n”); printf(“\n1.Push\n2.Pop\n3.Show\n4.Exit”); printf(“\n 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; } } }


Next Topic DS Queue



← prev next →