search

How will you implement stack and queue using linked list?

2 years ago
Komentar: 62793
Dibaca: 115

Implementing Stack and Queue Using Linked Lists in C#

Stacks and queues are fundamental data structures in computer science. Let's take a look at how to implement them using C#!

by
Ankit Sharma
·
Dec. 29, 17 · Web Dev Zone · Tutorial
Like (4)
Comment
Save
Tweet
51.96K Views

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 .

How will you implement stack and queue using linked list?
How will you implement stack and queue using linked list?
How will you implement stack and queue using linked list?

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:

  1. push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
  2. pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
  3. peek(): Return the top element.
  4. display(): Print all elements in Stack.

Below is the implementation of the above approach:




// 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 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());
}
}




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




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

How will you implement stack and queue using linked list?




Article Tags :
Linked List
Stack
Technical Scripter
Technical Scripter 2018
Practice Tags :
Linked List
Stack
Read Full Article

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.

How to implement stack and queue using linked list

Data Structures are used to store large amounts of data in an efficient and categorical manner. For example in lists, arrays, tuples, dictionaries, and sets.

We are now gonna look into Linear Data Structures:

  • Linked Lists
  • Stacks
  • Queues

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.


How will you implement stack and queue using linked list?

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.

Stack Implementation Using Linked List

Lesson 12 of 54By Simplilearn

Last updated on Sep 15, 20213497
How will you implement stack and queue using linked list?
PreviousNext
  • Tutorial Playlist

    Data Structure Tutorial

    Overview

    Arrays in Data Structures: A Guide With Examples

    Lesson - 1

    All You Need to Know About Two-Dimensional Arrays

    Lesson - 2

    All You Need to Know About a Linked List in a Data Structure

    Lesson - 3

    The Complete Guide to Implement a Singly Linked List

    Lesson - 4

    The Ultimate Guide to Implement a Doubly Linked List

    Lesson - 5

    The Fundamentals for Understanding Circular Linked List

    Lesson - 6

    The Ultimate Guide To Understand The Differences Between Stack And Queue

    Lesson - 7

    Implementing Stacks in Data Structures

    Lesson - 8

    Your One-Stop Solution for Stack Implementation Using Array

    Lesson - 9

    Your One-Stop Solution for Queue Implementation Using Array

    Lesson - 10

    Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

    Lesson - 11

    Your One-Stop Solution for Stack Implementation Using Linked-List

    Lesson - 12

    The Definitive Guide to Understand Stack vs Heap Memory Allocation

    Lesson - 13

    All You Need to Know About Linear Search Algorithm

    Lesson - 14

    All You Need to Know About Breadth-First Search Algorithm

    Lesson - 15

    A One-Stop Solution for Using Binary Search Trees in Data Structure

    Lesson - 16

    The Best Tutorial to Understand Trees in Data Structure

    Lesson - 17

    A Complete Guide to Implement Binary Tree in Data Structure

    Lesson - 18

    A Holistic Look at Using AVL Trees in Data Structures

    Lesson - 19

    All You Need to Know About Tree Traversal in Data Structure

    Lesson - 20

    The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

    Lesson - 21

    The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

    Lesson - 22

    The Best and Easiest Way to Understand an Algorithm

    Lesson - 23

    Your One-Stop Solution to Understand Shell Sort Algorithm

    Lesson - 24

    Your One-Stop Solution to Quick Sort Algorithm

    Lesson - 25

    The Most Useful Guide to Learn Selection Sort Algorithm

    Lesson - 26

    Everything You Need to Know About Radix Sort Algorithm

    Lesson - 27

    Everything You Need to Know About the Counting Sort Algorithm

    Lesson - 28

    Everything You Need to Know About the Merge Sort Algorithm

    Lesson - 29

    Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

    Lesson - 30

    Everything You Need to Know About the Bubble Sort Algorithm

    Lesson - 31

    The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

    Lesson - 32

    Your One-Stop Solution to Understand Recursive Algorithm in Programming

    Lesson - 33

    The Definitive Guide to Understanding Greedy Algorithm

    Lesson - 34

    Your One-Stop Solution to Understand Backtracking Algorithm

    Lesson - 35

    The Fundamentals of the Bellman-Ford Algorithm

    Lesson - 36

    Your One-Stop Solution for Graphs in Data Structures

    Lesson - 37

    The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

    Lesson - 38

    A Simplified and Complete Guide to Learn Space and Time Complexity

    Lesson - 39

    All You Need to Know About the Knapsack Problem : Your Complete Guide

    Lesson - 40

    The Fibonacci Series: Mathematical and Programming Interpretation

    Lesson - 41

    The Holistic Look at Longest Common Subsequence Problem

    Lesson - 42

    The Best Article to Understand What Is Dynamic Programming

    Lesson - 43

    A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

    Lesson - 44

    A Holistic Guide to Learn Stop Solution Using Dynamic Programming

    Lesson - 45

    One Stop Solution to All the Dynamic Programming Problems

    Lesson - 46

    Understanding the Fundamentals of Binomial Distribution

    Lesson - 47

    Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

    Lesson - 48

    Understanding the Difference Between Array and Linked List

    Lesson - 49

    The Best Article Out There to Understand the B+ Tree in Data Structure

    Lesson - 50

    A Comprehensive Look at Queue in Data Structure

    Lesson - 51

    Your One-Stop Solution to Understand Coin Change Problem

    Lesson - 52

    The Best Way to Understand the Matrix Chain Multiplication Problem

    Lesson - 53

    Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

    Lesson - 54

Table of Contents

View More

The problem with stack implementation using an array is working with only a fixed number of data elements, so we can also go for stack implementation using linked-list. Linked-list is the data structure that allocated memory dynamically, but in both cases, the time complexity is the same for all the operations like push, pop and peek.

Stack Implementation Using Linked-List

We already knew that linked lists allocate memory dynamically. Stack implementation using linked-list, the nodes are maintained in non-contiguous memory. Each node contains a pointer to the immediate next in line node in the Stack.

In Stack, implementation using Linked-List, every new element inserted to the top of the Stack which means every new inserting element pointed by the top and whenever we want to delete element from the Stack which is pointing to the top of the Stack by moving the top by moving top to is the previous node in the linked -list. The following field of the first element must always be NULL. There is an overflow condition in the Stack if the space left in the memory heap is not sufficient to create a node.

How will you implement stack and queue using linked list?

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
How will you implement stack and queue using linked list?

Top List List

Pos Terkait

Proses penyaluran listrik untuk sampai ke konsumen melalui tahap
Proses penyaluran listrik untuk sampai ke konsumen melalui tahap

Langkah langkah proses penyaluran listrik dari pembangkit listrik?
Langkah langkah proses penyaluran listrik dari pembangkit listrik?

Nilai potensial listrik di dalam bola adalah
Nilai potensial listrik di dalam bola adalah

Apa saja bahan bahan yang dapat digunakan membuat topeng?
Apa saja bahan bahan yang dapat digunakan membuat topeng?

Insertion at the end of a linear linked list is a special case.
Insertion at the end of a linear linked list is a special case.

How is the order of the entries of an ADT list determined
How is the order of the entries of an ADT list determined

Cara Membuat Produk Rekayasa pembangkit listrik Sederhana
Cara Membuat Produk Rekayasa pembangkit listrik Sederhana

Which command is used to add 5 to the third position in list named LST?
Which command is used to add 5 to the third position in list named LST?

Write a Python program to get the smallest odd number from a list
Write a Python program to get the smallest odd number from a list

Differentiate between list and tuple with a suitable example for each
Differentiate between list and tuple with a suitable example for each

Periklanan

BERITA TERKINI

Bisakah Anda mengaktifkan javascript di ponsel?
1 years ago . by AdorableMantra
Bagaimana Anda menghapus teks duplikat dengan python?
1 years ago . by DecreasingEmperor
Cara menghapus latar belakang video di CapCut
1 years ago . by SkepticalDugout
Apa itu rounddown dalam excel?
1 years ago . by JollyDollar
Dapatkan array multidimensi kunci php
1 years ago . by LuridRecognition
Cara mengeluarkan darah haid yang tidak keluar
1 years ago . by CuriousRedundancy
Dapatkan javascript bulan dengan 0
1 years ago . by NastyMedics
Python cetak daftar daftar secara vertikal
1 years ago . by DeviantColors
Cara membersihkan kacamata yang tergores
1 years ago . by Two-storyDealing
Cara menggunakan variable to dataframe python
1 years ago . by ThrobbingMetaphysics

Toplist Popular

#1
Top 10 berikut ini yang bukan merupakan penetapan tujuan visi perusahaan adalah 2022
1 years ago
#2
Top 10 sebuah bak air berbentuk balok dengan ukuran panjang 40 cm, lebar 30 cm, dan tinggi 35 cm 2022
1 years ago
#3
Top 9 banjir bukan sekadar bencana alam paragraf 3 gagasan utama 2022
1 years ago
#4
Top 10 diketahui himpunan himpunan sebagai berikut p bilangan ganjil yang kurang dari 15 2022
1 years ago
#5
Top 10 penyelesaian dari persamaan 3x 2 y 9 dan 2x y 3 adalah 2022
1 years ago
#6
Top 10 bagaimana cara memberi salam kepada orang tua dan guru yang benar brainly 2022
1 years ago
#7
Top 10 semakin tinggi nilai toleransi semakin tinggi nilai integrasi nasional 2022
1 years ago
#8
Top 10 benda kerajinan tidak boleh membahayakan pemakainya maka benda kerajinan memiliki prinsip 2022
1 years ago
#9
Top 9 bagian tutup sumbat termos biasanya terbuat dari benda berjenis brainly 2022
1 years ago
#10
Top 9 pernyataan yang sesuai dengan prinsipteori evolusi jb lamarck ditunjukkan oleh angka 2022
1 years ago

Periklanan

Terpopuler

Token Data

Periklanan

Tentang Kami

Legal

Dukungan

Social

homeenfritzhtrjako
Copyright © 2024 idkuu.com Inc.