Question

Bonus. Let QA denote a new class of abstract machines that act just like PDAs, except that the stack is replaced with a queue. Argue informally that QAs are at least as powerful as PDAs, in the sense that any language accepted by a PDA is also accepted by some QA. Hint: show that you can simulate a stack by using a queue.

Can more than one stack be used, as in two stack push down automata? YES!!! Please help!!!!

Answer 1

In queue what ever comes first will go out first. So Queue are FIFO(First in first out)
while stack what ever comes last will go out first So stack are LIFO(last in first out)

We can implement queue with the help of two stack.

in Queue we need to make two operation:
enQueue(x) -> insert the X in back of queue
deQueue() -> remove the first element in queue

We are going to use two stacks s1 and s2.

we enter all elements in s1 So oldest elemet will always at top of s1 so that deQueue operation just pops from s1.

enQueue(x)
1) While s1 is not empty, push everything from s1 to s2.
2) Push x to s1 (assuming size of stacks is unlimited).
3) Push everything back to s1.
Here time complexity will be O(n)

deQueue(q)
1) If s1 is empty then error
2) Pop an item from s1 and return it
Here time complexity will be O(1)

suppose we have following elements in queue:

First enter element 3 : 3
then                4 : 3 -> 4
then                5 : 3 -> 4 -> 5

then remove element from queue 4 -> 5

First 3 comes First 4 comes then 5 comes deQueue element Pop item from s1 s1 s1 s2 s1 S1 S2 insert 4 insert 5 s1 S2 4 push back to s1 push back to s1