Stack Basics

excerpt: This covers the push, pop and using stacks to reverse an array. tags: sentinel linked-list-traversal

A stack is a data structure where objects are added and removed in last-in-first-out order. They are sometimes called LIFOs. They expand as needed to hold more items just like linked lists. It is often used to store objects for later processing by other algorithms such as shortest-path network algorithms.

It is similar to a pile of books or plates, we cannot remove the item in the middle without making them collapse. The push operation adds an object to a stack. The pop operation removes an object from a stack.

Push Operation

The stack can be implemented using a linked list. The push method adds a new node to the top of the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

require_relative 'node'

class Stack
  def push(sentinel, value)
    # make a new node to store the value
    node = Node.new(value)
    
    # add the new node to the linked list
    node.link = sentinel.link
    sentinel.link = node
  end
end

The code for testing the implementation of the push method consists of the following classes. The node.rb:

1
2
3
4
5
6
7
8
9

class Node
  attr_reader :value
  attr_accessor :link
  
  def initialize(value, link=nil)
    @value = value
    @link = link
  end
end

The linked_list.rb:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

require_relative 'node'

class LinkedList
  def initialize(head)
    @head = head
  end
  
  def traverse
    current = @head

    while current
      p current.value
      current = current.link
    end
  end
    
end

The tester.rb:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

require_relative 'linked_list'
require_relative 'node'
require_relative 'stack'

# Create the linked list
last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

stack = Stack.new
stack.push(sentinel, 1)

list.traverse

Pop Operation

The pop method removes the top node from the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def pop(sentinel)
  if sentinel.link.nil?
    raise 'Cannot pop empty stack'
  end
  
  # the top node's value
  data = sentinel.link.value
  
  # remove the top node from the linked list
  sentinel.link = sentinel.link.link
  
  return data
end

The tester.rb can test the implementation:

1
2

stack.pop(sentinel)
list.traverse

The push and pop operations both have O(1) run times. The list does not require any extra space aside from the links between the nodes. So the linked lists are also space-efficient.

Array Stacks

A stack can also be implemented using an Array. The space for the array must be allocated to hold the number of items we expect to put in the stack. The constructor initializes the size of the array. The array_stack.rb is implemented as shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class ArrayStack
  def initialize(size)
    @size = size
  end
  
  def push(values, next_index, new_value)
    if next_index == @size
      raise 'Out of space'
    end
    
    # Add the new item
    values[next_index] = new_value
  end
end

The push method implementation can be tested by:

1
2
3
4
5
6

array = [1,4,8,5]

stack = ArrayStack.new(10)
stack.push(array, array.size, 9)

p array

The pop method can be implemented as shown below:

1
2
3
4
5
6
7

def pop(values)
  if values.size == 0
    raise 'Cannot pop an empty stack'
  end
  
  values.pop
end

The pop method can be tested by:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

array = [1,4,8,5]

stack = ArrayStack.new(10)
stack.push(array, array.size, 9)

p array

stack.pop(array)

p array

The array based stack has O(1) time complexity for adding and removing an item. The array based stack does not need any memory for storing links between nodes. However, it requires extra space to hold new items. If the array needs to be resized for holding more items than the initial allocation of array size, it will take O(N) time to copy the new items into a newly resized array.

Reversing an Array

The shortest path algorithms can use stacks. The reversing of an array is simple with a stack. First push every item onto the stack and then pop every item from the stack. The LIFO nature of the stack reverses the order of the items.

A stack makes it simple to reverse an array. Push each item onto the stack and pop it back off. The LIFO nature of the stack takes the item out in reverse order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

values = [2,5,7,3]

reverse = []
stack = []

for i in (0...values.size)
  stack.push(values[i])  
end

p stack

for i in (0...values.size)
  reverse << stack.pop
end

p reverse

The loop traverses the values array and saves all the elements in a stack. The pop operation removes all the elements from the array and saves it in the reverse array.

Display Linked List Backwards

Stack is useful to display a linked list backwards. The forward traversal of linked list saves all the nodes in the stack. The stack is then used to access the nodes and prints its value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def display_backwards(head)
  stack = []
  
  current = head
  while current
    stack << current  
    current = current.next
  end
  
  while !stack.empty?
    current = stack.pop
    p current.val
  end
end