Arrays as Stacks and Queues
Short Recap
Stacks and queues are abstract data structures that define specific ways to store and access data.
- Stacks follow a Last-In, First-Out (LIFO) order.
- Queues follow a First-In, First-Out (FIFO) order.
Note
Stacks and queues can be implemented using arrays, which provide a fixed-size, efficient way to manage data.
Stacks
- Initialise an array and a variable TOP to track the top element's index.
- Push operation:
- Check if the stack is not full.
- Increment TOP.
- Add the element to the ARRAY[TOP].
- Pop operation:
- Check if the stack is not empty.
- Return ARRAY[TOP].
- Decrement TOP.
- isEmpty operation:
- return top == -1
Example
// Given an array ARRAY of length N (global variables)
TOP = -1 // Another global variable
method push(VALUE) // Define function
if TOP = N - 1 then
output "Stack is full"
return // Stop execution
end if
TOP = TOP + 1 // Increment TOP
ARRAY[TOP] = VALUE // Add new vaue
end method
method pop() // Define function
if TOP = -1 then
output "Stack is empty"
return // Stop execution
end if
VALUE = ARRAY[TOP]
TOP = TOP - 1 // Decrement TOP
return VALUE
end method
method isEmpty()
return TOP = -1 // True if TOP is equal to -1
end method- In this implementation, the top variable starts at -1, indicating an empty stack.
- Each push increments the top, and each pop decrements it.
Linear Queues
Hint
When implementing a queue with an array, use two pointers: FRONT and REAR to track the start and end of the queue.
- Initialise an array and variables FRONT and REAR as 0.
- Enqueue operation:
- Check if the queue is not full.
- Increment REAR.
- Add the element to the ARRAY[REAR].
- Dequeue operation:
- Check if the queue is not empty
- Return ARRAY[FRONT].
- Increment FRONY.
- IsEmpty:
- return FRONT = REAR
Example
- At the beginning, both FRONT and REAR are 0.
- When entering the first element, FRONT remains 0, while REAR becomes 1.
- When entering another element, FRONT again remains 0, while REAR becomes 2.
- When entering yet another element, FRONT remains 0 and REAR becomes 3.
- If we remove an element, FRONT becomes 1 and REAR remains 3.
- If we remove another element, FRONT becomes 2 and REAR remains 3.
- If we remove yet another element, both FRONT and REAR become 0, since the queue is empty.
Example
// Given array ARRAY of length N (global variables)
FRONT = 0
REAR = 0
method enqueue(VALUE)
if REAR = N-1 then
output "Queue is full"
return // Stop execution
end if
REAR = REAR + 1
ARRAY[REAR] = VALUE
end method
method dequeue()
if FRONT = REAR then
output "Queue is empty"
return // Stop execution
end if
VALUE = ARRAY[FRONT]
FRONT = FRONT + 1
return VALUE
end method
method isEmpty()
return FRONT = REAR
end method
Note
A common mistake in array-based queues is not resetting FRONT and REAR, leading to out-of-bounds errors.
Circular Queues
A circular queue solves the problem of unused space in a linear queue by wrapping around the array.
- Initialise an array and variables FRONT and REAR to 0.
- Enqueue:
- Check if the queue is not full (the queue is full when (REAR + 1) mod N = FRONT)
- Increment REAR circularly: REAR = (REAR + 1) mod N.
- Add the element to ARRAY[REAR].
- Dequeue:
- Check if the queue is not empty
- Return ARRAY[FRONT].
- Increment front using (FRONT + 1) % maxSize.
- isEmpty:
- return FRONT = REAR
Example
https://www.youtube.com/embed/CXmg8MRGv_k?si=CI82RGpA4hRuzlBc
Self review
- Try to implement the key operations of a circular queue in an array using pseudocode.
- Try to implement operations of queues and stacks in the programming language of your choice.
