The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Introduction to Stacks

Next ►
►

What is a Stack?

A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). The most recently added element is the one that is removed first.

Key Characteristics of Stacks:

  • LIFO Structure: The last element added to the stack is the first one to be removed.
  • Operations: The primary operations are push (to add an element) and pop (to remove an element).
  • Top: The top of the stack is the most recently added element.

Real-World Examples of Stacks

  • Browser History: When you navigate to a new webpage, the current page is pushed onto the stack. When you click the back button, the most recent page is popped from the stack.
  • Undo Mechanism in Text Editors: Each action is pushed onto a stack, and the undo operation pops the most recent action.
  • Call Stack in Programming: Function calls are managed using a stack. The most recent function call is at the top of the stack.

Basic Operations

Push Operation

The push operation adds an element to the top of the stack.

Pop Operation

The pop operation removes the element from the top of the stack.

Peek Operation

The peek operation returns the element at the top of the stack without removing it.

IsEmpty Operation

The isEmpty operation checks if the stack is empty.

IsFull Operation

The isFull operation checks if the stack is full (in case of a stack with a fixed size).

Stack Representation

Stacks can be represented using arrays or linked lists. Below is a comparison:

Array-Based Stack Linked List-Based Stack
Fixed size Dynamic size
Simple to implement More complex to implement
May waste space if not full Efficient use of memory

Example: Array-Based Stack Implementation in Python

class Stack:
    def __init__(self, max_size):
        self.stack = []
        self.max_size = max_size

    def push(self, item):
        if len(self.stack) < self.max_size:
            self.stack.append(item)
        else:
            print("Stack Overflow")

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            print("Stack Underflow")
            return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return None

    def is_empty(self):
        return len(self.stack) == 0

    def is_full(self):
        return len(self.stack) == self.max_size

# Example usage
stack = Stack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2

Explanation:

  • Initialization: The stack is initialized with a maximum size.
  • Push: Adds an item to the stack if it is not full.
  • Pop: Removes and returns the top item if the stack is not empty.
  • Peek: Returns the top item without removing it.
  • IsEmpty: Checks if the stack is empty.
  • IsFull: Checks if the stack is full.

Practical Exercises

Exercise 1: Implement a Stack Using a Linked List

Task: Implement a stack using a singly linked list. Ensure you include the push, pop, peek, is_empty, and is_full operations.

Solution:

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

class LinkedListStack:
    def __init__(self, max_size):
        self.head = None
        self.size = 0
        self.max_size = max_size

    def push(self, item):
        if self.size < self.max_size:
            new_node = Node(item)
            new_node.next = self.head
            self.head = new_node
            self.size += 1
        else:
            print("Stack Overflow")

    def pop(self):
        if not self.is_empty():
            popped_node = self.head
            self.head = self.head.next
            self.size -= 1
            return popped_node.value
        else:
            print("Stack Underflow")
            return None

    def peek(self):
        if not self.is_empty():
            return self.head.value
        else:
            return None

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.max_size

# Example usage
stack = LinkedListStack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2

Explanation:

  • Node Class: Represents each element in the linked list.
  • LinkedListStack Class: Manages the stack operations using linked list nodes.

Common Mistakes and Tips

  • Stack Overflow: Always check if the stack is full before pushing an element.
  • Stack Underflow: Always check if the stack is empty before popping an element.
  • Memory Management: In linked list-based stacks, ensure proper memory management to avoid memory leaks.

Conclusion

In this section, we introduced the concept of stacks, their real-world applications, and basic operations. We also provided examples of stack implementation using arrays and linked lists. Understanding stacks is crucial as they are fundamental data structures used in various algorithms and applications. In the next section, we will delve deeper into the basic operations with stacks.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved