Last Updated on March 2, 2023 by Prepbytes
In this article, we will learn about what is stack and about various operations performed on Stack in Data Structure, stack implementation using linked list with the dry run of code. We will also enlist various advantages and disadvantages of implementation of Stack using Linked List. In the last, we will discuss some of the applications of Stack in Data Structure.
Stack in Data Structure: Introduction
A stack is a linear data structure in computer science that operates on the Last-In-First-Out (LIFO) principle. A stack stores elements in a sequential manner where elements are inserted (pushed) onto the top of the stack and removed (popped) from the top. The new element to be added is at the top of the stack. The operations performed on a stack include push, pop, and peek. Stacks are widely used in computer algorithms and programs for data manipulation, function calls, and expression evaluations.
Operations performed on Stack in Data Structure
The main operations performed on a stack data structure are:
- push(): This method adds an element to the top of the stack
- pop(): This method removes an element from the top of the stack
- peek(): This method returns the element at the top of the stack without removing it
- isEmpty(): This method returns true if the stack is empty, otherwise false
- size(): This method Returns the number of elements in the stack
Stacks are LIFO (Last In First Out) data structures, meaning that the last element added to the stack will be the first one to be removed. These operations make it a useful data structure for various algorithms, such as maintaining function call history, evaluating mathematical expressions, and implementing undo-redo functionality in applications.
Stack Implementation
A stack in data structure can be implemented using an array or a linked list.
- Stack Implementation using Array: In this approach, an array is used to store the elements of the stack. The top of the stack is kept track of using a variable that points to the index of the topmost element. The basic operations performed on a stack such as push, pop, and peek are implemented by adjusting the value of the top variable.
- Stack Implementation using Linked list: In this approach, each element of the stack is represented as a node in a linked list. The head of the Singly Linked List represents the top of the stack. The basic operations are performed by updating the links between the nodes in the linked list. This implementation is more flexible as it can grow and shrink dynamically as elements are added and removed from the stack.
Stack Implementation using Linked List
We can implement the stack using Linked List. Let us understand this in detail.
Input: We give 4 3 2 1.
Output: If the input is 4 3 2 1, then our singly linked list, which will have all functionalities of a stack, will be
where the head of the linked list is pointing to the 1.
Understanding of the Stack Implementation using Linked List
Let’s see how a stack works.
- It follows the LIFO(last in first out) principle, i.e., the element inserted last in the stack will be the first one accessible to us if we access elements from the stack.
- Suppose we inserted elements in the stack in order 4,3,2,1, and now if we want to access elements from the stack, the order in which the elements will be accessible to us will be 1,2,3,4.
Now, let’s recall what a Singly Linked List is.
- A Singly Linked List is a linear data structure containing nodes, and each node have a data part and a next pointer that points to the next node in the linked list.
- If we can amend the inserting new node operation in a singly linked list in such a way that the current inserted element is always at the head of the linked list and is the first element accessible to us if we want to access an element from the linked list, then we can see that our linked list is mimicking the behavior of stack.
- Similarly, we will try to think of other stack operations and how we can implement these operations using a singly linked list.
Let us have a glance at the algorithm.
Approach and Algorithm of Stack using Linked List
There are mainly 5 functions of a stack. We will learn each function’s approach and algorithm one by one.
-
push()
- In the push function, we push the element into the stack and make it the top.
- So, to do the same with a singly linked list, we will check if the list is Null or not.
- If it is Null, then make the new node the head.
- If the list is not empty, then make the next of the new node point to the head of the list. In the end, make the new node the head of the list. In this way, we are first adding the element at the head, and the making it our head.
-
pop()
- In the pop function, we pop the topmost element of the stack.
- So, to do the same with a singly linked list, first, we will check if the list is Null or not.
- If it is Null, then return NULL.
- If there is only one node in the list, then remove the head, and return NULL.
- If both the above base cases fail:
- We will create a new node temp and make it point to the head.
- Now, we will do head = head → next to make the 2nd node our new head.
- After this, we will do temp → next = NULL, and free (temp).
- In this way, we are making deleting the 1st node of the list and making the 2nd node our new head.
- Remember – We are using 1 based indexing in the above approach.
-
peek()
- In the peek function, we have to return the top element of the stack without deleting it.
- So, to do the same with a singly linked list, first, we will check if the list is empty or not.
- If the list is empty, we will simply exit as there is no data in the list.
- If the list is not empty, we will just return the head → data, as it is the top element of the stack.
-
isEmpty()
- In the isEmpty function, we have to check whether the stack is empty or not.
- So, to do the same with a singly linked list, we will just check if the head is NULL or not.
- If the head is NULL, it means that the list is empty, so we will return true.
- If the head is not NULL, it means that the list is not empty, so we will return false.
-
display()
- In the display function, we have to print the stack.
- So, to do the same with a singly linked list, we will do a list traversal and print the elements of list one by one.
Dry Run of Stack using Linked List
Code for Stack Implementation using Linked List
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* link;
};
struct Node* top;
// Using this function we will be pushing elements into the stack
void push(int data)
{
struct Node* tem;
tem = new Node();
if (!tem)
{
cout << "\nHeap Overflow";
exit(1);
}
tem->data = data;
tem->link = top;
top = tem;
}
// Using this function we will be checking whether the stack is empty or not
int isEmpty()
{
return top == NULL;
}
// Using this function we will return the top element of the stack
int peek()
{
if (!isEmpty())
return top->data;
else
exit(1);
}
// Using this function we will pop the top element of the stack
void pop()
{
struct Node* tem;
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
tem = top;
top = top->link;
tem->link = NULL;
free(tem);
}
}
// this function will be used to display the items of the stack
void display()
{
struct Node* tem;
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
tem = top;
while (tem != NULL)
{
cout << tem->data << "-> ";
tem = tem->link;
}
}
}
int main()
{
push(4);
push(3);
push(2);
push(1);
display();
cout << "\nTop element is "<< peek() << endl;
pop();
pop();
cout<<"Stack after popping 2 times \n";
display();
cout << "\nTop element is "<< peek() << endl;
return 0;
} import static java.lang.System.exit;
class StackUsingLinkedlist {
private class Node {
int data;
Node link;
}
Node top;
StackUsingLinkedlist()
{
this.top = null;
}
// Using this function we will be pushing elements into the stack
public void push(int x)
{
Node temp = new Node();
if (temp == null) {
System.out.print("\nHeap Overflow");
return;
}
temp.data = x;
temp.link = top;
top = temp;
}
// Using this function we will be checking whether the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// using this function we will return the top element of the stack
public int peek()
{
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Using this function we will pop the top element of the stack
public void pop()
{
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
top = (top).link;
}
// this function will be used to display the items of the stack
public void display()
{
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
while (temp != null) {
System.out.printf("%d->", temp.data);
temp = temp.link;
}
}
}
}
class PrepBytes {
public static void main(String[] args)
{
StackUsingLinkedlist stk = new StackUsingLinkedlist();
stk.push(4);
stk.push(3);
stk.push(2);
stk.push(1);
stk.display();
System.out.printf("\nTop element is %d\n", stk.peek());
System.out.println("Stack after popping 2 times");
stk.pop();
stk.pop();
stk.display();
System.out.printf("\nTop element is %d\n", stk.peek());
}
} # your code goes hereclass Node:
class Node:
def __init__(self,data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def isempty(self):
if self.head == None:
return True
else:
return False
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
def pop(self):
if self.isempty():
return None
else:
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
MyStack = Stack()
MyStack.push(4)
MyStack.push(3)
MyStack.push(2)
MyStack.push(1)
MyStack.display()
print("\nTop element is ",MyStack.peek())
MyStack.pop()
MyStack.pop()
print("Stack after poping 2 times")
MyStack.display()
print("\nTop element is ", MyStack.peek()) Output for Stack Implementation using Linked List
1->2->3->4->
Top element is 1
Stack after popping 2 times
3->4->
Top element is 3Time and Space Complexity of Stack Implementation using Linked List
The time complexity for various methods is written below:
- push(): O(1)
- pop(): O(1)
- peek(): O(1)
- isEmpty(): O(1)
- display(): O(n)
Space Complexity for implementation of stack using linked list is O(n) for every operation.
Advantages of Stack Implementation using Linked List
We can implement Stack using an array as well as using the Linked List, but implementation of stack using Linked List have more advantages. The advantages of implementing a stack using linked list are as follows:
- Dynamic size: The size of the stack can be adjusted dynamically as the linked list can grow or shrink according to the elements pushed or popped.
- Efficient memory utilization: The linked list uses only as much memory as required by the elements in the stack, whereas an array-based implementation might have to allocate extra memory to accommodate growth.
- Flexibility: Linked list implementation provides more flexibility than an array-based implementation as elements can be added or removed anywhere in the list.
- Ease of implementation: Implementing a stack using linked list is easier as it only requires a few basic operations to be performed on the linked list such as adding and removing elements from the beginning.
- Improved performance: The linked list implementation can provide improved performance compared to an array-based implementation, especially when dealing with large stacks, as inserting or removing elements from the beginning of the linked list is an O(1) operation.
Disadvantages of Stack Implementation using Linked List
The disadvantages of implementing stack using linked list are:
- Increased memory usage: As each element in the stack is stored as a separate node, linked list implementation of stack takes up more memory than other implementations such as arrays.
- Slower performance: Operations on the linked list take more time compared to arrays, as accessing elements in linked lists require traversing through multiple nodes.
- Complexity: Linked list implementation of the stack requires more complex coding compared to other implementations such as arrays, leading to longer development time and more bugs.
- Dynamic allocation limitations: Dynamic allocation of memory for linked lists may be limited by the amount of available memory on the system.
- Pointer management: Managing pointers in linked lists is more challenging compared to arrays, leading to increased risk of bugs and data corruption.
Applications of Stack in Data Structure
Stack is a commonly used data structure in computer science and has numerous applications, some of which are:
- Expression evaluation and parsing: Stack is used to evaluate expressions such as infix, postfix, and prefix expressions.
- Undo/Redo operations: Stack can be used to maintain a history of performed actions, allowing users to undo/redo actions as needed.
- Memory management: Stack is used in the implementation of function calls and returns, as well as in the allocation of memory in a system.
- Balancing of symbols: Stack can be used to check the balance of symbols in expressions and code.
- Backtracking: Stack is often used in the implementation of algorithms that involve searching and backtracking, such as depth-first search.
- Browser history: Stack is used to maintain a history of visited pages in a web browser, allowing users to go back and forth between pages.
Summary
So, in this article, we learned that one data structure can be used to implement another data structure. We have seen how the implementation of stack using linked list works. We have learned about various methods of Stack along with several advantages and disadvantages of Stack implementation using Linked List. We have also discussed several applications of Stack in Data Structure.
FAQs Related to Stack Data Structure
1. When we implement stack using linked list?
We can implement a stack using a linked list when we need a data structure with last-in, first-out (LIFO) behavior, and the size of the stack may vary dynamically during runtime. The linked list implementation allows for efficient and dynamic adjustments to the size of the stack, making it a good choice for implementing a stack data structure.
2. What is peek() in Linked list?
The peek() method retrieves the first head of the list, but it does not remove the head.
3. What is pollLast() in the linked list?
This method removes or retrieves the last element of the list, and returns null if the list is empty.
4. What is Time Complexity for push() and pop() function of stack?
The time complexity for both operations is O(1), which means they can take a constant time to execute.