Consider a stack implemented as an array where the size is increased by a consta
ID: 3799376 • Letter: C
Question
Consider a stack implemented as an array where the size is increased by a constant factor every time the array fills up. What is the average running time of the push operation? What about if the array size is tripled when the array fills up? What is a potential downside of implementing a queue as a static array? Consider a stack implemented using a singly linked list with a head and tail pointer (and no sentinel nodes) with the top of the stack at the tail of the list. What is the average running time for peek (return the value of the top element without removing it)? What is the average running time for pop? What is the average running time for push? Consider the following situations: Discuss any advantages and disadvantages of efficiently implementing a queue using an array. Consider a queue implemented using a singly linked list with a head and tail pointer (with no sentinel nodes). Discuss any advantages and disadvantages of implementing the queue in this fashion if the frExplanation / Answer
1.) Push operation takes O(1) amount of time. It is irrespective of the fact whether size of the array is increasing by 1 or tripled by 3. So, in both cases, push operation will take running time of O(1).
2.) Implementing a queue can lead in number of gaps in the starting of the array which can't be filled as pointers to both front and rear move forwards.
3.) Since, push operation adds the element at the beginning of the linked list and pop operation takes element at the beginning of the list. So, peek, push and pop operations will take running time of O(1).
4.) One of the main advantage of implementing queue using an array is ease of implementation. And one of the biggest disadvantage is creation of gaps (As mentioned earlier).
a.) since front is pointing to the beginning of the list and tail pointer is pointing to end of the list then both enqueue and dequeue operation will take constant amount of time. So, time efficiency is the main advantage.
b.) since front is pointing to the end of the list and tail pointer is pointing to front of the list then both enqueue and dequeue operation will take O(n) amount of time as we have to traverse again to the end of list to perform enqueue operation and at the starting of the list for performing dequeue operation which is the disadvantage of this method over previous part.
Hope it helps, do give your response.