Skip to main content

Data structure problem 1:Implement a queue using 2 stacks.



This is one of the interview questions asked in technical or data structure round.

As we know stack is first in last out and queue is first in first out.

Here we have to implement the behaviour of queue using 2 stacks.

So let's begin with one of the approaches,


For 2 stacks we have define 2 arrays;


var stack1=[];

var stack2=[];



For insertion or push, we will use stack1.

For any insertion, we can push it in stack1 array.


a)Insert "A"

stack1.push("A");


b)Insert "B"

stack1.push("B");


c)Insert "C"

stack1.push("C");


Now when we remove or pop, the first pushed element should be removed first i.e behaviour of a queue.

  

So if we poped from stack1 we will get the behaviour of stack here.


stack1.pop()//"C" will be removed i.e behaviour of stack last in first out.


We can't use this, so we will need stack2 for this purpose to implement the behaviour of the queue.


d)Remove or pop:

For first remove or pop, we will need to pop every element in stack1 and push it to stack2.

So here are the values of stack2 and stack1, 

   stack2 =["C","B","A"];

   stack1=[];

And then pop from stack2. 

i.e stack2.pop()//"A" will be poped which is inserted first. 

So here we have implemented behaviour of queue.



For another insertion or push,

e)Insert "D"

stack1.push("D");


stack1=["D"];

stack2=["C","B"];


Now for 2nd remove operation first we need to check if stack2 is empty. 

If not empty then just pop element from stack2 for every remove

operation till stack2 becomes empty.

stack2.pop()//=>"B"

stack2.pop()//=>"C"

Now stack 2 is empty, So we can't pop .

stack1=["D"];

stack2=[];


So if stack2 is empty then pushed all elements from stack1 to stack2 and pop stack2.

i.e one that we had done for first remove or pop operation.  

stack1=[];

stack2=["D"];

stack2.pop()//=>"D"


By this approach, we can implement a queue using two stacks.


I hope you like this article. Please stay connected for more such articles.

If any doubts please let me know in the comment section.

You can also follow me on Twitter or Linkedin for the latest updates.


Written By:

Saurabh Joshi




Comments

Popular posts from this blog

Globant part 1

 1)call,apply,bind example? Ans: a. call Method: The call method is used to call a function with a given this value and arguments provided individually. Javascript code: function greet(name) {   console.log(`Hello, ${name}! I am ${this.role}.`); } const person = {   role: 'developer' }; greet.call(person, 'Alice'); // Output: Hello, Alice! I am developer. In this example, call invokes the greet function with person as the this value and passes 'Alice' as an argument. b. apply Method: The apply method is similar to call, but it accepts arguments as an array. Javascript code: function introduce(language1, language2) {   console.log(`I can code in ${language1} and ${language2}. I am ${this.name}.`); } const coder = {   name: 'Bob' }; introduce.apply(coder, ['JavaScript', 'Python']); // Output: I can code in JavaScript and Python. I am Bob. Here, apply is used to invoke introduce with coder as this and an array ['JavaScript', 'Pyt...

Node.js: Extract text from image using Tesseract.

In this article, we will see how to extract text from images using Tesseract . So let's start with this use-case, Suppose you have 300 screenshot images in your mobile which has an email attribute that you need for some reason like growing your network or for email marketing. To get an email from all these images manually into CSV or excel will take a lot of time. So now we will check how to automate this thing. First, you need to install Tesseract OCR( An optical character recognition engine ) pre-built binary package for a particular OS. I have tested it for Windows 10. For Windows 10, you can install  it from here. For other OS you make check  this link. So once you install Tesseract from windows setup, you also need to set path variable probably, 'C:\Program Files\Tesseract-OCR' to access it from any location. Then you need to install textract library from npm. To read the path of these 300 images we can select all images and can rename it to som...

CSS INTERVIEW QUESTIONS SET 2

  You make also like this CSS interview question set 1. Let's begin with set 2, 5)What is the difference between opacity 0 vs display none vs visibility hidden? Property           | occupies space | consumes clicks | +--------------------+----------------+-----------------+ | opacity: 0         |        yes      |        yes       | +--------------------+----------------+-----------------+ | visibility: hidden |        yes       |        no        | +--------------------+----------------+-----------------+ | display: none      |        no       |        no        | When we say it consumes click, that means it also consumes other pointer-events like onmousedown,onmousemove, etc. In e...