This program demonstrates the implementation of a stack data structure using a linked list. Stacks are a type of data structure with Last In First Out (LIFO) access policy. The operations demonstrated in this stack are:

• Push: Add an item to the top of the stack.
• Pop: Remove the item at the top of the stack.
• Peek: Get the item at the top of the stack without removing it.
• is_empty: Check if the stack is empty.

Code Explanation

The stack functionality is encapsulated within a class Stack. This class uses an inner class Node, which represents an element in the stack. Here’s a detailed breakdown of the methods within the Stack class:

1. Node class: A simple class for storing data and the link to the next node.
2. __init__: Initializes the stack.
3. push: Adds a new element to the top of the stack.
4. pop: Removes the element from the top of the stack and returns it.
5. peek: Returns the top element without removing it.
6. is_empty: Returns True if the stack is empty, otherwise False.

Python Code

class Stack:
    class Node:
        def __init__(self, value):
            self.value = value
            self.next = None

    def __init__(self):
        self.top = None

    def push(self, item):
        new_node = self.Node(item)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        current_top = self.top
        self.top = self.top.next
        return current_top.value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.top.value

    def is_empty(self):
        return self.top is None

Usage

To use this stack, instantiate an object of the Stack class and use the push, pop, and peek methods to manipulate it.