Implement a Queue Using Two Stacks

Getting to first base with my mind, and other ways i like to tease my brain.

Problem:

Implement a queue using two stacks.

First Thoughts:

Queues are a FIFO, first in first out, data structure while stacks are a LIFO, last in first out data structure. Here, we have to be able to account for inserting things into our « queue » which we will call Squeue.

My Solution:

This first thing operation we account for is for inserting into the Squeue.

We can insert an item the same way we would insert it into a regular stack. Just by « pushing » the object onto stack1. This can be done in constant time and is thus O(1).

The tricky part comes when we have to remove an element from the Squeue. In a queue, the first object that is added in need to be the first one that is removed from the queue, but when we try to remove an object from a stack, we will be given the…

View original post 185 mots de plus

Publicités

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s