使用两个队列实现栈的 C++ 程序

栈

栈是采用 LIFO 方式实现的，其中插入和删除都在同一端（顶部）进行。最后进入的元素最先被删除。

栈操作包括：-

• push (int data) - 在顶部插入
• int pop() - 从顶部删除

队列

队列是采用 FIFO 方式实现的，其中从一端（后部）插入，从另一端（前端）删除。最先进入的元素最先被删除。

队列操作包括：-

• EnQueue (int data) - 在后端插入
• int DeQueue() - 从前端删除

这是一个使用两个队列实现栈的 C++ 程序

算法

Begin
   function enqueue1 to insert item a at qu1:
   Set, np1 = new qu1
   np1->d1 = a
   np1->n1 = NULL
   if (f1 == NULL)
      Then set
      r1 = np1
      r1->n1 = NULL
      f1 = r1
   else
      r1->n1 = np1
      r1 = np1
      r1->n1 = NULL
End

Begin
   function dequeue1 to delete item from qu1.
   if queue is null
      Print no elements present in queue.
   Else
      q1 = f1
      f1 = f1->n1
      a = q1->d1
      delete(q1)
   return a
End

Begin
   function enqueue2 to insert item a at qu2.
   np2 = new qu2;
   np2->d2 = a;
   np2->n2 = NULL;
   if queue is null
      Set r2 = np2
      r2->n2 = NULL
      f2 = r2
   Else
      Set r2->n2 = np2
      r2 = np2
      r2->n2 = NULL
End

Begin
   function dequeue2 to delete item from qu2:
   if queue is null
      Print no elements present in queue.
   Else
      q2 = f2
      f2 = f2->n2
      a = q2->d2
      delete(q2)
   return a
End

示例代码

#include<iostream>
using namespace std;

struct qu1// queue1 declaration {
   qu1 *n1;
   int d1;
}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;

struct qu2// queue2 declaration {
   qu2 *n2;
   int d2;
}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;

void enqueue1(int a) {
   np1 = new qu1;
   np1->d1 = a;
   np1->n1 = NULL;
   if (f1 == NULL) {
      r1 = np1;
      r1->n1 = NULL;
      f1 = r1;
   } else {
      r1->n1 = np1;
      r1 = np1;
      r1->n1 = NULL;
   }
}

int dequeue1() {
   int a;
   if (f1 == NULL) {
      cout<<"no elements present in queue\n";
   } else {
      q1 = f1;
      f1 = f1->n1;
      a = q1->d1;
      delete(q1);
      return a;
   }
}

void enqueue2(int a) {
   np2 = new qu2;
   np2->d2 = a;
   np2->n2 = NULL;
   if (f2 == NULL) {
      r2 = np2;
      r2->n2 = NULL;
      f2 = r2;
   } else {
      r2->n2 = np2;
      r2 = np2;
      r2->n2 = NULL;
   }
}

int dequeue2() {
   int a;
   if (f2 == NULL) {
      cout<<"no elements present in queue\n";
   } else {
      q2 = f2;
      f2 = f2->n2;
      a = q2->d2;
      delete(q2);
      return a;
   }
}

int main() {
   int n, a, i = 0;
   cout<<"Enter the number of elements to be entered into stack\n";
   cin>>n;
   while (i < n) {
      cout<<"enter the element to be entered\n";
      cin>>a;
      enqueue1(a);
      i++;
   }
   cout<<"\n\nElements popped\n\n";
   while (f1 != NULL || f2 != NULL)// if both queues are not null {
      if (f2 == NULL)// if queue 2 is null {
         while (f1->n1 != NULL) {
            enqueue2(dequeue1());
         }
         cout<<dequeue1()<<endl;
      } else if (f1 == NULL)//if queue 1 is null {
         while (f2->n2 != NULL) {
            enqueue1(dequeue2());
         }
         cout<<dequeue2()<<endl;
      }
   }
}

输出

Enter the number of elements to be entered into stack
5
enter the element to be entered
1
enter the element to be entered
2
enter the element to be entered
3
enter the element to be entered
4
enter the element to be entered
5

Elements popped
5
4
3
2
1

Nishtha Thakur

更新日期：2019 年 7 月 30 日

1 千次以上浏览

开启你的 职业生涯

完成此课程以获得认证

开始吧