Stacks, queues, deques

Question Click to View Answer

Create a Stack class that can be initialized with an array of items. Add a push method that adds items to the top of the stack and a pop method that removes items from the top of the stack.

A stack is an ordered collection of items. New items are added to the top of the stack and items are removed from the stack starting at the top. This page has an awesome description of stacks.

class Stack
  attr_reader :items

  def initialize(items)
    @items = items
  end

  def push(item)
    items.push(item)
  end

  def pop
    items.pop
  end
end

s = Stack.new(["a", "b", "c"])
s.push("dog")
p s.items
p s.pop # => "dog"
p s.pop # => "c"

Create a reverse method that uses a stack data structure to reverse a string. reverse("duck") should return "kcud".

A Ruby array has push and pop methods and behaves similarly to a stack. This answer uses the split method to create a stack of letters and then reverses the string.

def reverse(str)
  stack = str.split("")
  result = ""
  while !stack.empty?
    result += stack.pop
  end
  result
end

The ( and ) parenthesis need to be balanced in programming language. (5+6)*(7+8)/(4+3) is a valid expression because the parenthesis are properly matched, but ())) is not a valid expression. Write a balanced_parenthesis? that takes a string and returns true/false if the parenthesis are balanced. Use a stack to solve the problem!

balanced_parenthesis?('((()))') should return true

balanced_parenthesis?('(()') should return false

The balanced_parenthesis? method loops through every character in the string. The loop pushes ( characters onto the stack and pops ) characters from the stack. The string is not balanced if the stack is empty when ) should be popped. The string is also not balanced if the stack is not empty after the loop is finished running. This link shows how to solve the problem with Python.

def balanced_parenthesis?(str)
  stack = []
  str.split("").each do |char|
    if char == "("
      stack.push(char)
    elsif char == ")"
      return false if stack.empty?
      stack.pop
    end
  end
  stack.empty?
end

p balanced_parenthesis?('((()))') # true
p balanced_parenthesis?('(()') # false
p balanced_parenthesis?('((((((())') # false
p balanced_parenthesis?('()))') # false
p balanced_parenthesis?('(5+6)*(7+8)/(4+3)') # true

Use the Divide by 2 algorithm to write a divide_by_2 method that converts a decimal number to a binary number. The divide_by_2 method should use a stack to keep track of the digits for the binary result.

The divide_by_2 algorithm adds zero to the stack for even numbers and 1 to the stack for odd numbers. It keeps splitting the number until the integer division returns zero. The stack is then reversed to deduce the answer.

def divide_by_2(num)
  stack = []
  while num > 0
    num.even? ? stack.push(0) : stack.push(1)
    num = num / 2
  end
  stack.map(&:to_s).reverse.join
end

This link has an awesome description and Python solution to the problem.

A queue is an ordered collection of items with a front and a rear. Items are added to the rear of the queue and taken from the front of the queue.

Define a MyQueue class with an enqueue() method to add items to the queue and a dequeue() method to remove items from the queue.

Hint: The string "bob" is at the front of the following queue ["bob", "cat", 99]. 99 is at the rear of the queue.

The MyQueue class will use an array to store the items in the queue. The first element in the array is at the front of the queue and the last element is at the rear of the queue.

class MyQueue

  attr_reader :items

  def initialize(items: [])
    @items = items
  end

  def enqueue(item)
    items.push(item)
  end

  def dequeue
    items.shift
  end

end

queue = MyQueue.new
queue.enqueue("boo")
queue.enqueue("42")
queue.enqueue(true)
queue.dequeue # => "boo"
queue.dequeue # => 42

In the previous question, we defined a MyQueue class with enqueue and dequeue methods. Use the MyQueue class to shift all the element of the following array two spaces to the left: ["hal", "matt", "bob", "sam", "joe"] The desired output is ["bob", "sam", "joe", "hal", "matt"].

The MyQueue class is instantiated and a loop is run twice that dequeues and enqueues an item. When an item is dequeued and enqueued, all the items in the list are shifted one position left.

queue = MyQueue.new(items: ["hal", "matt", "bob", "sam", "joe"])
2.times do
  name = queue.dequeue
  queue.enqueue(name)
end
queue.items # => ["bob", "sam", "joe", "hal", "matt"]

What is a deque?

A deque or double ended queue allows items to be added or removed from the front or the rear of the queue. A deque can behave like a stack, a queue, or both. This link has a great description of deques.

The word "deque" refers to the abstract data type and is pronounced "deck". The word "dequeue" refers to removing items from a queue data structure.

Create a Deque class with an add_rear method to add items to the rear of the queue, a remove_rear method to remove items from the rear of the queue, an add_front method to add items to the front of the queue, and a remove_front method to remove items from the front the queue.

The Deque class can optionally be instantiated with a list of items. The beginning of the items array is the front of the queue and the end of the items array is the rear.

class Deque

  attr_reader :items

  def initialize(items: [])
    @items = items
  end

  def add_rear(item)
    items.push(item)
  end

  def remove_rear
    items.pop
  end

  def add_front(item)
    items.unshift(item)
  end

  def remove_front
    items.shift
  end

end

d = Deque.new
d.add_rear("cool") # items => ["cool"]
d.add_rear("nice") # items => ["cool", "nice"]
d.add_front(44) # items => [44, "cool", "nice"]
d.remove_front # items => ["cool", "nice"]
d.remove_rear # items => ["cool"]

In the previous question, we defined a Deque class with remove_front and remove_rear methods. Use the Deque class to create a palindrome? method that returns true if a string is a palindrome and false otherwise. A palindrome is a string that remains the same when the letters are reversed - "radar" and "level" are good examples.

def palindrome?(deque)
  while deque.items.length > 1
    if deque.remove_front != deque.remove_rear
      return false
    end
  end
  true
end

radar = Deque.new(items: "radar".split(""))
palindrome?(radar) # => true
cat = Deque.new(items: "cat".split(""))
palindrome?(cat) # => false