How can one implement a queue with only a stack implementation?

Question

I know with 2 stacks.but how with one?

Answer 1

Although it may be cheating to use recursion, I am not entirely sure if the code below can solve the problem, especially the part of peek().

public class Main {
    Stack<Integer> s1 = new Stack<Integer>();

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        s1.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        int top = s1.pop();
        if (s1.isEmpty())
            return top;

        int result = pop();
        s1.push(top);
        return result;
    }

    /**
     * Get the front element.
     */
    public int peek() {
        int top = s1.pop();
        if (s1.isEmpty()) {
            s1.push(top);
            return top;
        }

        int result = peek();
        s1.push(top);
        return result;
    }
    
    public boolean empty() {
        return s1.isEmpty();
    }
}

Answer 2

public T DeQueue()
{
    T retval = default(T);
    T current = Pop();

    if (stackInternal.Count >= 1)
    {
        retval = DeQueue();
    }

    if (stackInternal.Count == 0 && retval.Equals( default(T)))
    {
        retval = current;
        return retval;
    }
    else
    {
        Push(current);
    }

    return retval;
}

Answer 3

Following is the implementation for the java:

• During Enqueue operation, we can straight away push the element into the stack.

• During Dequeue operation,

  • Pop all the elements from Main Stack recursively until Stack size is equal to 1.
  • If Stack size = 1, Pop item from Stack, and return the same item.
  • Push all popped element back to Stack.

Below is tested program for the same.

public class QueueUsingSingleStack {

    Stack<Integer> stack = new Stack<>();

    private void enqueue(int i) {
        stack.push(i);
    }

    private int dequeue() throws Exception {
        if (stack.size() == 0)
            throw new Exception("Queue is Empty");

        if (stack.size() == 1)
            return stack.pop();

        int data = stack.pop();
        int retVal = dequeue();
        stack.push(data);
        return retVal;
    }

    public static void main(String[] args) throws Exception {
        QueueUsingSingleStack queue = new QueueUsingSingleStack();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

    }

}

Answer 4

//Implementing queue using a single stack



#include<stdio.h>
#define SIZE 10
int stack[10];
int top = -1;

int pop() {
    if(top != -1) return stack[top--];
}
void push(int data) {
    if(top < SIZE) stack[++top] = data;
}
void enqueue(int data) {
    push(data);
}
int dequeue() {
    if(top == 0) return pop();
    int data = pop();
    int value = dequeue();
    push(data);
    return value;
}

int main(void) {

    int i;

    //Enqueue
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    for(i=0;i<=top;i++) printf("%d ",stack[i]);
    printf("\n");

    //Dequeue
    printf("Dequeue --> %d\n",dequeue());
    printf("Dequeue --> %d\n",dequeue());
    for(i=0;i<=top;i++) printf("%d ",stack[i]);
    printf("\n");

    return 0;

}

Answer 5

#include<stdio.h>
#define SIZE 100
int stack[SIZE],top=-1;
void enqueue()
{
  int data1;
  printf("Enter the element to enqueue");
  scanf("%d",&data1);
  if(isEmptyStack()) 
    push(data1);
  else
    enqueue1(data1);
}
 int enqueue1(int data1)
{
  int data;
  if(isEmptyStack())
    return;
  data=pop();
  enqueue1(data1);
  push_bottom(data,data1);
   return ;
 }
int push_bottom(int data,int data1)
 { 
    if(isEmptyStack())
    {
     push(data1);
     push(data);
    }
   else
   {
    push(data);
   }
   return;
}
int isEmptyStack()
{
 if(top==-1)
  return 1;
  return 0;
}
int push(data)
{
  top++;
  stack[top]=data;
   return ;
}
void dequeue()
 {
  int a;
  a=pop();

}
 int pop()
 {
   int a=stack[top];
    top--;
  return a;
 }
 void print()
  {
     int i;
     printf("Stack elements are:");
    for(i=top;i>-1;i--)
   {
      printf("\n%d",stack[i]);
   } 
 }
 void main()
 {
   int choice;
   clrscr();
   printf("----Queue implementation using only one stack---");
   while(1)
    {
     printf("\n1.Enqueue \n2.Dequeue \n3.Print \n4.Exit");
     scanf("%d",&choice);
     switch(choice)
     {
      case 1:
      enqueue();
      break;
       case 2:
            dequeue();
            break;
       case 3:
         print();
        break;
       case 4:
         exit(0);
      }
     }
    }

Answer 6

Recursion is the answer

    public class QueueWithStack
    {
      private static Stack stackQueue;

      public QueueWithStack()
      {
        stackQueue = new Stack();
      }

      public void enqueue(int entry)
      {
        stackQueue.add(entry);
      }

      //dequeue a particular element from queue
      public void dequeue(int entry)
      {
        int popInt;

        if (!stackQueue.isEmpty())
        {
          popInt = stackQueue.pop();
          if (popInt != entry)
          {
            dequeue(entry)
            stackQueue.push(popInt);
          }
        }
        return;
      }

      public void dequeueFIFO()
      {
        if (!stackQueue.isEmpty())
        {
          int popInt = stackQueue.pop();
          if (!stackQueue.isEmpty())
          { 
            deququeFIFO();
            stackQueue.push(popInt);
          }
        }
      }
    }

Calling a main, creating a QueueWithStack object, and adding and removing Integers from this "queue" will allow the user to push items into the queue, and access any item from within the queue at any time, as well as remove items from the queue in FIFO order.

Answer 7

You can "cheat" by using recursive function calls to pop the stack, then you push the item being queued, then as the recursive calls unwind you push what was popped. But this is really two stacks, because the system program counter is a stack.