# 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
STA rear

full    LDA error1
OUT

dequeue LDA front
SUB rear
BRZ empty
LDA @front
OUT
LDA front
STA front

empty   LDA error2
OUT

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:

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

Did you like this challenge?

Click on a star to rate it!

Average rating 4.8 / 5. Vote count: 18

No votes so far! Be the first to rate this post.

As you found this challenge interesting...

Follow us on social media!

Tagged with: