Stacks and Queues in LMC

In this post we will investigate how to implement a queue and a stack data structure using low-level programming. We will use an upgraded version of Little Man Computer (LMC) that supports indirect addressing to to do.

Implementing a Queue in LMC


A queue is a FIFO data structure: First-In First-Out in other words, it is used to implement a first come first served approach. An item that is added (enqueue) at the end of a queue will be the last one to be accessed (dequeue).

queue-diagram

Two pointers are needed to implement a queue data structure: A front pointer which holds the memory address of the first item of the queue and a rear pointer which holds the memory address of the last item of the queue.

When implementing a Queue data structure we need to implement two algorithms/functions to enqueue a new value at the end of the queue and to dequeue a value from the front of the queue.

Algorithm to enqueue a value to a queue:

Algorithm to dequeue a value from a queue:

Low Level Implementation of a queue using LMC:

The above algorithm works as follows:

  • The user needs to input one of the following three menu options:
    • 1: To enqueue a new value,
    • 2: To dequeue a value,
    • Any other value: To exit the program.
  • If the user opts for option 1, they will then need to input the value to enqueue. They will then be redirected to the start of the program to input their next option from the menu. If the queue is full, the program will output the error code -1. The queue will be stored in memory starting at memory location 50. The queue will be full once it reaches memory location 99.
  • If the user opts for option 2, a value will be removed from the queue and displayed as an output. They will then be redirected to the start of the program to input their next option from the menu. If the queue is empty, the program will output the error code -2.
  • The program will stop if the user selects a value different from 1 or 2 from the menu.

Direct vs indirect addressing:
The LMC language was initially implemented to only support direct addressing: Each operand is a memory location of where the data to be used is stored. However to access the value stored at the front (dequeue) or rear (enqueue) memory locations of the queue it is necessary to use indirect addressing. The above code will hence only work with an LMC simulator that supports indirect addressing. In the code above the @ sign is used to indicate when indirect addressing is used. The following page gives more explanations of the main memory address modes used in low-level languages.

You can try code provided above in our LMC simulator as it does support indirect addressing:
LMC SimulatorOpen in New Window

Test Plan:

Test # Input Values Expected Output Pass/Fail?
#1 1,10 – 1,11 – 1,12 – 2 – 2 – 2 – 2 – 3 LMC-Queue-Test-2
#2 1,1 – 1,2 – 1,3 – 2 – 1,4 – 2 – 1,5 – 2 – 3 LMC-Queue-Test-1

Implementing a Stack in LMC


A stack is a FILO data structure: First-In Last-Out. Imagine a stack of books piled up on a table. When you add (push) a book on top of the pile, it will be the first book that you will then take (pop) from the pile (stack).

stack-diagram

Only one pointer is needed to implement a stack data structure: An End of Stack pointer which holds the memory address of the last item of the stack.

When implementing a Stack data structure we need to implement two algorithms/functions to push a new value at the end of the stack and to pop a value from the end of the stack.

Algorithm to push a value to a stack:

Algorithm to pop a value from a stack:

Your Challenge:
Your challenge is to adapt the code given to implement a queue in order to implement a stack instead. You will need to apply the right terminology (push and pop instead of enqueue and dequeue) and apply the above two algorithms in LMC.

Share Button
Tagged with: