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.
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
// 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
TipWhen 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].
