{"id":4992,"date":"2021-09-16T11:50:29","date_gmt":"2021-09-16T11:50:29","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4992"},"modified":"2023-04-23T03:44:42","modified_gmt":"2023-04-23T03:44:42","slug":"implement-a-stack-using-a-singly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/implement-a-stack-using-a-singly-linked-list\/","title":{"rendered":"Implement a Stack using a Singly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

A stack is an abstract data type that follows the LIFO (Last In First Out) principle. It is widely used in computer science, programming languages, and operating systems. Implementing a stack using a singly linked list is a common exercise that helps to understand how linked lists work and how they can be used to implement other data structures. In this article, we will learn how to do stack implementation using singly linked list.<\/p>\n

Understanding Stack Implementation Using Singly Linked List<\/h2>\n

When implementing a stack using singly linked list, it is essential to consider the standard operations of push, pop, and peek. The push operation involves adding an element to the top of the stack, while the pop operation removes the top element from the stack. The peek operation returns the value of the top element without removing it.<\/p>\n

Suppose we insert elements 4, 3, 2, and 1 into the stack using the push operation. In push operation elements are added to the top of the stack. In other words, the last element to be pushed onto the stack becomes the top element, while the first element to be pushed becomes the bottom element. So, when elements are pushed onto the stack in that order, the top of the stack will contain element 1, and the bottom of the stack will contain element 4.<\/p>\n

When we want to access the elements in the stack, we can only access them in a LIFO (Last-In-First-Out) manner, meaning that we can only access the top element first, followed by the second-to-top element, and so on. In other words, we must first remove the top element using the pop operation to access the next element in the stack.<\/p>\n

So, to access the elements in the order 1, 2, 3, and 4, we would need to pop the elements from the stack in reverse order, starting with 1, then 2, then 3, and finally 4. This is because the top of the stack currently contains element 1, so it must be popped first to access the next element, which is 2. The below image shows how these elements are represented in a singly linked list.<\/p>\n

\"\"<\/p>\n

Overall when accessing elements in a stack, we can only access them in reverse order of insertion, starting with the last element pushed onto the stack.<\/p>\n

Approach of Stack Implementation Using Singly Linked List<\/h3>\n

The approach and algorithm for implementing a stack using singly linked list involves five main functions: push, pop, peek, isEmpty, and display.<\/p>\n

    \n
  1. \n

    push() Function<\/strong>
    \nThe push function adds an element to the top of the stack. To implement this function with a singly linked list, we first check if the list is empty. If it is, we make the new node the head of the list. If the list is not empty, we make the next of the new node point to the head of the list and then make the new node the new head of the list.<\/p>\n<\/li>\n

  2. \n

    pop() Function<\/strong>
    \nThe pop function removes the topmost element of the stack. To implement this function with a singly linked list, we first check if the list is empty. If it is, we return NULL. If there is only one node in the list, we remove the head and return NULL. If there is more than one node in the list, we create a new node temp and make it point to the head. Then, we make the 2nd node our new head by doing head = head \u2192 next. Finally, we make temp \u2192 next = NULL, and free (temp).<\/p>\n<\/li>\n

  3. \n

    Peek() Function<\/strong>
    \nThe peek function returns the top element of the stack without deleting it. To implement this function with a singly linked list, we first check if the list is empty. If it is, we simply exit as there is no data in the list. If the list is not empty, we just return the head \u2192 data, as it is the top element of the stack.<\/p>\n<\/li>\n

  4. \n

    isEmpty() Function<\/strong>
    \nThe isEmpty function checks whether the stack is empty or not. To implement this function with a singly linked list, we 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.<\/p>\n<\/li>\n

  5. \n

    display() Function<\/strong>
    \nThe display function prints the stack. To implement this function with a singly linked list, we do a list traversal and print the elements of the list one by one.<\/p>\n<\/li>\n<\/ol>\n

    Dry Run of Implementing Stack Using Singly Linked List<\/h3>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    Code Implementation of Stack Using Singly Linked List<\/h3>\n

    Now, let’s see how to implement stack using singly linked list in C, C++, Java, and Python:<\/p>\n\t\t\t\t\t\t