CareerCup

ah sorry! the question was to implement enqueue(int i) and dequeue() using stack ADT

what does ADT mean?

void enqueue(int i)
{
push(i);
}
int dequeue()
{
int temp1,temp2;
if (!count()) return ***;//TBD
if (count()==1) temp2=pop();
else {
temp1=pop();
temp2=dequeue();
enqueue(temp1);
}
return temp2;
}

doesnt a queue add from the bottom ,the above solution seems to be opposite of what needs to be done

Please comment on the statement
temp2=dequeue();

should it not just be dequeue();

why do we need to return the value of dequeue every time in temp2?

Use two stacks: S and T.

For enqueue(), just invoke S.push()

For dequeue(), pop each item in S and push it into T one by one. And the last item is the one to dequeue. And as the final step, pop each item in T and push it into S one by one.

Time efficiency might be a problem here...

Update my algorithm above.

For enqueue(),
1) if S.count() = 0 and T.count() != 0, then pop each item in T and push it into S one by one
2) Invoke S.push() to enqueue the new item

For dequeue(),
1) if S.count() > 0, then pop each item in S and push it into T
2) Invoke T.pop() to dequeue an item

anong klaseng java yan...

anong klaseng java yan...

anong klaseng java yan...

anong klaseng java yan...

enQ{
        push(a);
}

_dQ(data){

        if(stack_empty)
                return data;
        
        temp=pop();
        a=dQ(temp);
        push(temp);
        return a;
}

dequeue(){
        if(stack_empty)
        throw Exception;
        return  _dQ(0);
}

A Java implementation using only one stack. Use recursion to implement dequeue.

public class ID64863
{
	// Use only one stack. Use recursion to implement dequeue.
	StackWithCount stack=new StackWithCount();
	
	public void enqueue(int element)
	{
		stack.push(element);
	}
	public int dequeue()
	{
		if (stack.count()<=1)
			return stack.pop();
		int top=stack.pop();
		int result=dequeue();
		stack.push(top);
		return result;
	}
	
	public static void main(String[] args)
	{
		ID64863 queue=new ID64863();
		queue.enqueue(0);
		queue.enqueue(1);
		queue.enqueue(2);
		queue.enqueue(3);
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
	}
	public class StackWithCount extends Stack<Integer>
	{
		public int count()
		{
			return elementCount;
		}
	}
}