3. Write a pseudocode c++ algorithm to solve the following problem: Given exactl

Question

3. Write a pseudocode c++ algorithm to solve the following problem: Given exactly 1 Queue (empty to begin with) and 1 Stack (full of unsorted integers), sort all of the values such that in the end, the Stack contains all of the original values in ascending order (top value will be the largest int). You may only use the ADT operations listed in the slides: Queue (enqueue, dequeue, getFront, size, isEmpty) Stack (push, pop, getTop, size, isEmpty) You may also use a constant number of int variables. Your algorithm must have a runtime of O(N^2) worst-case. (Hint: Think about how the selection sort algorithm works.)

What is the Big-Oh running time complexity of your algorithm in question 3. Explain. Be sure to explain the Big-Oh runtime of each step in the algorithm.

Explanation / Answer

We have a stack full of unsorted numbers and an empty queue.At the end all the numbers
ina ascending order with largest number at the top:

We can pop all the numbers from the stack and fill it in the queue

while (!stack.isEmpty){
      a = stack.pop()
      queue.enqueue(a)
}

Now till the queue is empty we will do following operations:

a) Take an element from the queue and push to the stack.
b) Again taking a number and puhing to the stack, we will check if the top of
   the stack is more than the number dqueued, then we will put the number back to the queue
   and if it is smaller then we pop the current top and push this number and push the number
   coming from the stack to the queue.This operation we need to do number of element times.

for i: 1 to n{ // n is the number of elements
for j: 1 to n {
    a = queue.dequeue()
    if (!stack.isEmpty()){
        stack.push(a)
    }
    else{
        if (stack.top > a){
           b = stack.pop()
           queue.enqueue(b)
           stack.push(a)
        }
        else {
           queue.enqueue(a)
        }
   }

At the end of each iteration of i, we will have the smallest in queue to be in the stack.

As this runs for two loops with n , the complexity is O(n^2)
   

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.