A queue Q is implemented using 2 stacks S1 and S2 using best possible algorithm. Consider the following operations to be performed in the empty queue in that order: Enqueue(A), Enqueue(B), Enqueue(C), Dequeue(), Enqueue(E), Enqueue(F) Dequeue(), Dequeue(), Dequeue()
To perform the above operations minimum number of PUSH and POP operations required are x and y respectively. What would be the value of x * y?
This is a homework problem for which the answer is given as 90 but I think it should be 56.
if we use the following algorithm, the answer comes out to be 90.
Enqueue:
Push the new element onto inbox
Dequeue:
If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
Pop and return the top element from outbox
But, if we make the following change to Dequeue operation, we could get 56 as answer as well.
Updated_Dequeue:
If outbox is empty:
Refill it by popping each element from inbox and pushing it onto outbox except the last one.
Pop and return the top(which is the last one) element from inbox
else:
Pop and return the top element from outbox
This would save us one Pop and one Push operation every time we are copying over elements from inbox to outbox while performing dequeue operation.
I dont believe this change makes the algorithm any better asymptotically but since question specifically asks for minimum number of PUSH and POP oprations, it should be 56, isn't?
Thanks!
In the most basic stack implementations you cannot know how many elements are on the stack. The only operations on such basic implementation are push and pop, with an error occurring when trying to pop an empty stack (which would not count as a pop).
I suppose it is this type of stack interface this challenge presupposes, and so you would not be able to know there is just one element remaining on the inbox stack without performing a pop.
isEmpty is a methodIf the stack has a isEmpty method, so that you don't need to actually call pop to detect an empty stack, you can get a little optimisation on the enqueue operation:
This change will lead to an output of 72 instead of 90.
But this is not possible without the isEmpty method, as then it will "cost" to check for an empty stack when it is actually not empty (you'll have to push back the value that was popped).
As background info, I provide here a minimal Stack implementation (only push and pop) and Queue implementation with the execution of the example; in JavaScript:
class Stack { // Implementation as Linked List
constructor() {
this.head = null;
// Additional access counters for statistics
this.pushCount = 0;
this.popCount = 0;
}
push(value) {
this.head = { value, next: this.head };
this.pushCount++;
}
pop() {
// Abort when the stack is empty. This does not count as a pop
if (!this.head) throw RangeError("Cannot pop from empty stack");
const value = this.head.value;
this.head = this.head.next;
this.popCount++;
return value;
}
}
class Queue {
constructor() {
this.inbox = new Stack();
this.outbox = new Stack();
}
enqueue(value) {
this.inbox.push(value);
}
dequeue() {
try {
return this.outbox.pop();
} catch {}
// outbox is empty:
try {
while (true) { // Until error:
this.outbox.push(this.inbox.pop());
}
} finally {
return this.outbox.pop();
}
}
statistics() {
return (this.inbox.popCount + this.outbox.popCount) * (this.inbox.pushCount + this.outbox.pushCount);
}
}
const q = new Queue();
q.enqueue("A");
// q: A
q.enqueue("B");
// q: A B
q.enqueue("C");
// q: A B C
console.log(q.dequeue()); // A
// q: B C
q.enqueue("E");
// q: B C E
q.enqueue("F");
// q: B C E F
console.log(q.dequeue()); // B
// q: C E F
console.log(q.dequeue()); // C
// q: E F
console.log(q.dequeue()); // E
// q: F
console.log("statistics:", q.statistics()); // 90As you can see, this stack interface does not provide the number of items on the stack and not even the fact whether the stack is empty. It is only via an invalid pop call that one can get information on whether the stack was empty or not before that call was made.
Still, you can chop off some push/pop calls if you allow for a local variable to temporarily hold some value that is neither in the inbox nor the outbox stacks:
class Stack { // Implementation as Linked List
constructor() {
this.head = null;
// Additional access counters for statistics
this.pushCount = 0;
this.popCount = 0;
}
push(value) {
this.head = { value, next: this.head };
this.pushCount++;
}
pop() {
// Abort when the stack is empty. This does not count as a pop
if (!this.head) throw RangeError("Cannot pop from empty stack");
const value = this.head.value;
this.head = this.head.next;
this.popCount++;
return value;
}
}
class Queue {
constructor() {
this.inbox = new Stack();
this.outbox = new Stack();
}
enqueue(value) {
this.inbox.push(value);
}
dequeue() {
try {
return this.outbox.pop();
} catch {}
// outbox is empty:
let buffer = this.inbox.pop(); // Don't push this on the outbox yet
try {
while (true) { // Until error:
const value = this.inbox.pop();
this.outbox.push(buffer);
buffer = value;
}
} finally {
return buffer; // Saving a push and pop on outbox.
}
}
statistics() {
return (this.inbox.popCount + this.outbox.popCount) * (this.inbox.pushCount + this.outbox.pushCount);
}
}
const q = new Queue();
q.enqueue("A");
// q: A
q.enqueue("B");
// q: A B
q.enqueue("C");
// q: A B C
console.log(q.dequeue()); // A
// q: B C
q.enqueue("E");
// q: B C E
q.enqueue("F");
// q: B C E F
console.log(q.dequeue()); // B
// q: C E F
console.log(q.dequeue()); // C
// q: E F
console.log(q.dequeue()); // E
// q: F
console.log("statistics:", q.statistics()); // 56So now we do get the 56 output that you suggested, even without having to rely on a size or isEmpty method. But I am pessimistic on whether this is allowed with the constraints of the problem, since the local variable buffer really acts as an additional data structure on top of the two stacks.