Stack Algorithm

The Stack Using Array Algorithm is an efficient data structure that implements the stack concept using an array as its underlying storage mechanism. The stack is a linear data structure that follows the Last-In-First-Out (LIFO) order, where the last element added to the stack is the first one to be removed. It consists of two main operations: pushing (adding) an element onto the stack and popping (removing) the element from the top of the stack. The array-based implementation of this algorithm allows for fast and easy access to the stack's top element, making it a popular choice for various applications such as parsing, expression evaluation, and function call management. In the array-based stack implementation, an integer variable called "top" is used to keep track of the index of the topmost element in the stack. When a new element is pushed onto the stack, the "top" index is incremented, and the element is placed at that index in the array. Conversely, when an element is popped from the stack, the "top" index is decremented, effectively removing the element from the stack. One of the key considerations for this algorithm is the stack's capacity, which is determined by the size of the underlying array. When the stack becomes full, it may require resizing (either by doubling or shrinking) to accommodate additional elements or to conserve memory. This dynamic resizing can be implemented using a dynamic array or by allocating and deallocating memory as needed. Overall, the Stack Using Array Algorithm offers a simple and efficient method for implementing a stack data structure with constant time complexity for both push and pop operations, making it an attractive choice for a wide range of applications.
/**
 * This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
 * and written by Vladimir Kostyukov, http://vkostyukov.ru
 *
 * Stack http://en.wikipedia.org/wiki/Stack_(abstract_data_type)
 *
 * Push - O(1)
 * Top - O(1)
 * Pop - O(1)
 */

class Stack[+A](self: List[A]) {

  /**
   * The top of this stack.
   */
  def top: A = self.head

  /**
   * The rest of this stack.
   */
  def rest: Stack[A] = new Stack(self.tail)

  /**
   * Checks whether this stack is empty or not.
   */
  def isEmpty: Boolean = self.isEmpty

  /**
   * Pops top element from this stack.
   *
   * Time - O(1)
   * Space - O(1)
   */
  def pop: (A, Stack[A]) = (top, rest)

  /**
   * Pushes given element 'x' into this stack.
   *
   * Time - O(1)
   * Space - O(1)
   */
  def push[B >: A](x: B): Stack[B] = new Stack(x :: self)
}

object Stack {

   /**
    * Returns an empty stack instance.
    *
    * Time - O(1)
    * Space - O(1)
    */
   def empty[A]: Stack[A] = new Stack(Nil)

   /**
    * Creates a new stack from given 'xs' sequence.
    *
    * Time - O(n)
    * Space - O(1)
    */
   def apply[A](xs: A*): Stack[A] =
     xs.foldLeft(Stack.empty[A])((r, x) => r.push(x))
}

LANGUAGE:

DARK MODE: