Queues

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

A “queue” (that’s ‘q’, followed by two “ue”s) is like an array, but implemented in a “queue” or “line” fashion. I.e. elements are typically only accessed one by one, in the order they were inserted.

For example, say you get in line at a theater and there are five people ahead of you. Five people, starting with the first person in line, then the second, and so on, all got there before you.

It’s only fair that everyone gets their tickets in the order they came in; the first person, second person, and so on up to you. You may see this referred to as a FIFO structure, standing for “First In First Out”, meaning the first object added will be the first object removed.

Uses you might be familiar with include download queues and music playlists. This structure can come up in various programming problems where order matters.

C++

C#

Java

JavaScript

Python

Swift

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

int main() {
  // Declaration
  queue<int> numQueue;

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

  // Check front of queue
  cout << "Front: " << numQueue.front() << endl;

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

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

  // Check if queue is empty
  cout << boolalpha;
  cout << "Queue is empty: " << numQueue.empty() << endl;

  // Iterate through queue
  while(!numQueue.empty()){
    cout << numQueue.front() << endl;
    numQueue.pop();
  }
}

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

    // Add values
    numQueue.Enqueue(1);
    numQueue.Enqueue(2);
    numQueue.Enqueue(3);
    numQueue.Enqueue(4);

    // Check front of queue
    System.Console.WriteLine("Front: " + numQueue.Peek());

    // Remove front value (dequeue), also returns the value
    System.Console.WriteLine("Removing front value... ");
    numQueue.Dequeue();

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

    // Check if queue is empty
    System.Console.WriteLine( "Queue is empty: " + (numQueue.Count == 0));

    // Iterate through queue
    while(numQueue.Count != 0)
      System.Console.WriteLine(numQueue.Dequeue());
  }
}

import java.util.*;
public class queues {
  public static void main(String[] args) {
    // Declaration
    Queue<Integer> numQueue = new LinkedList<Integer>();

    // Add values
    numQueue.add(1);
    numQueue.add(2);
    numQueue.add(3);
    numQueue.add(4);

    // Check front of queue
    System.out.println("Front: " + numQueue.peek());

    // Remove front value (remove), also returns the value
    System.out.println("Removing front value... ");
    numQueue.remove();

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

    // Check if queue is empty
    System.out.println("Queue is empty: " + (numQueue.isEmpty()));

    // Iterate through queue
    while(!numQueue.isEmpty())
      System.out.println(numQueue.remove());
  }
}

// Declaration
var numQueue = [];

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

// Check front of queue
console.log("Front: " + numQueue[0]);

// Remove front value (shift), also returns the value
console.log("Removing front value... ");
numQueue.shift();

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

// Check if queue is empty
console.log("Queue is empty: " + (numQueue.length === 0));

// Iterate through queue
while(numQueue.length !== 0)
  console.log(numQueue.shift());

# Declaration
numQueue = []

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

# Check front of queue
print("Front: " + str(numQueue[0]))

# Remove front value (pop), also returns the value
print("Removing front value... ")
numQueue.pop(0)

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

# Check if queue is empty
print("Queue is empty: " + str(not numQueue) )

# Iterate through queue
while numQueue:
  print(numQueue.pop(0))

// Declaration
var numQueue = [Int]()

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

// Check front of queue
print("Front: \(numQueue.first!)")

// Remove front value, also returns the value
print("Removing front value... ")
numQueue.removeFirst()

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

// Check if queue is empty
print("Queue is empty: \(numQueue.isEmpty)")

// Iterate through queue
while(!numQueue.isEmpty){
  print(numQueue.removeFirst())
}

Notes

C++

C#

Java

JavaScript

Python

Swift

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

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

The Queue 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 Queue type. However, in Java, Queue is just an interface. An implementation such as LinkedList (used here) is needed. Linked lists, as a structure, will have its own page here in the future. There is also the PriorityQueue implementation, compatible with the Queue interface.

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

Technically, shift() operates in O(n) time, however it shouldn’t make a difference practically if the number of elements isn’t in the hundreds of thousands, which shouldn’t be happening on a browser anyways.

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

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 queue type in Swift. Instead, the normal array type can be used, as it has similar functions for what is needed from a queue type, such as the += operator to add elements and queue.removeFirst() to get the front element. As a result, everything from the page Preferred Arrays is also valid here.

When accessing array variables through code like queue.first, 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.