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).
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:
If queue IS NOT FULL:
rearPointer = rearPointer + 1
queue[rearPointer] = value
Algorithm to dequeue a value from a queue:
If queue IS NOT EMPTY:
value = queue[frontPointer]
frontPointer = frontPointer + 1
Low Level Implementation of a queue using LMC:
enqueue LDA max
full LDA error1
dequeue LDA front
empty LDA error2
front DAT 50
rear DAT 50
one DAT 1
max DAT 100
error1 DAT -1
error2 DAT -2
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.
|Test #||Input Values||Expected Output||Pass/Fail?|
|#1||1,10 – 1,11 – 1,12 – 2 – 2 – 2 – 2 – 3|
|#2||1,1 – 1,2 – 1,3 – 2 – 1,4 – 2 – 1,5 – 2 – 3|
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).
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:
If stack IS NOT FULL:
stackPointer = stackPointer + 1
stack[stackPointer] = value
Algorithm to pop a value from a stack:
If stack IS NOT EMPTY:
value = stack[stackPointer]
stackPointer = stackPointer - 1
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.