《剑指offer》面试题9-用两个栈实现队列

落日映苍穹つ 2022-03-10 14:05 147阅读 0赞

# 一、题目 #

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

# 二、题目分析 #

### 1、队列的性质是先进先出，而栈的性质是先进后出，先进的在栈底部，后进的在栈顶；   2、第一个栈临时保存插入的数据，当调用弹出函数的时候，如果stack2不为空则直接弹出；为空则把stack1中的数据全部弹出放到stack2中；   3、往第二个栈里面到，为避免麻烦，则选择在栈2中没有元素了之后再倒把栈1的元素全部倒给栈2，这样也能保证栈1栈底的元素总在栈2的栈顶。 ###

# 三、代码实现 #

template<typename T> class CQueue {
    public:
    	//CQueue();//构造函数
    	//~CQueue();//析构函数
    	void appendTail(const T& node);
    	T deleteHead();
    private:
    	stack<T> stack1;
    	stack<T> stack2;
    };
    //队列插入元素
    template<typename T>void CQueue<T>::appendTail(const T& node) {
    	stack1.push(node);//队列插入元素时，直接将其插入到栈1中
    }
    //队列删除元素
    template<typename T> T  CQueue<T>::deleteHead() {
    	T temp;
    	if (stack2.empty()) {//若栈2为空
    		if (stack1.empty()) return -1;//若栈1为空表示队列无元素可删除
    		while (!stack1.empty()) {//若栈1不为空
    			stack2.push(stack1.top());//则将栈1的所有元素推入到栈2中
    			stack1.pop();//将栈1置为空
    		}
    	}
    	temp = stack2.top();//取出栈2的栈顶元素
    	stack2.pop();//删除栈2的栈顶元素
    	return temp;
    }

同理，使用两个队列实现栈：

template<typename T> class QStack {
    public:
    	//CQueue();//构造函数
    	//~CQueue();//析构函数
    	void mypush(const T& node);
    	T mypop();
    private:
    	queue<T> queue1;
    	queue<T> queue2;
    };
    //栈插入元素
    template<typename T>void QStack<T>::mypush(const T& node) {
    	if (!queue1.empty() && !queue2.empty()) {
    		throw "error";//异常情况
    	}
    	if (queue1.empty() && queue2.empty()) {//若两个队列都为空时，直接将其插入到队列1中
    		queue1.push(node);
    	}
    	else if (!queue1.empty()) {//若队列1非空，直接将其插入到队列1中
    		queue1.push(node);
    	}
    	else {//若队列2非空，直接将其插入到队列2中
    		queue2.push(node);
    	}
    }
    //栈删除元素
    template<typename T> T  QStack<T>::mypop() {
    	if (queue1.empty() && queue2.empty()) return -1;
    	T temp;
    	if (!queue1.empty()) {
    		//queue1中的元素依次删除，并插入到queue2中，其中queue1删除最后一个元素
    		//相当于从栈中弹出队尾元素
    		int len = queue1.size();
    		for (int i = 0; i < len - 1; ++i) {
    			queue2.push(queue1.front());
    			queue1.pop();
    		}
    		temp = queue1.front();
    		queue1.pop();
    		return temp;
    	}
    	if (!queue2.empty()) {
    		//queue2中的元素依次删除，并插入到queue1中，其中queue2删除最后一个元素
    		//相当于从栈中弹出队尾元素
    		int len = queue2.size();
    		for (int i = 0; i < len - 1; ++i) {
    			queue1.push(queue2.front());
    			queue2.pop();
    		}
    		temp = queue2.front();
    		queue2.pop();
    		return temp;
    	}
    }