Understanding Stack

Introduction

So, what exactly is a stack? At its core, a stack is a linear data structure that follows the "Last-In, First-Out" (LIFO) principle. It behaves much like a real-life stack of objects, where the last item placed on top is the first one to be removed. This unique characteristic makes stacks ideal for managing information that requires strict ordering based on the order of insertion and retrieval.

Imagine a stack of books on a desk: if you add a new book, it goes on top of the pile, and when you want to retrieve a book, you always take the one from the top. Similarly, a stack data structure organizes data items in a way that allows efficient insertion and removal operations, making it a powerful tool in a variety of scenarios.

Stacks are used extensively in algorithm design and implementation. They provide an elegant solution for problems that involve nested structures, such as parentheses matching, expression evaluation, and backtracking algorithms. Moreover, they serve as a crucial building block for other data structures, such as queues, hash tables, and compilers.

Implementation

Push Operation

The push operation adds an element to the top of the stack. It involves the following steps:
- Check if the stack is full or not.
- If the stack is full, display an overflow message.
- If the stack is not full, increment the top pointer and add the new element to the stack.
```
  def push(stack, element):
      if len(stack) == MAX_SIZE:
          print("Stack Overflow")
      else:
          stack.append(element)
          print("Element", element, "pushed to the stack")
```
Pop Operation

The pop operation removes the topmost element from the stack. It involves the following steps:
- Check if the stack is empty or not.
- If the stack is empty, display an underflow message.
- If the stack is not empty, remove the element from the top of the stack and decrement the top pointer.
```
  def pop(stack):
      if len(stack) == 0:
          print("Stack Underflow")
      else:
          element = stack.pop()
          print("Element", element, "popped from the stack")
```
Top Operation

The top operation returns the topmost element of the stack without removing it. It involves the following steps:
- Check if the stack is empty or not.
- If the stack is empty, display an underflow message.
- If the stack is not empty, return the top element.
```
  def top(stack):
      if len(stack) == 0:
          print("Stack Underflow")
      else:
          return stack[-1]
```

Display

The display operation shows all the elements of the stack from top to bottom. It involves the following steps:

Check if the stack is empty or not.
If the stack is empty, display an underflow message.

If the stack is not empty, iterate through the stack and print each element.

  def display(stack):
      if len(stack) == 0:
          print("Stack Underflow")
      else:
          print("Elements in the stack:")
          # reversed for the last in first flow
          for element in reversed(stack):
              print(element)

Time Complexities

Push Operation

The time complexity for the push operation is O(1) or constant time. It involves appending an element to the end of the stack, which can be done in a constant amount of time, regardless of the size of the stack.
Pop Operation

The time complexity for the pop operation is also O(1) or constant time. It involves removing the topmost element from the stack, which can be achieved by directly accessing and removing the last element in the stack, regardless of the size of the stack.
Top Operation

The time complexity for the top operation is O(1) or constant time. It involves returning the topmost element of the stack, which can be obtained by accessing the last element in the stack, regardless of the size of the stack.
Display Operation

The time complexity for the display operation is O(n), where n is the number of elements in the stack. It involves iterating through the entire stack and printing each element. As the number of elements in the stack increases, the time taken to display all the elements will also increase linearly.

Real-Time Example

A common real-time example that demonstrates the use of a stack is the undo/redo functionality in a text editor. Let's consider a simplified implementation of a text editor in Python that utilizes a stack to provide undo and redo capabilities.

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []

    def insert_text(self, new_text):
        self.undo_stack.append(self.text)
        self.text += new_text
        self.redo_stack = []

    def delete_text(self, num_chars):
        if num_chars >= len(self.text):
            self.undo_stack.append(self.text)
            self.text = ""
        else:
            self.undo_stack.append(self.text)
            self.text = self.text[:-num_chars]
        self.redo_stack = []

    def undo(self):
        if len(self.undo_stack) > 0:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()

    def redo(self):
        if len(self.redo_stack) > 0:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

    def get_text(self):
        return self.text

editor = TextEditor()

editor.insert_text("Hello, ")
editor.insert_text("world!")
print(editor.get_text())  # Output: Hello, world!

editor.undo()
print(editor.get_text())  # Output: Hello, 

editor.redo()
print(editor.get_text())  # Output: Hello, world!

The TextEditor class represents our text editor. It has attributes for storing the text, the undo stack, and the redo stack.
The insert_text method is used to insert new text into the editor. It appends the current state of the text to the undo stack, adds the new text to the existing text, and clears the redo stack.
The delete_text method deletes a specified number of characters from the text. It works similarly to insert_text by appending the current state of the text to the undo stack, modifying the text accordingly, and clearing the redo stack.
The undo method pops the top element from the undo stack (representing the previous state of the text) and restores it as the current text. It appends the current state of the text to the redo stack for potential redo operations.
The redo method pops the top element from the redo stack (representing a previously undone state of the text) and restores it to the current text. It appends the current state of the text to the undo stack for potential undo operations.
The get_text method returns the current text stored in the editor.

Understanding Stack

Table of contents

Introduction

Implementation

Time Complexities

Real-Time Example