Essential Data Structures: Bags, Stacks, Queues, and Big O

Posted on Dec 7, 2025 in Computers

Fundamentals of Data Structures and OOP

Data Structures (DS): Methods for storing and managing data efficiently so it can be reused.

Examples of Data Structures:

  • Lists
  • Queues
  • Trees
  • Bags
  • Dictionaries
  • Graphs

Object-Oriented Programming (OOP) Principles

  • Encapsulation
  • Abstraction
  • Inheritance
  • Polymorphism

Bags: Unordered Collections

A Bag is a finite collection of objects where the order of elements does not matter. Duplicates are allowed.

Examples: Shopping bags, piggy banks.

Core Bag Operations:

  • add
  • remove
  • contains
  • clear
  • getFrequencyOf
  • isEmpty
  • toArray (returns items in the bag as an array)

ArrayBag Implementation

A fixed-size implementation. When an item is removed from the middle, the last item is swapped into the newly empty spot to maintain contiguous storage.

ArrayBag Time Complexity:

  • O(1) Operations: add, remove(unspecified item), isEmpty, getCurrentSize
  • O(n) Operations: remove(specific item), getFrequencyOf, contains, toArray, clear

Resizable Array Bag Implementation

Similar to ArrayBag, but dynamically adjusts size. When the array is full, the add() operation calls a doubleCapacity() helper method to create a new, larger array.

Resizable Array Bag Time Complexity:

  • O(1) Operations: add, remove(unspecified item), isEmpty, getCurrentSize
  • O(n) Operations: remove(specific item, worst case), contains, getFrequencyOf, resize

LinkedBag Implementation

Uses Nodes, where each node holds data and a pointer to the next node. The last node points to null.

  • Adding: Creates a new node and places it at the head of the chain (O(1)).
  • Removing: Removing a specific item requires traversing the list unless it is the first node.

LinkedBag Time Complexity:

  • O(1) Operations: add, remove(unspecified item), isEmpty, getCurrentSize()
  • O(n) Operations: remove(specific item), contains, getFrequency, clear, toArray

Algorithm Efficiency and Big O Notation

Time Efficiency

Measures how much time an algorithm takes to run, based on the number of basic operations performed. It is typically expressed as a function of the size of the input, denoted as n.

Big O Notation

A mathematical method used to describe the upper bounds on an algorithm’s running time, indicating the worst-case performance as the input size grows.

Stacks: Last-In, First-Out (LIFO)

A Stack is a LIFO (Last-In, First-Out) data structure where interaction is only possible with the top element.

Common Uses of Stacks:

  • Managing method calls (pushed onto the program stack and popped when finished).
  • Checking balanced expressions (e.g., parentheses).
  • Converting infix expressions to postfix (e.g., A + B * C → ABC*+).

Core Stack Operations:

  • push (Adds an item to the top)
  • pop (Removes and returns the top item)
  • peek (Returns the top item without removing it)
  • isEmpty
  • clear

ArrayStack Implementation

Uses a fixed-size array where the back of the array represents the top of the stack. This design avoids element shifting during push and pop operations.

Note: If indices 0-2 are filled, the next entry goes to index 3. This implementation cannot be resized.

ArrayStack Time Complexity:

All core operations are O(1), except for clear(), which is O(n).

LinkedStack Implementation

A singly linked structure where each Node holds data and a pointer. The Top of the Stack is always the first Node (the head).

LinkedStack Time Complexity:

All core operations are O(1), except for clear(), which is O(n).

VectorStack (Java)

A built-in Java class that functions as a resizable array implementation for stacks. The back of the vector acts as the top of the stack, ensuring O(1) performance by avoiding shifting.

It throws an EmptyStackException when attempting to operate on an empty stack. It includes the standard stack methods built into the class structure.

Queues: First-In, First-Out (FIFO)

A Queue is a FIFO (First-In, First-Out) data structure, conceptually representing a line. New entries are added to the back, and removals occur at the front.

Examples: Waiting in line, managing stock lots (first shares bought must be the first shares sold).

Core Queue Operations:

  • enqueue (Adds an item to the back)
  • dequeue (Removes and returns the item at the front)
  • getFront (Retrieves the front item, similar to peek)
  • isEmpty
  • clear

ArrayQueue Implementation

Uses a circular array to manage space efficiently. The frontIndex points to the front (where items are removed), and the backIndex points to the back (where items are added).

The index for a new item is calculated using the modulo operator:

newItemIndex = (backIndex + 1) % queue.length

Linked Queue Implementation

Items are added at the back and removed from the front. This structure grows dynamically.

  • firstNode references the front (used for dequeue).
  • lastNode references the back (used for enqueue).

Maintaining a reference to the lastNode is crucial because it allows new entries to be added in O(1) time without traversing the entire list.

Deque: Double-Ended Queue

A Deque (Double-Ended Queue) allows items to be added or removed from both the front and the back. It is neither strictly LIFO nor strictly FIFO.

Core Deque Operations:

  • addToFront
  • addToBack
  • removeFront
  • removeBack
  • getFront
  • getBack
  • isEmpty
  • clear

Examples: Implementing undo/redo functionality, tracking stock lots where shares can be added or removed from either end.