1. Stack

Prerequisite

• Familiar with classes in Lua
• Setup code editor with Lua

Overview

A Stack is a very common data structure used in programming which stores values in last in, first out order (LIFO). Implement a stack as a class in Lua to store arbitrary values of any type.

Recall that classes can be created like:

local Box = {}
Box.__index = Box

function Box.new(x) -- static constructor
  local self = setmetatable({}, Box)
  self.x = x
  return self
end

function Box:Get() -- instance method (note ':')
  return self.x
end

return Box

Tasks

Task 1: Stack class

Create a skeleton Stack class with the constructor and necessary fields. Add a toString method so that the string representation as shown in the examples below could be returned.

For instance:

local stack = Stack.new(3)  -- stack with max size 3
print(stack:toString())     -- should print "[]"

Task 2: Push() and Pop()

Add Push() and Pop() methods to manipulate the stack. Push(x) should push the value of x onto the top of the stack. Pop() should pop the top value off the stack and return it. Also modify the toString() method to correctly display the values in the stack.

For instance:

local stack = Stack.new(3)
stack:Push(1)
stack:Push(2)
print(stack:toString())     -- should print "[1 2]"
local popped = stack:Pop()
print(popped)               -- should print "2"
print(stack:toString())     -- should print "[1]"

Task 3: IsFull() and IsEmpty()

Add IsFull() and IsEmpty() methods which check if the stack is full or empty

For instance:

local stack = Stack.new(1)
stack:Push(1)
print(stack.IsFull())   -- should print "true"
print(stack.IsEmpty())  -- should print "false"

Task 4: Bounds checking

Use the IsFull() and IsEmpty() methods in your code to make sure that Push() and Pop() do not add/remove values innappropriately.

For instance:

local stack = Stack.new(1)
stack:Pop()     -- should print "error: stack empty"
stack:Push(1)
stack:Push(2)   -- should print "error: stack full"

Solution

LuaJava

local Stack = {}
Stack.__index = Stack

function Stack.new(size: number)
    local self = setmetatable({}, Stack)
    self.size = size
    return self
end

function Stack:push(value)
    if self:isFull() then
        print("Stack is full. Cannot push any values.")
        return
    end
    table.insert(self.array, value)
end

function Stack:pop()
    if self:isEmpty() then
        print("Stack is empty. Cannot pop any values.")
        return nil
    end
    return table.remove(self.array)
end

function Stack:peek()
    if #self.array == 0 then
        print("Stack is empty. Cannot peek any values.")
        return nil
    end
    return self.array[#self.array]
end

function Stack:isFull()
    return #self.array == self.size
end

function Stack:isEmpty()
    return #self.array == 0
end

return Stack

public class Stack {
  private int head;
  private Integer[] array;
  private int size;

  public Stack(int size) {
    this.size = size;
    this.head = 0;
    this.array = new Integer[this.size];
  }

  public void push(int x) {
    if (isFull()) {
      System.out.println("Stack is full. Cannot push any values.");
    } else {
      this.array[this.head++] = x;
    }
  }

  public Integer pop() {
    if (isEmpty()) {
      System.out.println("Stack is empty. Cannot pop any values.");
      return null;
    } else {
      return this.array[--this.head];
    }
  }

  public Integer peek() {
    // or just pop push if lazy
    if (isEmpty()) {
      System.out.println("Stack is empty. Cannot peek any values.");
      return null;
    } else {
      Integer res = this.array[--this.head];
      this.head++;
      return res;
    }
  }

  public boolean isFull() {
    return this.size == this.head;
  }

  public boolean isEmpty() {
    return this.head == 0;
  }
}

Extra

Consider what else we can do with stacks? What if we wanted stacks to be of dynamic size? Could be implement stacks more simply just by using tables? How can we use stacks in game development?