C program to implement stack and queue using linked list

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.

Table of Contents Show

Linked list implementation of stack
Queue – Linked List Implementation
Implement a stack using singly linked list
Queue using linked list
Stack using linked list
C program to Implement a Stack using Singly Linked List
Problem Definition

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 – 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.

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 <bits/stdc++.h>

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# 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

<script>
// Javascript program to Implement a stack
// using singly linked list
// import package
// A linked list node
class Node
{

constructor()

{

this.data=0;

this.link=null;

}
}
// Create Stack Using Linked list
class StackUsingLinkedlist
{

constructor()

{

this.top=null;

}

// Utility function to add an element x in the stack

push(x)

{

// create new node temp and allocate memory

let temp = new Node();

// check if stack (heap) is full. Then inserting an

// element would lead to stack overflow

if (temp == null) {

document.write("<br>Heap Overflow");

return;

}

// initialize data into temp data field

temp.data = x;

// put top reference into temp link

temp.link = this.top;

// update top reference

this.top = temp;

}

// Utility function to check if the stack is empty or not

isEmpty()

{

return this.top == null;

}

// Utility function to return top element in a stack

peek()

{

// check for empty stack

if (!this.isEmpty()) {

return this.top.data;

}

else {

document.write("Stack is empty<br>");

return -1;

}

}

// Utility function to pop top element from the stack

pop() // remove at the beginning

{

// check for stack underflow

if (this.top == null) {

document.write("<br>Stack Underflow");

return;

}

// update the top pointer to point to the next node

this.top = this.top.link;

}

display()

{

// check for stack underflow

if (this.top == null) {

document.write("<br>Stack Underflow");

}

else {

let temp = this.top;

while (temp != null) {

// print node data

document.write(temp.data+"->");

// assign temp link to temp

temp = temp.link;

}

}

}
}
// main class
// create Object of Implementing class

let 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

document.write("<br>Top element is ", obj.peek()+"<br>");
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack

document.write("<br>Top element is ", obj.peek()+"<br>");
// This code is contributed by rag2127
</script>

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

Read Full Article

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.

Stack using linked list

Stack using an array - drawback

If we implement the stack 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, it will only work for a fixed number of elements.

Solution

We can implement the stack using the linked list.

In the linked list, we can change its size at runtime.

C program to Implement a Stack using Singly Linked List

/* * C Program to Implement a Stack using Linked List */ #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }*top; /* Initialize an empty stack */ void initialize() { top = NULL; } /* Checks if Stack is empty or not */ int isEmpty() { if (top == NULL) return 1; else return 0; } /* Returns the top element of Stack */ int peek() { return top->data; } /* Count stack elements */ int getStackSize(struct node *head){ /* Input Validation */ if (head == NULL) { printf("Error : Invalid stack pointer !!!\n"); return; } int length = 0; while(head != NULL){ head = head->next; length++; } return length; } /* Push an Element in Stack */ void push(int num) { struct node *temp; temp =(struct node *)malloc(1*sizeof(struct node)); temp->data = num; if (top == NULL) { top = temp; top->next = NULL; } else { temp->next = top; top = temp; } } /* Pop Operation: Removes Top Element of the Stack */ void pop() { struct node *temp; if (isEmpty(top)) { printf("\nStack is Empty\n"); return; } else { temp = top; top = top->next; printf("Removed Element : %d\n", temp->data); free(temp); } } /* Prints the linked list representation of a stack */ void printStack(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } printf("\n"); } void main() { /* Initialize Stack */ initialize(); /* Push Elements in stack */ push(1); push(2); push(3); push(4); /* Prints Size of Stack */ printf("Stack Size : %d\n", getStackSize(top)); /* Printing top element of Stack */ printf("\nTop Element : %d\n", peek()); /* Printing Stack */ printf("Stack as linked List\n"); printStack(top); /* Removing elements from stack */ pop(); pop(); pop(); pop(); pop(); printStack(top); return; } Output
Stack Size : 4 Top Element : 4 Stack as linked List 4-->3-->2-->1 Removed Element : 4 Removed Element : 3 Removed Element : 2 Removed Element : 1 Stack is Empty

Problem Definition

A stack can be implemented using array data structure or a dynamically growing linked-list data structures. The linked-list implementation of stack does not need to check for “stack being full” because the list grows dynamically.

A linked-list has nodes that are linked together using pointers. A linked-list node has a data and a link pointer of type node that points to the next node element in the list.

An example of a node

struct node { int data; node* next; };

Steps to build a linked-list based stack is as follows

Step 1: Declare pointers to build initial stack.

struct node *head, *temp;

The *head pointer of type struct points to the first node of the linked-list and the *temp pointer of type struct points to any new node you create. The pointers are created but does not point to anything. You must point to some variable or allocate memory to initialize them.

Step 2: Initialize the head node.

In C programming language, you must initialize any pointer by dynamically allocating memory using function malloc (). You initialize pointer head as follows

head =(struct node* )malloc( ( struct node))

Now that have assigned memory to the head node, give values to its variables.

head->data=10; head->next =NULL;

See the following diagram to understand what initializing a node means.

Single Node in Linked-list

The head pointer points to a location which has address 0x3000 and data value is 10. The node->next is also a pointer that maintain the linked-list and currently points to NULL.

Step 3: Create a new node and *temp points to it

We now create a new node by allocating memory dynamically for *temp.

temp = (struct node*) malloc ((struct node));

assign values to the variable and point the next pointer to NULL.

temp->data = 20; temp->next = NULL;

See the memory drawing below to understand the process.

Two Independent Node of Linked List

Right now, we have two independent nodes, not a linked-list. To start building a list and making sure that the linked-list work like a stack.

Step 4: Now temp nodes must point to head node so that it becomes the first node or head node.

temp->next = head;

Pointer in Action

A Linked-List

Step 5: Write a pop () function that removes the top element.

In the stack, pop () function directly removes the top element automatically. You need to skip the top element and make the second element as the head of the linked-list based stack.

To make a new head use following code

head = head->next;