stackk

Question

Consider implementation of stack using queue by following algorithm.
Let x be an element to be pushed in the stack.
push(q1, x) {
EQ(q1,x)

while (q1 does not contain 1 element) {
k= DQ(q1)
EQ(q1,k)
}
}
pop(q1) {
DQ(q1)
}
If we implement the above algorithm using linked list, what will be the time complexity for push and pop operations?

1.   O(n), O(n)
2.   O(logn), O(1)
3.   O(1), O(n)
4.   O(n), O(1)

Comments

while loop in push will run an infinite amount of time. Because first inserting x and then keep on checking in while loop for queue contains only one element which will never false because before and after any iteration of while loop the size of queue remains same.

---

@shubhanshu

that while loop doesnt lead to infinite execution

that loop is used to move the elements to the right of it

if  push 1 2

then until one elemnt dequeue and enqueue so it becomes 2 1

now push = 2 1 3

pop and enqueue until one elemnt

so 3 2 1

now if we pop it will give elements in reverse order and therefore we have implemented a stack using queue

---

why is not infinite loop.. how it will stop does it maintain count or length ?

nothing is mentioned except q1 does not contain 1 element

how can you assume like that...

I think above code will go to infinite loop

Answer 1

In the program, Stack is implemented using 1 queue.
Assume, we are keeping two pointers front and rear which points to the head and the tail of the Linked List respectively.

Enqueue a new element at the tail (end) of the linked list and dequeue from the head(front) of the linked list.

Push operation needs O(n), because when push an element in the linked list (queue) we have to move all the previous elements in the linked list to the right of the newly inserted element, and Pop operation will need O(1).
 

Hence, (4) is correct option!