Implement a stack using singly linked list
To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to perform Pop , Push , Peek ,Display operations in the following article .
A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.
The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.
Stack Operations:
-
push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
-
pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
-
peek(): Return the top element.
-
display(): Print all elements in Stack.
Below is the implementation of the above approach:
C++
|
// C++ program to Implement a stack
//using singly linked list
#include
using namespace std;
// Declare linked list node
struct Node
{
int data;
Node* link;
};
Node* top;
// Utility function to add an element
// data in the stack insert at the beginning
void push(int data)
{
// Create new node temp and allocate memory in heap
Node* temp = new Node();
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp)
{
cout << "\nStack Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
int isEmpty()
{
//If top is NULL it means that
//there are no elements are in stack
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// If stack is not empty , return the top element
if (!isEmpty())
return top->data;
else
exit(1);
}
// Utility function to pop top
// element from the stack
void pop()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
// Assign top to temp
temp = top;
// Assign second node to top
top = top->link;
//This will automatically destroy
//the link between first node and second node
// Release memory of top node
//i.e delete the node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
temp = top;
while (temp != NULL)
{
// Print node data
cout << temp->data << "-> ";
// Assign temp link to temp
temp = temp->link;
}
}
}
// Driver Code
int main()
{
// Push the elements of stack
push(11);
push(22);
push(33);
push(44);
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
// Delete top elements of stack
pop();
pop();
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
return 0;
}
|
Java
|
// Java program to Implement a stack
// using singly linked list
// import package
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data; // integer data
Node link; // reference variable Node type
}
// create global top reference variable global
Node top;
// Constructor
StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add an element x in the stack
public void push(int x) // insert at the beginning
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap 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;
}
// Utility function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Utility 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;
}
}
// Utility 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;
}
// 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;
while (temp != null) {
// print node data
System.out.printf("%d->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class GFG {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// 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();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}
|
Python3
|
'''Python supports automatic garbage collection so deallocation of memory
is done implicitly. However to force it to deallocate each node after use,
add the following code:
import gc #added at the start of program
gc.collect() #to be added wherever memory is to be deallocated
'''
class Node:
# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# head is default 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
# adds to the start of 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 (start of the stack)
def pop(self):
if self.isempty():
return None
else:
# Removes the head node and makes
#the preceding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
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:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
# Driver code
MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(33)
MyStack.push(44)
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ",MyStack.peek())
# Delete top elements of stack
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ", MyStack.peek())
# This code is contributed by Mathew George
|
C#
|
// C# program to Implement a stack
// using singly linked list
// import package
using System;
// Create Stack Using Linked list
public class StackUsingLinkedlist
{
// A linked list node
private class Node
{
// integer data
public int data;
// reference variable Node type
public Node link;
}
// create global top reference variable
Node top;
// Constructor
public StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add
// an element x in the stack
// insert at the beginning
public void push(int x)
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full.
// Then inserting an element
// would lead to stack overflow
if (temp == null)
{
Console.Write("\nHeap 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;
}
// Utility function to check if
// the stack is empty or not
public bool isEmpty()
{
return top == null;
}
// Utility function to return
// top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty())
{
return top.data;
}
else
{
Console.WriteLine("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
// update the top pointer to
// point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
else
{
Node temp = top;
while (temp != null)
{
// print node data
Console.Write("{0}->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// Driver code
public class GFG
{
public static void Main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
}
}
// This code is contributed by 29AjayKumar
|
Javascript
Output:
44->33->22->11->
Top element is 44
22->11->
Top element is 22
Time Complexity:
The time complexity for all push(), pop(), and peek() operations is O(1) as we are not performing any kind of traversal over the list. We perform all the operations through the current pointer only.
Article Tags :
Linked List
Stack
Technical Scripter
Technical Scripter 2018
Practice Tags :
Linked List
Stack
Queue – Linked List Implementation
In the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.
In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.
enQueue() This operation adds a new node after rear and moves rear to the next node.
deQueue() This operation removes the front node and moves front to the next node.
Linked list implementation of stack
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.
Queue using linked list
Queue using an array - drawback
If we implement the queue using an array, we need to specify the array size at the beginning(at compile time).
We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements.
Solution
We can implement the queue data structure using the linked list.
In the linked list, we can change its size at runtime.
1. What is Stack in C?
A stack in C is nothing but a linear data structure that follows the LIFO rule (Last In First Out). In a stack, both insertion and deletion take place from just one end, that is, from the top.
In order to better understand it, consider the following scenario: Imagine you have 5 plates that you have to keep on top of each other of distinct colors: Red, Green, Blue, White, and Orange.
You start by placing the red plate on the table. This is the first element of the stack. Then, you place the green plate on top of the red plate. This is the second element of the stack. Similarly, you place the blue plate followed by white and then finally orange.Note that the first plate you inserted into the stack was the red one. Now, you want to remove the red plate. But, before that, you need to remove the rest of the plates that are on top of the red one.
From this discussion, it is pretty obvious that the first plate (first data element) to be inserted is removed at the last. And, the last plate to be inserted is removed at first, that is, it follows the “Last In First Out” rule. Also, we infer that placing and removing the plate is done from the top, that is, insertion and deletion are done from the top
We can implement a stack in C in 2 ways:
- Statically: Array implementation of stacks allows the static memory allocation of its data elements. It is important to note that in this method, the stack acquires all the features of an array.
- Dynamically: Linked list implementation of stacks follow the dynamic memory allocation of its data elements. It is important to note that in this method, the stack inherits all the characteristics of a linked list in C.
Stay updated with latest technology trends
Join DataFlair on Telegram!!
1.1 Array Implementation of Stack in C
As we already discussed, arrays support the static memory allocation of the data elements of the stack. Therefore, it is important to determine the size of the stack prior to the program run.
The C stack functions basically include:
1.1.1 Insertion
In a stack, the operation of inserting an element into the stack is referred to as pushing an element in the stack. The elements are inserted into the stack from the top and hence would compel the elements to shift.
Here is a diagrammatic representation of how elements are pushed into a stack:
This is how we can insert elements into a C stack:
#define LIMIT 100
void push()
{
int stack[LIMIT], top, element;
if(top == LIMIT- 1)
{
printf("Stack Overflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}
Enhance your Fundamental Skills with Different types of Operators in C
1.1.2 Deletion
In a stack, the operation of deleting an element into the stack is referred to as popping an element in the stack. The deletion of a data element from the stack is done from the top.
Here is a diagrammatic representation of how elements are pushed into a stack:
This is how we can delete elements from a stack:
#define LIMIT 100
void pop()
{
int stack[LIMIT], top, element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}
1.1.3 Display
The stack data elements are displayed in the stack according to the LIFO rule.
This is how you can display the stack in C:
#define LIMIT 100
void display()
{
int stack[LIMIT], top, i;
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}
Apart from these 3 main functions, it is necessary to check the overflow and underflow conditions to avoid unfavorable situations.
1.1.4 Stack Overflow
Here we are talking about the static memory allocation of data elements of a stack. Therefore, if the stack is filled completely, that is, no more elements can be inserted in the stack, then the condition would be called STACK-FULL condition. It is also referred to as stack overflow.
1.1.5 Stack Underflow
In case we wish to display the data elements of the stack or perform the deletion operation, but no elements have been inserted into the stack yet, this condition is called STACK-EMPTY. It is also referred to as stack underflow.
Before discussing the example, let’s revise the concept of Variables in C
Here is a program in C that illustrates the array implementation of stacks:
#include
#include
#define LIMIT 100 // Specifying the maximum limit of the stack
/* Global declaration of variables */
int stack[LIMIT]; // Array implementation of stack
int top; // To insert and delete the data elements in the stack
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations
void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule
int main()
{
printf("Welcome to DataFlair tutorials!\n\n");
printf ("ARRAY IMPLEMENTATION USING STACKS\n\n");
top = -1; // Initializing top to -1 indicates that it is empty
do
{
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}
void push()
{
int element;
if(top == LIMIT- 1)
{
printf("Stack underflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}
void pop()
{
int element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}
void display()
{
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}Output-
1.2 Linked List Implementation of Stack in C
As we already discussed, linked lists support the dynamic memory allocation of the data elements of the stack. Therefore, the size of the stack is allocated during the program run and needn’t be specified beforehand.
The 3 basic operations of Insertion, Deletion, and Display follow a similar trend as we saw in the array implementation of stacks.
Functions in C – An Important Concept for beginners
The stack functions basically include:
1.2.1 Insertion
This is how we can insert elements into the stack in C:
void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}
1.2.2 Deletion
This is how we can delete elements from a stack in C:
void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}
1.2.3 Display
This is how we display the elements of a stack:
void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}
Here is a code in C that illustrates the linked list implementation of arrays:
#include
#include
void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the elememt from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule
struct node
{
int data;
struct node *next;
};
struct node *temp;
int main()
{
printf("Welcome to DataFlair tutorials!\n\n");
int choice;
printf ("LINKED LIST IMPLEMENTATION USING STACKS\n\n");
do
{
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}
void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}
void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}
void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}Output-
1.3 Application of Stack in C
The principle LIFO followed by stacks gives birth to the various applications of stacks. Some of the most popular applications of stacks are:
- Number reversal: A stack helps you reverse a number or a word entered as a sequence of digits or characters respectively.
- Undo operation: Implementation of a stack helps you perform the “undo” operation in text editors or word processors. Here, all the changes done in the text editor are stored in a stack.
- Infix to postfix conversion: Using stacks, you can perform the conversion of an infix expression to a postfix expression.
- Backtracking:Stacks are finding applications in puzzle or maze problem-solving.
- Depth-first search (DFS): Stacks allow you to perform a searching algorithm called the depth-first search.
