Implement stack using linked list
In this post, you will learn how to implement a stack using linked list in different programming language.
Stack is a linear data structure which is simple and easy to implement. In stack, elements are inserted and removed from only one end. So, it is less flexible than list. The first element stored in the stack is last removed out and the element last stored is first removed out. That's why stack is called LIFO (Last-In-First-Out).
Real life examples of stack are plates on a tray, coin stacks, shipments in a cargo and the examples of stack in the computer world are compiler, browser back button.
Stack Operations
The PUSH and POP operations are performed only one end of the stack. There is a pointer TOP in the stack to keep track of top element. Whenever a new element is inserted, the pointer is increased by one and then the element is placed on the stack. And when an existing element is deleted the pointer is decreased by one.
The linked list is a non primitive data structure that is free from fixed memory size restrictions. It is static free and the user can add any number of elements when required. We can use this to create other data structures like stacks, queues, etc. It allows the insertion and deletion of nodes at any point in the list.
Stack Implementation using linked list in 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("\n**Stack operations using linked list***\n");
while(choice != 4)
{
printf("\nChoose one from the given options...");
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("Error: Not able to push the element");
}
else
{
printf("Enter a value to insert: ");
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("Error: 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;
}
}
}
Output of the above code:
**Stack operations using linked list***
Choose one from the given options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice:
1
Enter a value to insert: 43
Item pushed
Choose one from the given options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice:
1
Enter a value to insert: 82
Item pushed
Choose one from the given options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice:
2
Item popped
Choose one from the given options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice:
3
Printing Stack elements
43
Choose one from the given options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice:
Stack Implementation using linked list in C++
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"Element removed from the stack: "<< top->data <<endl;
top = top->next;
}
}
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"Stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<" Enter your choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}
Output of the above code:
1) Push in stack
2) Pop from stack
3) Display stack
4) Exit
Enter your choice:
1
Enter value to be pushed:
44
Enter your choice:
1
Enter value to be pushed:
53
Enter your choice:
2
Element removed from the stack: 53
Enter your choice:
3
Stack elements are: 44
Enter your choice:
Stack Implementation using linked list in Java
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data;
Node link;
}
// create global variable
Node top;
// Create constructor
StackUsingLinkedlist()
{
this.top = null;
}
// function to add an element in the stack
public void push(int x)
{
// create new node temp and allocate memory
Node temp = new Node();
// check for stack overflow
if (temp == null) {
System.out.print("\nStack Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Function to return top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
System.out.println("\nItem popped");
// update the top pointer to point to the next node
top = (top).link;
}
public void display()
{
// Check for stack underflow
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
System.out.printf("\nPrinting Stack elements:\n");
while (temp != null) {
// print node data
System.out.printf("%d ", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class MainStackClass {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(45);
obj.push(23);
obj.push(92);
obj.push(17);
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
// Delete top element of Stack
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}
Output of the above code:
Printing Stack elements:
17 92 23 45
Top element is 17
Item popped
Printing Stack elements:
92 23 45
Top element is 92
Stack Implementation using linked list in Python
class Node:
# Class to create nodes of linked list
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# set the head to NULL
def __init__(self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head
def pop(self):
if self.isempty():
return None
else:
poppednode = self.head
self.head = self.head.next
poppednode.next = None
print("\nItem popped");
return poppednode.data
# Returns the head node data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
# Prints out the stack
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
print("\nPrinting stack elements:")
while(iternode != None):
print(iternode.data," ",end = " ")
iternode = iternode.next
return
# Driver code
obj = Stack()
obj.push(43)
obj.push(12)
obj.push(23)
obj.push(64)
# Display stack elements
obj.display()
# Print top element of stack
print("\nTop element: ",obj.peek())
# Delete top elements of stack
obj.pop()
obj.pop()
# Display stack elements
obj.display()
# Print top element of stack
print("\nTop element: ", obj.peek())
Output of the above code:
Printing stack elements:
64 23 12 43
Top element: 64
Item popped
Item popped
Printing stack elements:
12 43
Top element: 12
Related Articles
Implementation of queue using array in CQueue implementation in Python
Queue Implementation in C
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Prime factors of a number in c
Armstrong number program in c
Write a program to check leap year in c
C program to find area of rectangle
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to convert Decimal to Octal
C program to convert decimal to binary
C program to check whether a number is even or odd