Stacks

A container of objects that are inserted and removed according to the first-in, last-out principle.

Section Menu

How do I use this section?

1. CHALLENGE

Balanced Brackets

As a software engineer, you'll often be asked to optimize programs. One of the easiest ways to do so is by the introduction of an additional data structure. Here's another classic problem along the same vein. We're provided a string like the following: "{[])}" that is inclusive of the following symbols: parentheses...

2. CHALLENGE

Two Stack Queue

Building a Queue with Two Stacks: A Challenge in Engineering Elegance The Queue with Stacks In this challenge, your task is to implement a queue using two stacks. While many programming languages offer queues through arrays or lists, we're restricting our approach to only utilize stacks. The end result should b...

3. CHALLENGE

Implement a Stack With Minimum

Recall that a stack is an abstract data type modeling a collection of elements. Its primary operations are push (which adds an element to the top of the stack) and pop (which removes the most newest element). Traditionally, a stack can easily be implemented in many dynamic languages using an array (and its built-in methods)....

4. CHALLENGE

Build a Calculator

Let's build a very basic calculator by programming it! You've probably seen one that look similar to this: But we wo...

5. CHALLENGE

Trapping Rain Water

The Trapping Rain Water Challenge: A Deep Dive Imagine you're looking at an elevation map displaying rainfall over a region's landscape. The map consists of bars of varying heights, each representing different elevations. Can you determine the amount of rainwater that this uneven terrain can hold? ![Elevation Map](https://stora...

Cheat Sheet

  • Quick summary: a sequential collection where elements are added to and removed from the same end.
  • Important facts:
    • First-in, last-out (FILO) data structure.
    • Equivalent of a real-life pile of papers on desk.
    • In stack terms, to insert is to push, and to remove is to pop.
    • Often implemented on top of a linked list where the head is used for both insertion and removal. Can also be implemented using dynamic arrays.
  • Pros:
    • Fast insertions and deletions: O(1).
  • Cons:
    • Access and search are O(n).
  • Notable uses:
    • Maintaining undo history.
    • Tracking execution of program functions via a call stack.
    • Reversing order of items.
  • Time complexity (worst case):
    • Access: O(n)
    • Search: O(n)
    • Insertion (pushing): O(1)
    • Deletion (popping): O(1)
  • See also: