【C/C++练习题】用两个栈实现队列

举报
王建峰 发表于 2021/11/19 00:30:17 2021/11/19
【摘要】 《剑指Offer》面试题9   1 问题 题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。 template <typename T> class CQueue{public: CQueue...

《剑指Offer》面试题9

 

1 问题

题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。


      template <typename T>
      class CQueue
      {
      public:
         CQueue(void);
          ~CQueue(void);
         void appendTail(const T& node);
         T deleteHead();
      private:
          stack<T> stack1;
          stack<T> stack2;
      };
  
 

 

2 分析

1.栈和队列都是线性表,但是栈只能从一端进行操作,队列从首尾两端进行操作。一个栈stack1作为队列尾部,另一个栈stack2作为队列头。
2.栈对数据的逻辑操作满足"先入后出",和队列相反。当经过stack1->stack2,原本栈底数据变成栈顶数据(两次反操作,等于一次正操作)
3.stack1 数据入队(队列尾部)、stack2 数据出队(队列头部)

 

3 代码


      #include "iostream"
      #include "stack"
      #include <exception>
      using namespace std;
      template <typename T>
      class CQueue
      {
      public:
         CQueue(void);
          ~CQueue(void);
         void appendTail(const T& node);
         T deleteHead();
      private:
          stack<T> stack1;
          stack<T> stack2;
      };
      template <typename T>
      CQueue<T> :: CQueue(void){
      }
      template <typename T>
      CQueue<T> :: ~CQueue(void){
      }
      template <typename T>
      void CQueue<T> :: appendTail(const T& node)
      {// 在队列末尾添加一个结点
     	this->stack1.push(node);	//数据压栈
      }
      template <typename T>
      T CQueue<T> :: deleteHead()
      {// 队列的头结点出队
         if(stack2.size()<= 0)
          {//1.stack2从stack1取数据
             while(stack1.size()>0)
              {
                  T& data = stack1.top();
                  stack1.pop();
                  stack2.push(data);
              }
          }
         //队列空了
         if(stack2.size() == 0)
          {
              cout << "queue is empty" << endl;
             exit(-1);
          }
         //数据出队
          T head = stack2.top();	//栈顶元素弹出
          stack2.pop();			//移除栈顶元素
         return head;
      }
      void Test(char actual, char expected)
      {
         if(actual == expected)
             printf("Test passed.\n");
         else
             printf("Test failed.\n");
      }
      int main(int argc, char* argv[])
      {
          CQueue<char> queue;
          queue.appendTail('a');
          queue.appendTail('b');
          queue.appendTail('c');			//cba
         char head = queue.deleteHead();	//a出队, cb
         Test(head, 'a');
          head = queue.deleteHead();		//b出队,c
         Test(head, 'b');
          queue.appendTail('d');			//d入队,dc
          head = queue.deleteHead();		//c出队,d
         Test(head, 'c');
          queue.appendTail('e');			//e入队,ed
          head = queue.deleteHead();		//d出队,e
         Test(head, 'd');
          head = queue.deleteHead();		//e出队,队空
         Test(head, 'e');
         return 0;
      }
  
 

4 运行结果

文章来源: blog.csdn.net,作者:hinzer,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/feit2417/article/details/96834586

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。