Stacks in Scala: Implementation and Operations

Hello, dear student! Today's lesson will take you on an exciting journey through Stacks, a powerful tool in Scala. In programming, Stacks are fundamental data structures utilized in various applications. Our goal for this lesson is to understand the concept of Stacks, learn how to implement and manipulate them in Scala, and delve deep into their complexities. Let's get started!

First and foremost, let's understand what a Stack is. Imagine a stack of plates that you can only remove from the top. That's precisely what a Stack is: a Last-In, First-Out (LIFO) structure. Stacks are used in memory management, backtracking algorithms, and more. The key operations involved are Push (adding an element to the top of the stack), Pop (removing the topmost element), and Peek (looking at the topmost element without removing it).

Scala provides several ways to implement Stacks, and one efficient way is by using an Array[Int]. Here's how you can create a basic Stack using an Array in Scala:

class Stack(capacity: Int) {
  private var stackArray: Array[Int] = new Array[Int](capacity)
  private var top: Int = -1

  def isEmpty: Boolean = top == -1
}

In this implementation, stackArray is an Array that holds the elements of the stack, and top is an integer that keeps track of the index of the topmost element. The isEmpty method checks if the stack is empty by verifying if top is -1.

In an Array-based Stack, the Push operation adds a new element at the top of the Stack. Here’s how we can write a push function:

def push(data: Int): Unit = {
  if (top < stackArray.length - 1) {
    top += 1
    stackArray(top) = data
  } else {
    println("Stack Overflows")
  }
}

This method checks if there is space in the stack by comparing top with the array's length. If there is space, it increments top and assigns the new element to the top position. If the stack is full, it prints a message indicating an overflow.

The Pop operation removes the topmost element from the Stack.

def pop(): Option[Int] = {
  if (!isEmpty) {
    val topElement = stackArray(top)
    top -= 1
    Some(topElement)
  } else {
    println("Stack Underflows")
    None
  }
}

This method removes and returns the top item of the stack. It checks if the stack is empty using isEmpty. If not, it retrieves the element at the top index, decrements top, and returns the top element wrapped in Some. If the stack is empty, it prints a message and returns None.