CODEWITHSUNDEEP
python-3.xdata-structuresqueuestack
Hamza
Hamza

Reputation: 75

Returning elements to stack in original order without using temporary stack

I have a stack S containing n elements and a queue Q that is initially empty. I have to implement an algorithm that uses Q to scan S to see if it contains a certain element x, with the additional constraint that my algorithm must return the elements back to S in their original order. The compulsion is that I may only use S, Q, and a constant number of other variables.

I have implemented this algorithm having used a temporary stack to hold elements and then return them to the original stack in their original order but how do I accomplish this task without using a temporary stack?

if __name__ == '__main__':
    
    def scan(S, Q, x):
        
        for i in range(10):
            S.push(i)
        
        S1 = ArrayStack()
        flag = False
        
        for i in range(len(S)):
            Q.enqueue(S.pop())
            if Q.first() == x:
                flag = True
                print("Your desired element has been found:", Q.first())
                S1.push(Q.dequeue())
                break
            else:
                S1.push(Q.dequeue())
                
        if flag == False: 
            print("Sadly, your desired element could not be found.")
                
        
        for i in range(len(S1)):
            S.push(S1.pop())
         
        
    scan(ArrayStack(), LinkedQueue(), 9)

Upvotes: 1

Views: 363

Answers (1)

trincot
trincot

Reputation: 349989

The trick is to first put the elements from the queue back on the stack -- which will put them in reversed order -- but then repeat the process again for the same number of values: pop them from the stack into the queue and then flush the queue back to the stack again. Now they will be back in their original order.

Not sure whether the function's signature has been given to you like that, but I would not pass Q as argument, since it only serves the function's algorithm, not the caller. On the other hand, I would not initialise the stack inside the function, but let the caller deal with populating the stack. That way the caller controls which stack data to call the function with.

So this is what you could do:

def scan(S, x):
    Q = LinkedQueue()  # Create the queue here
    
    found = False
    for i in range(len(S)):
        Q.enqueue(S.pop())
        found = Q.first() == x
        if found:
            break
    i += 1  # The number of values that are currently in the queue
    # Flush the queue on the stack
    for j in range(i):
        S.push(Q.dequeue())
    # They are reversed on the stack, so remove them again
    for j in range(i):
        Q.enqueue(S.pop())
    # and finally flush the queue again
    for j in range(i):
        S.push(Q.dequeue())
    return found

Call like this:

S = ArrayStack()
# Initialise the stack here
for i in range(10):
    S.push(i)    
# Get the boolean result from the function call
found = scan(S, 12)
# Use it to display a message
if found:
    print("Your desired element has been found")
else:
    print("Sadly, your desired element could not be found.")

Upvotes: 1

Related Questions