Stack Using Linked List
Stack Using Linked List
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. It has two main operations: push (to add an element) and pop (to remove the top element).
Stack Implementation using Linked List:
A linked list is a data structure where each element (node) contains a data field and a reference (link) to the next node in the sequence. In a linked list implementation of a stack, the top of the stack corresponds to the first node in the linked list.
Algorithm
1.Define the Node Structure:
Create a structure to represent a node in the linked list. This structure should have two members: one for storing the data and another for pointing to the next node.c
struct Node {
int data;
struct Node* next;
};
Create a pointer to the top of the stack (top) and initialize it to NULL.
struct Node* top = NULL;
struct Node* top = NULL;
Allocate memory for a new node.
Set the data of the new node.
Set the data of the new node.
Update the 'next' pointer of the new node to point to the current top.
Update the 'top' pointer to the new node.void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top;
top = newNode;
}
4.Pop Operation:
Check if the stack is not empty (i.e., top is not NULL).
If not empty, store the data of the top node, update 'top' to point to the next node, and free the memory of the removed node.
int pop() {
if (top == NULL) {
printf("Stack is empty.\n");
return -1; // or any value to indicate an error
}
int poppedValue = top->data;
struct Node* temp = top;
top = top->next;
free(temp);
return poppedValue;
}
5.Display Stack :
Check if the Stack is Empty:
If the stack is empty (i.e., top is NULL), print a message indicating that the stack is empty.
Traverse and Print:
If the stack is not empty, initialize a temporary pointer to the top of the stack.
Traverse the stack using a loop until the temporary pointer becomes NULL.
Print the data of each node as you traverse.
void displayStack() {
if (top == NULL) {
printf("Stack is empty.\n");
} else {
struct Node* temp = top;
printf("Stack content:\n");
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
}
Complexity Analysis
Let's analyze the time complexity of the basic stack operations (push, pop, and display) for the linked list implementation:
Push Operation:Time Complexity: O(1)
The push operation involves creating a new node, updating pointers, and performing some basic assignments. These operations take a constant amount of time, making the time complexity of push O(1).
Pop Operation:Time Complexity: O(1)
Similar to push, the pop operation involves updating pointers, freeing memory, and performing basic assignments. These operations also take a constant amount of time, resulting in a time complexity of O(1).
Display Operation:Time Complexity: O(n)
The display operation involves traversing the entire linked list, where "n" is the number of elements in the stack. As each element needs to be visited once, the time complexity is linear with respect to the number of elements in the stack.
In summary:
Push and pop operations have constant time complexity O(1).
Display operation has a linear time complexity O(n), where "n" is the number of elements in the stack.
The space complexity for the linked list implementation is also important to consider:
Space Complexity: O(n)
The space complexity is linear with respect to the number of elements in the stack since each element is represented by a node, and additional space is used for pointers.
It's important to note that these complexities are based on the assumption of a singly linked list. If you were using a doubly linked list or another variant, the complexities might be different.
Stack using Linked List -C Implementation
/*******************************************************************************/
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct Node *top=NULL;
void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top;
top = newNode;
}
int pop() {
if (top == NULL) {
printf("Stack is empty.\n");
return -1; // or any value to indicate an error
}
int poppedValue = top->data;
struct Node* temp = top;
top = top->next;
free(temp);
return poppedValue;
}
void displayStack() {
if (top == NULL) {
printf("Stack is empty.\n");
} else {
struct Node* temp = top;
printf("Stack content:\n");
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
}
void main()
{
int ch;
do
{
printf("\nMenu\n----\n1. Push\n2. Pop\n3.display\n4. Exit");
printf("\nEnter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the data to push:");
int data;
scanf("%d",&data);
push(data);
displayStack();
break;
case 2:
int rv;
rv=pop();
if(rv!=-1) printf("Popped Value is:%d\n",rv);
displayStack();
break;
case 3:
displayStack();
break;
case 4:
exit(0);
default:
printf("There is no such operation:");
}
}
while(1);
}
Comments
Post a Comment