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

Stack Implementation

Next ►
►

In this section, we will delve into the implementation of stacks. Stacks are a fundamental data structure that follows the Last In, First Out (LIFO) principle. We will cover:

  1. Conceptual Overview
  2. Implementation Using Arrays
  3. Implementation Using Linked Lists
  4. Code Examples
  5. Common Mistakes and Tips

Conceptual Overview

A stack is a collection of elements with two principal operations:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes the element from the top of the stack.

Other auxiliary operations include:

  • Peek/Top: Returns the top element without removing it.
  • isEmpty: Checks if the stack is empty.
  • isFull: Checks if the stack is full (relevant for array-based implementations).

Implementation Using Arrays

Advantages:

  • Simple and easy to implement.
  • Direct access to elements using indices.

Disadvantages:

  • Fixed size, which can lead to overflow if the stack exceeds its capacity.

Code Example

class StackArray:
    def __init__(self, capacity):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, item):
        if self.is_full():
            raise OverflowError("Stack is full")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.stack[self.top]
        self.stack[self.top] = None
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[self.top]

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

Explanation

  • Initialization: The stack is initialized with a fixed capacity.
  • Push: Adds an element to the top of the stack if it's not full.
  • Pop: Removes and returns the top element if the stack is not empty.
  • Peek: Returns the top element without removing it.
  • isEmpty: Checks if the stack is empty.
  • isFull: Checks if the stack is full.

Implementation Using Linked Lists

Advantages:

  • Dynamic size, no need to define a fixed capacity.
  • Efficient memory usage.

Disadvantages:

  • Slightly more complex to implement.
  • Additional memory overhead for storing pointers.

Code Example

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

class StackLinkedList:
    def __init__(self):
        self.top = None

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.top.data
        self.top = self.top.next
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.top.data

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

Explanation

  • Node Class: Represents each element in the stack.
  • Initialization: The stack is initialized with the top set to None.
  • Push: Adds a new node to the top of the stack.
  • Pop: Removes and returns the top node if the stack is not empty.
  • Peek: Returns the top node's data without removing it.
  • isEmpty: Checks if the stack is empty.

Common Mistakes and Tips

  • Array-Based Stack Overflow: Always check if the stack is full before pushing an element.
  • Linked List Memory Management: Ensure that nodes are properly linked and unlinked to avoid memory leaks.
  • Boundary Conditions: Always handle edge cases such as popping from an empty stack.

Conclusion

In this section, we have covered the implementation of stacks using both arrays and linked lists. Each method has its own advantages and disadvantages. Understanding these implementations will help you choose the appropriate stack structure based on the requirements of your application. Next, we will explore the various applications of stacks to see how they can be utilized in real-world scenarios.

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