Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 134 ยท Collections

Stacks, Queues and Other Structures

Build stacks, queues, priority queues and linked lists in Ruby - Array as stack and queue, Queue and SizedQueue, a binary heap and a hand-written list - with runnable examples.

Ruby has no separate Stack class and no Deque class. It does not need them, because the humble Array already behaves like both. That surprises people coming from Java or C++, where you pick a specialised container for every job. In Ruby you pick a behaviour: last in, first out (a stack); first in, first out (a queue); smallest first (a priority queue); or cheap insertion in the middle (a linked list), and then choose the simplest tool that provides it.

This lesson shows each structure with runnable code: arrays as stacks and queues, the core Queue and SizedQueue classes (built for threads, but usable anywhere), a priority queue written as a binary heap, and a singly linked list. Along the way you will see what each operation costs, because the choice of structure is really a choice about speed. You should be comfortable with Arrays and Classes and Objects.

A stack with an Array

A stack hands things back in the reverse order you gave them, like a pile of plates: you add to the top and remove from the top. An array does this with push (or <<) and pop, both of which work at the end and are fast, no matter how long the array is.

Ruby Undo history as a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

pop on an empty array returns nil rather than raising an error, as the final p history.pop shows. last (or peek in other languages) looks at the top without removing it. Stacks appear everywhere: undo/redo, the call stack itself, depth-first search, and checking that brackets match.

Ruby Balanced brackets with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Every opening bracket is pushed. Every closing bracket must match whatever sits on top. A mismatch, a closing bracket with nothing open (pop gives nil, which never equals a bracket), or leftovers at the end all mean "not balanced".

A queue with an Array

A queue is first in, first out, like people waiting in a line. With an array you add to the back with push and remove from the front with shift.

Ruby A waiting line using push and shift

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

shift removes from the front, unshift adds to the front, and shift(n) removes several at once. In Ruby, shift on an array is O(1) amortized: the interpreter shares the underlying memory and just moves a start marker instead of copying all remaining elements. unshift and insert near the front are not as cheap in the general case. So for ordinary queues of any size, an array is a perfectly good choice.

An array with push/pop/shift/unshift is therefore a deque (double-ended queue) as well. The names to remember: push and pop work at the end, shift and unshift at the front.

Queue and SizedQueue

Core Ruby also ships a Queue class (it is Thread::Queue, available without any require). It has the same first-in, first-out behaviour but is thread-safe, which means several threads can add and remove at once without corrupting it. That makes it the standard building block for producer/consumer programs (see Mutex, Queue and ConditionVariable). You can use it in a single thread too.

Ruby Queue basics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

<<, push and enq are synonyms for adding; pop, shift and deq are synonyms for taking. Calling close says "no more items will arrive". After closing, the remaining items can still be taken, and then pop returns nil instead of waiting. That is the clean signal a worker thread uses to know it can stop.

What if you pop from an empty queue? Normally pop waits for another thread to add something. With no other thread alive, waiting could never end, and Ruby detects that. Passing true (non-blocking) makes it fail immediately instead:

Ruby Popping an empty queue without waiting (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The result is main.rb:3:in 'Thread::Queue#pop': queue empty (ThreadError). A plain jobs.pop here would instead stop the program with No live threads left. Deadlock? (fatal), which is Ruby's deadlock detection (with a second thread alive, it would simply wait). You can also write jobs.pop(timeout: 1) to wait at most a second and get nil on timeout.

SizedQueue adds a maximum size. When it is full, push waits until a consumer makes room, which gives you back-pressure: a fast producer cannot flood a slow consumer.

Ruby A bounded queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

With true as the second argument, push is non-blocking and raises ThreadError ("queue full") when there is no room; without it, the call would wait for a consumer.

A priority queue by hand

Sometimes "first in" is the wrong rule and you want "most important first": the next job with the nearest deadline, the shortest path to explore next. Ruby has no built-in priority queue, but a binary heap makes one in about twenty lines. A heap is an array where the item at index i has its children at 2i + 1 and 2i + 2, and every parent is less than or equal to its children. The smallest item is therefore always at index 0.

Ruby A min-heap priority queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

push adds at the end and lets the item sift up while it is smaller than its parent. pop takes the root, moves the last item to the root and lets it sift down. Both touch at most one item per level of the tree, so they cost O(log n), against O(n) for keeping a sorted array with repeated inserts. The optional block makes the ordering configurable: pass a comparison for a max-heap or for hashes like the tasks above. This is exactly the structure behind Dijkstra's algorithm and event schedulers.

A linked list by hand

In a linked list each element (a node) holds a value and a reference to the next node. Inserting or removing at a known position needs no shifting, which is why textbooks love them. In practice Ruby arrays beat linked lists for almost everything, but writing one is a good exercise in objects and in Enumerable.

Ruby A singly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

By defining only each and mixing in Enumerable you get map, select, include?, first, sort, sum and dozens more for free (see The Enumerable Module). Notice the cost: append must walk the whole list to find the tail (O(n)), whereas prepend is O(1). Adding a @tail reference would make append O(1) as well.

Which one should you use?

Need Use Cost
Stack Array with push / pop O(1)
Simple queue or deque Array with push / shift / unshift O(1) amortized for shift
Queue shared between threads Queue O(1), thread-safe
Bounded buffer between threads SizedQueue blocks when full
Smallest or largest first binary heap (written by hand, or a gem) O(log n)
Fast removal in the middle linked list (rarely worth it) O(1) given the node

A common mistake is reaching for Queue in single-threaded code "because it is a queue". It adds locking you do not need, and its pop can freeze the program waiting. In a single thread an array is simpler, and you can inspect it with p.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which pair of Array methods makes a stack?

    push adds at the end and pop removes from the end, so the last item added is the first removed.
  2. 2. What does [].pop return?

    pop on an empty array returns nil. Check empty? first if nil could be a stored value.
  3. 3. What happens when you call Queue.new.pop(true)?

    The true argument means non-blocking, so an empty queue raises ThreadError immediately. Without it, pop waits for another thread to add an item.
  4. 4. Why use SizedQueue instead of Queue in a producer/consumer program?

    A full SizedQueue makes push wait, which gives back-pressure. Queue grows without limit.
  5. 5. In the binary heap, why does pop cost O(log n)?

    The tree has about log2 n levels, and sifting down moves the item at most one level per step.

Summary

  • An Array is a stack with push/pop and a queue (or deque) with push/shift/unshift; all are cheap.
  • pop on an empty array returns nil; check empty? when nil could be real data.
  • Queue and SizedQueue are thread-safe; pop(true) raises ThreadError instead of waiting, close signals the end, and SizedQueue adds back-pressure.
  • Ruby has no built-in priority queue; a binary heap gives O(log n) push and pop.
  • A linked list is easy to write with a Struct node and Enumerable, but arrays are the better default.
  • Choose the structure by the behaviour you need, then by cost.

Next: Classes and Objects