Data Structure Design As we have seen in the lectures, priority queues can be im
ID: 3850678 • Letter: D
Question
Data Structure Design As we have seen in the lectures, priority queues can be implemented with a variety of underlying data structures. This question involves implementing the operations of a priority queue (INSERT and REMOVEMIN) using a particularly odd choice for the underlying data structure: a pair of stacks. For this question, the only operations you are permitted to use on the stacks are PUSH and POP. Your pseudocode may use any (constant) number of local variables, but no arrays or other O(n) storage structures are permitted except the two stacks. (a) Give pseudocode for the INSERT and REMOVEMIN operations using only two stacks S_1 and S_2 to store the underlying elements, such that the INSERT operation requires CircleMinus(1) time. You may assume that the PUSH and POP operations of the stacks are CircleMinus(1) in the worst case. Give a Big-Theta expression for the asymptotic worst case running time of the REMOVEMIN operation. (b) Give pseudocode for the INSERT and REMOVEMIN operations using only two stacks S_1 and S_2 to store the underlying elements, such that the REMOVEMIN operation requires CircleMinus(1) time. You may assume that the PUSH and POP operations of the stacks are CircleMinus(1) in the worst case. Give a Big-Theta expression for the asymptotic worst case running time of the INSERT operation.Explanation / Answer
a)
class QueueUsingTwoStacks{
private:
Stack s1;
Stack S2;
public:
void Insert(int data);
int RemoveMin();
};
void Insert(int x):
1. Push x to InputStack.
int RemoveMin():
1. IF (both InputStack and OutputStack are empty) THEN error.
2. IF (OutputStack is empty)
Pop all elements from InputStack and push them into OutputStack (one element at a time).
3. Pop minimum element from OutputStack and return.
In this case, Insert() will take constant time and worst case analysis of RemoveMin() is Big - Theta (n).
b)
void Insert(int x):
1. Pop everything from OutputStack and push it into InputStack.
2. Push x into InputStack.
3. Pop everything out from InputStack and push it into OutputStack.
int RemoveMin():
1. IF (OutputStack is empty) THEN error.
2. Find minimum element from the OutputStack in O(1).
2. Pop that element from OutputStack and return.
In this case, RemoveMin() will take constant time and worst case analysis of Insert() is Big - Theta (n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.