I just got this question from a textbook exercise saying
"Stack and Queue ADT's can be implemented using array. Which one is simpler to implement using an array? Explain"
I think using an array is probably not the best way to implement both a stack and queue in the first place because of the fixed space in an array, unless it is resized after each overflow of item.
I do not have a perfect response to this but which one of them is simpler to implement using arrays?
The only difference that I can think of is that with a stack, you only have to keep track of the front of the stack in the array, while with a queue you will need of keep track of both the front and end of the queue.
"Keep track of" means "storing an array index/offset for".
Other than that, the standard operations on stacks and queues are fairly similar in number; push(), pop() for stacks, and enqueue(), dequeue() for queues, and neither data type is particularly complex or difficult to implement.
A stack would be better implemented as an array compared to a queue, mainly because of how the types of operations affect the array itself.
For a queue data structure, you need to be able to remove elements from one end and push elements into the other. When you have an array, adding or removing an element from the front of the array is relatively bad because it involves you having to shift every other element to accommodate the new one.
queue: [2, 3, 4, 5, 6]
enqueue: 1
queue: [1, 2, 3, 4, 5, 6] (every element had to shift to fit 1 in the front)
or if you oriented your queue the opposite way,
queue: [1, 2, 3, 4, 5, 6]
dequeue: 1
queue: [2, 3, 4, 5, 6] (every element had to shift when 1 was removed from the front)
So no matter which direction you orient your queue, you will always have some operation (enqueue or dequeue) which involves adding/removing an element from the front of the array, which in turn causes every other element to shift which is relatively inefficient (would be great to avoid, and is why most queues aren't implemented with an array).
With a stack data structure, you only need to add and remove elements from the same end. This allows us to avoid the problem we were having with adding/removing elements from the front of the array. We just need to orient our stack to add and remove elements from the back of the array, and we will not encounter the problem with having to shift all the elements when something is added or removed.
stack: [1, 2, 3, 4]
push: 5
stack: [1, 2, 3, 4, 5] (nothing had to be shifted)
pop:
stack: [1, 2, 3, 4] (nothing had to be shifted)
Yes, It is obvious that array is not the best to implement queue or stack in data structure for real life problems.
I think, Implementation of a stack is always easier than the implementation of a queue because in stack we just have to push the element on the highest index and pop the same element from the same index. And if we want to push another element than we will push it on the same index. Every operation performs on the same index.
But in the case of a queue, there are two indices to trace one from which we have to dequeue the element and another index for the operation enqueue.
We have to update the indices for their corresponding operations(i.e. front when deque and end when enqueue).
