Data Structures

Stack Data Structure Getting Started

A stack is a linear data structure that mimics real-life stacks such as a stack of physical disks. Stacks are useful to process the data in the Last In First Out (LIFO) order.

1. Concepts of Stack Data Structure

Stacks have only one end for both insertions and deletions. So, the stack always removes the last element inserted. This is known as Last In First Out (LIFO) or First In Last Out (FILO).

Stack Data Structure Representation
Stack Data Structure Representation

Properties of Stack

  • Top: The top of the stack
  • Element: The actual data
  • Push: A new element is inserted on Top of the stack
  • Pop: Element is removed from the Top of the stack
  • Underflow: Stack is empty, but requested for pop
  • Overflow: Stack reaches its capacity, but requested for push (applicable only for the array-based implementation of the stack)

2. Operations and Time Complexity of Stack

Basically, the insertion and deletion in the stack are called Push and pop respectively. The following are the Stack operations with time and space complexities.

OperationShort DescriptionTime
Complexity
(worst)
Space
Complexity
(worst)
PushInsert a new element on topO(1)O(n)
PopDelete the element from the topO(1)O(n)
SearchSearch the element by valueO(n)O(n)
Time and Space complexity of Stack operations

Stack always performs the operations on Top, so the Push and Pop operations work faster in O(1) time. The search operation takes O(n) time, so they are not intended for the stack.

3. Implementation of Stack Data Structure

Stacks can be implemented both using Array and Linked List. However, we can choose the right implementation based on static or dynamic data.

3.1. Array implementation of Stack

Array implementation of Stack is static and limited by the array size. The stack can not store elements beyond its capacity. But, arrays work faster for push and pop operations because of the continuous memory. So, use the array-based implementation for the fixed amount of data.

Stack implementation using Array with C++ example

3.2. Linked List implementation of Stack

Linked List implementation of Stack is dynamic in size. It can grow and shrink based on dynamic data. However, the push and pop operations are slower than the array, because it requires memory allocation and deallocation. So, use the linked list based implementation only for the dynamic data.

Stack implementation using Linked List with C++ example

3.3. Array vs Linked List implementation of Stack

Look at the table to know the difference between Array and Linked list implementation of Stack.

Stack using ArrayStack using Linked List
Static sizeDynamic size grows at runtime
Suitable for static dataSuitable for dynamic data
Faster push and pop operations. Because of its continuous memory locations which are cache friendly for the CPU.Bit slower due to runtime allocations. Also, the data is not stored in continuous memory locations.
Memory is not effectively used. Because an array requires predefined memory which is not fully utilized.Effective usage of the memory as it creates the node only when required.
No additional memory is required for bookkeepingAdditional memory is required to store the links.
Array vs Linked List for Stack Implementation

4. Applications of Stack Data Structure

4.1. When to use the Stack?

Stacks are useful for Applications that process the data in the Last In First Out (LIFO) order. Specifically, processing nested structures such as recursive operations. For example,

  • Reversing a string – Recursively push all the characters on Stack. Finally, pop all the characters that result in reverse order.
  • Balanced parenthesis – Matching open and closing braces in an expression.
  • Backtracking – Remember certain states when you navigate and use them to go back to the previous states.
  • Tree or graph traversals – Use stack to remember the path of traversal and to return back.

The stack data structure cannot be used for sequential First In First Out (FIFO) operations. Alternatively, use Queue Data Structure for FIFO operations.

4.2. Realtime Applications of Stack

  • Stack memory allocation for programming – Allocates stack memory when you call a function and cleans when you return back.
  • The compiler uses the stack to convert arithmetic expressions to either Prefix or Postfix form.
  • Redo/Undo operations.
  • Backward navigations.
  • Tower of Hanoi.
  • Stock span problem.
  • Histogram problem.
  • Graph algorithms like topological sorting and strongly connected components.

4.2. Advantages and Disadvantages of Stack

4.2.1. Pros

  • Faster insertion and deletion operations in O(1) time.
  • Requires additional memory to store the pointer in Linked List Implementation.

4.2.2. Cons

  • Searching on the stack is slower and takes O(n) time.
  • Not suitable for sequential First In First Out (FIFO) operations.
  • Memory space is not effectively used in Array Implementation.
Copyright copyright 2024 Simplerize