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).

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:

FUNCTION ENQUEUE(value):
     If queue IS NOT FULL:
            rearPointer = rearPointer + 1
            queue[rearPointer] = value

Algorithm to dequeue a value from a queue:

FUNCTION DEQUEUE():
     If queue IS NOT EMPTY:
            value = queue[frontPointer]
            frontPointer = frontPointer + 1
            RETURN value

Low Level Implementation of a queue using LMC:

menu    INP
        SUB one
        BRZ enqueue 
        SUB one 
        BRZ dequeue
        BRA exit
	
exit    HLT
 
enqueue LDA max
        SUB rear
        BRZ full
        INP
        STA @rear
        LDA rear
        ADD one
        STA rear
        BRA menu

full    LDA error1
        OUT
        BRA menu

dequeue LDA front
        SUB rear
        BRZ empty
        LDA @front
        OUT
        LDA front
        ADD one
        STA front
        BRA menu

empty   LDA error2
        OUT
        BRA menu

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.

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
#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:

FUNCTION PUSH(value):
     If stack IS NOT FULL:
            stackPointer = stackPointer + 1
            stack[stackPointer] = value

Algorithm to pop a value from a stack:

FUNCTION POP():
     If stack IS NOT EMPTY:
            value = stack[stackPointer]
            stackPointer = stackPointer - 1
            RETURN value

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.