from random import randint
import sys
import numpy as np
import time 
import pandas as pd

Stack

Definition

A stack is a linear data structure characterized by its LIFO (Last In, First Out) principle. It is an ordered collection of elements where the addition and removal of elements occur only at one end, known as the top of the stack. The stack follows a strict policy of element insertion and removal through its top, implying that the last element added to the stack is the first to be removed. This structure can be implemented as an abstract data type that provides operations to manipulate its contents.

Usage

Stacks find extensive usage across various domains due to their efficiency and simplicity. They are commonly utilized for solving problems involving reversing or undoing operations. The stack data structure is integral in parsing expressions, implementing recursive algorithms, evaluating postfix expressions, and backtracking through recursive depth-first search algorithms. Furthermore, stacks are fundamental in the implementation of run-time call stacks in programming languages, enabling function calls and their respective return addresses to be stored and managed efficiently. The versatility and utility of the stack data structure make it a fundamental component in algorithm design and analysis.

Sequential stack

Definition

A sequential stack, also known as an array-based stack, is a type of stack implementation that uses an underlying array to store its elements. It maintains a fixed-size array where elements are added and removed from one end, typically the top of the stack. Sequential stacks provide efficient random access to elements and support constant-time insertion and deletion operations. However, the size of a sequential stack is fixed, meaning it cannot dynamically resize to accommodate varying numbers of elements.

Advantages of sequential stacks

  • Efficient random access : Sequential stacks provide efficient random access to elements due to the underlying array representation.
  • Constant-time operations : Insertion and deletion operations in sequential stacks have a constant time complexity, making them efficient.
  • Space efficiency : Sequential stacks have efficient memory utilization as they only require storage for the elements themselves and the fixed-size array.

Disadvantages of sequential stacks

  • Fixed size : Sequential stacks have a fixed size determined during initialization, which means they cannot dynamically resize to accommodate varying numbers of elements. This limitation can lead to stack overflow or underflow if the number of elements exceeds the capacity or if the stack becomes empty.
  • Inefficient resizing : Resizing a sequential stack requires creating a new larger array and copying all elements, resulting in additional time complexity and potential memory allocation issues.
  • Wasteful memory usage : If the stack does not utilize its entire capacity, the memory allocated for the unused portion of the array is wasted.
  • Limited scalability : Due to the fixed-size nature, sequential stacks may not be suitable for applications with unpredictable or varying numbers of elements, as they require upfront determination of the maximum capacity.

Advantages

  • Efficient random access
  • Constant-time operations
  • Space efficiency

Disadvantages

  • Fixed size
  • Inefficient resizing
  • Wasteful memory usage
  • Limited scalability

Linked stack

Definition

A linked stack, also referred to as a linked list-based stack, is a type of stack implementation that uses a linked list to store its elements. It is composed of nodes where each node contains an element and a reference to the next node. The top of the stack is represented by the first node in the linked list. Linked stacks provide flexibility in terms of size as they can dynamically grow or shrink to accommodate elements. Insertion and deletion operations are efficient, requiring only the manipulation of the linked list’s pointers. Linked stacks allow for efficient memory utilization, but they may incur additional overhead due to the storage of node references.

Advantages of Linked Stack:

  • Dynamic size : Linked stack allows for a dynamic size, as elements can be added or removed easily without any need for resizing or shifting of elements.
  • Efficient memory utilization : Linked stack optimizes memory utilization as it only allocates memory for the elements actually stored in the stack, unlike an array-based stack which requires a fixed size allocation.
  • Ease of implementation : Implementing a linked stack is relatively straightforward, requiring minimal coding and no need for complex resizing strategies.
  • Flexibility : Linked stack allows for easy implementation of additional operations such as copying or merging stacks, which can be useful in various applications.

Disadvantages of Linked Stack:

  • Overhead of pointers : Each element in a linked stack requires additional memory space for storing pointers, which can result in increased overhead when compared to an array-based stack.
  • Slower access times : Accessing an element in a linked stack requires traversing through the nodes, leading to slower access times compared to direct indexing in an array-based stack.
  • Extra memory overhead : Linked stack utilizes additional memory to store the pointers, which can result in higher memory overhead compared to the actual data being stored.
  • Potential for memory fragmentation : If elements are frequently added and removed from a linked stack, it can lead to memory fragmentation over time, which may cause inefficient memory usage.

Advantages

  • Dynamic size
  • Efficient memory utilization
  • Ease of implementation
  • Flexibility

Disadvantages

  • Overhead of pointers
  • Slower access times
  • Extra memory overhead
  • Potential for memory fragmentation