queue - 如何实现一个只有堆栈实现的队列？

Question

我知道有 2 个堆栈。但是如何使用一个？

Answer 1

您可以通过使用递归函数调用来“作弊”来弹出堆栈，然后推送正在排队的项目，然后随着递归调用展开，您推送弹出的内容。但这实际上是两个堆栈，因为系统程序计数器是一个堆栈。

Answer 2

递归就是答案

    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);
          }
        }
      }
    }

调用一个 main，创建一个 QueueWithStack 对象，并从这个“队列”中添加和删除整数将允许用户将项目推送到队列中，并随时访问队列中的任何项目，以及从队列中删除项目按先进先出顺序。

Answer 3

以下是java的实现：

• 在 Enqueue 操作期间，我们可以直接将元素压入堆栈。

• 在出队操作期间，

  • 递归弹出主栈中的所有元素，直到栈大小等于 1。
  • 如果 Stack size = 1，则从 Stack 中弹出项目，并返回相同的项目。
  • 将所有弹出的元素推回堆栈。

下面是相同的测试程序。

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

#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 5

//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 6

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 7

虽然使用递归可能会作弊，但我不完全确定下面的代码是否可以解决问题，尤其是 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();
    }
}