本文共 1704 字，大约阅读时间需要 5 分钟。

题目总结与代码归档：

GitHub代码路径：

面试题9

用两个栈实现队列

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

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

解题思路

一个队列中包含两个栈stack1和stack2，操作两个“先进后出"的栈实现一个”先进先出"的队列

代码实现

09 用两个栈实现队列.h

#pragma once#include 
   
    #include 
    
     using namespace std;template 
     
       class CQueue{
   public:	CQueue(void);	~CQueue(void);	// 在队列末尾添加一个结点	void appendTail(const T& node);	// 删除队列的头结点	T deleteHead();private:	stack
      
        stack1;	stack
       
         stack2;};template 
        
          CQueue
         
          ::CQueue(void){ }template 
          
            CQueue
           
            ::~CQueue(void){ }template 
            
              void CQueue
             
              ::appendTail(const T& node){ stack1.push(node); // 尾部添加 直接 stack1 入栈}template 
              
                T CQueue
               
                ::deleteHead(){ // 删除头部 需分情况处理 if (stack2.size() <= 0) // stack2 中没有数据 需要从 stack1 依次出栈元素并压入stack2中 { while (stack1.size() > 0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if (stack2.size() == 0) //上述处理后 还未空 说明 本身为空 throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head;}
               
              
             
            
           
          
         
        
       
      
     
    
   

09 用两个栈实现队列.cpp

#include "09 用两个栈实现队列.h"#include 
   
    int main(int argc, char* argv[]){
   	CQueue
    
      queue;	queue.appendTail('a');	queue.appendTail('b');	queue.appendTail('c');	char head = queue.deleteHead();	cout << head << endl;	queue.appendTail('d');	head = queue.deleteHead();	cout << head << endl;	queue.appendTail('e');	head = queue.deleteHead();	cout << head << endl;	head = queue.deleteHead();	cout << head << endl;	system("pause");	return 0;}
    
   

GitHub链接：

CSDN首页：

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/107624432 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！