Skip to main content
edited tags
Link
200_success
  • 144.1k
  • 22
  • 188
  • 473
You use 2 stacks to implement a q, not a q to implement 2 stacks
Source Link
forsvarir
  • 11.7k
  • 6
  • 38
  • 71

Implement two stacks as a single queue using two stacks

This is for practicingpractising and understanding how the data structure works (Queue and stack). The main idea is to use two stacks and act as a single queue. The way I implement this problem is by assigning one stack to store odd number of elements and another one to store even number of elements. Example: if there are 3 elements, the first and the third element goes to the oddStack, the second element goes to evenStack.

Implement two stacks as a single queue

This is for practicing and understanding how the data structure works (Queue and stack). The main idea is to use two stacks and act as a single queue. The way I implement this problem is by assigning one stack to store odd number of elements and another one to store even number of elements. Example: if there are 3 elements, the first and the third element goes to the oddStack, the second element goes to evenStack.

Implement a queue using two stacks

This is for practising and understanding how the data structure works (Queue and stack). The main idea is to use two stacks and act as a single queue. The way I implement this problem is by assigning one stack to store odd number of elements and another one to store even number of elements. Example: if there are 3 elements, the first and the third element goes to the oddStack, the second element goes to evenStack.

Source Link

Implement two stacks as a single queue

I tried to implement a queue using two stacks. I saw there are questions about this topic, but in my example, I used build-in stack from java. My question is, can someone give me some advice to make my code more efficient or better (in turn of class structure, for-loop, etc)?

This is for practicing and understanding how the data structure works (Queue and stack). The main idea is to use two stacks and act as a single queue. The way I implement this problem is by assigning one stack to store odd number of elements and another one to store even number of elements. Example: if there are 3 elements, the first and the third element goes to the oddStack, the second element goes to evenStack.

import java.util.Stack;

public class twoStacksInOneQueue {

private Stack <Integer> oddStack;
private Stack <Integer> evenStack;
private int counter;// count added element
private int shift;//count internal movement from one stack to another.
/**
 Constructor
 */
public twoStacksInOneQueue()
{
    counter = 1;
    shift = 0;
    oddStack = new Stack<Integer>();
    evenStack = new Stack <Integer>();
}
/**
 add element to queue according to amount of elements.
 if there are 3 element, the 3rd element is put into odd stack.
 */
public void addToQueue(int num)
{
    if(counter % 2 == 0)
    {
        evenStack.push(num);
        System.out.println("evenStack: " +  num);
    }
    else
    {
        oddStack.push(num);
        System.out.println("oddStack: " +  num);
    }
    counter++;       
}

/**
 remove an element from queue according to amount of elements
 */
public int removeFromQueue()
{
    int temp;
    int result = 0;

    if(counter == 0)//empty queue
    {
        System.out.println("The Queue is empty!");
    }
    else if (counter % 2 == 0) //if there are even elements
    {
        while(!evenStack.empty())//loop while not empty
        {
            //move the entire stack to another to get the bottom of the stack
            temp = evenStack.pop();
            oddStack.push(temp);
            shift++;
        }
        result = oddStack.pop();//the previous bottom of the moved stack
        System.out.println("result From even: "+result);

        while (shift-1  > 0)//move the moved stack back. -1 because of the popped element above
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift--;
        }
        counter--;
    }
    else //if there are odd elements
    {
        while(!oddStack.empty())
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift++;
        }
        result = evenStack.pop();

        System.out.println("result from odd: "+result);
        while (shift-1 > 0)
        {
            temp = evenStack.pop();
            oddStack.push(temp);
            shift--;
        }
        counter--;
    }
    shift = 0;//reset internal moved counter.
    return result;
}

public static void main (String [] arg)
{
   twoStacksInOneQueue myQueue = new twoStacksInOneQueue();
    for (int i = 0; i< 4; i++)
    {
        myQueue.addToQueue(i+1);
    }

    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
}