Stacks

Time Complexity			Space Complexity
Access	Search	Insert / Delete	O(n)
O(1)	O(n)	O(1)

A “stack” is like an array, but implemented in a “stack” fashion. I.e. elements are typically only accessed one by one, in the opposite order from when they were inserted.

For example, say you had homework due in all your classes. In an effort to save time, you want to do all of the homework by the end of the day. You take out textbooks in genetics, physics, psychology, and then biology.

Being the efficient student you are, you don’t want to move the books around more than needed, so you only take textbooks from the top. Notice this gives us the opposite order from what we started with; biology, psychology, physics, and then genetics. This is the defining characteristic of a stack - you may see this referred to as a LIFO structure, standing for “Last In First Out”, meaning the last object added will be the first object removed.

Uses you might be familiar with include the “undo” button on most programs and the back button on a web browser. This structure can come up in various programming problems where order matters.

C++

C#

Java

JavaScript

Python

Swift

#include <iostream>
#include <stack>
using namespace std;

int main() {
  // Declaration
  stack<int> numStack;

  // Add values
  numStack.push(1);
  numStack.push(2);
  numStack.push(3);
  numStack.push(4);

  // Check top of stack
  cout << "Top: " << numStack.top() << endl;

  // Remove top value (pop), does not return the value
  cout << "Removing top value... " << endl;
  numStack.pop();

  // Get size
  cout << "Size: " << numStack.size() << endl;

  // Check if stack is empty
  cout << boolalpha;
  cout << "Stack is empty: " << numStack.empty() << endl;

  // Iterate through stack
  while(!numStack.empty()){
    cout << numStack.top() << endl;
    numStack.pop();
  }
}

using System.Collections;
class Program {
  static void Main(string[] args) {
    // Declaration
    Stack numStack = new Stack();

    // Add values
    numStack.Push(1);
    numStack.Push(2);
    numStack.Push(3);
    numStack.Push(4);

    // Check top of stack
    System.Console.WriteLine("Top: " + numStack.Peek());

    // Remove top value (pop), also returns the value
    System.Console.WriteLine("Removing top value... ");
    numStack.Pop();

    // Get size
    System.Console.WriteLine( "Size: " + numStack.Count);

    // Check if stack is empty
    System.Console.WriteLine( "Stack is empty: " + (numStack.Count == 0));

    // Iterate through stack
    while(numStack.Count != 0)
      System.Console.WriteLine(numStack.Pop());
  }
}

import java.util.*;
public class stacks {
  public static void main(String[] args) {
    // Declaration
    Stack<Integer> numStack = new Stack<Integer>();

    // Add values
    numStack.push(1);
    numStack.push(2);
    numStack.push(3);
    numStack.push(4);

    // Check top of stack
    System.out.println("Top: " + numStack.peek());

    // Remove top value (pop), also returns the value
    System.out.println("Removing top value... ");
    numStack.pop();

    // Get size
    System.out.println("Size: " + numStack.size());

    // Check if stack is empty
    System.out.println("Stack is empty: " + (numStack.empty()));

    // Iterate through stack
    while(!numStack.empty())
      System.out.println(numStack.pop());
  }
}

// Declaration
var numStack = [];

// Add values
numStack.push(1);
numStack.push(2);
numStack.push(3);
numStack.push(4);

// Check top of stack
console.log("Top: " + numStack[numStack.length - 1]);

// Remove top value (pop), also returns the value
console.log("Removing top value... ");
numStack.pop();

// Get size
console.log("Size: " + numStack.length);

// Check if stack is empty
console.log("Stack is empty: " + (numStack.length === 0));

// Iterate through stack
while(numStack.length !== 0)
  console.log(numStack.pop());

# Declaration
numStack = []

# Add values
numStack.append(1)
numStack.append(2)
numStack.append(3)
numStack.append(4)

# Check top of stack
print("Top: " + str(numStack[-1]))

# Remove top value (pop), also returns the value
print("Removing top value... ")
numStack.pop()

# Get size
print("Size: " + str((len(numStack))) )

# Check if stack is empty
print("Stack is empty: " + str(not numStack) )

# Iterate through stack
while numStack:
  print(numStack.pop())

// Declaration
var numStack = [Int]()

// Add values
numStack += [1]
numStack += [2]
numStack += [3]
numStack += [4]

// Check top of stack
print("Top: \(numStack.last!)")

// Remove top value, also returns the value
print("Removing top value... ")
numStack.removeLast()

// Get size
print("Size: \(numStack.count)")

// Check if stack is empty
print("Stack is empty: \(numStack.isEmpty)")

// Iterate through stack
while(!numStack.isEmpty){
  print(numStack.removeLast())
}

Notes

C++

C#

Java

JavaScript

Python

Swift

The line #include <stack> is needed to use the standard library’s stack type.

Unlike most other languages, the stack.pop() function in C++ doesn’t return the element removed from the stack. This just means stack.top() should also be used to access the element if needed, before stack.pop().

The Stack structure is under System.Collections, so the line using System.Collections; is used for compactness.

The line import java.util.*; is needed to use the Stack type.

There is no standard stack type in JavaScript. Instead, the normal array type can be used, as it has similar functions for what is needed from a stack type, such as stack.push() and stack.pop(). As a result, everything from the page Preferred Arrays is also valid here.

There is no standard stack type in Python. Instead, the normal array type can be used, as it has similar functions for what is needed from a stack type, such as stack.append() and stack.pop(). As a result, everything from the page Preferred Arrays is also valid here.

The syntax array[-n] can be used to get the “nth to last” element of an array in Python. This method is typically preferred in python.

The syntax not array can be used to find out whether the array is empty. This has to do with how arrays are implemented in python, specifically that they will return false as a boolean if they are empty.

There is no standard stack type in Swift. Instead, the normal array type can be used, as it has similar functions for what is needed from a stack type, such as the += operator to add elements and stack.removeLast() to get the top element. As a result, everything from the page Preferred Arrays is also valid here.

When accessing array variables through code like stack.last, swift will return an optional type. Because we can assume it exists here, using the ! operator after the variable gives us the Int type we are expecting.

To insert a variable into a string to do things like log variables, the syntax words \(yourVar) more words is used, where yourVar is your variable and the entire string is enclosed in quotation marks.