【剑指offer】面试题7：用两个栈实现队列

2019-11-06 07:47:19

字体：大中小

来源：转载

供稿：网友

//用两个栈实现一个队列，实现它的两个函appendTail和deleteHead,分别在队列尾部插入结点和在队列头部删除结点的功能//思路：1.栈遵照先入先出的规则，当出队时，应当弹出第一个入栈的元素，但并不在栈顶，因此不能直接删除//2.所以借助栈2，把栈1的元素弹出压入栈2，就实现了逆置，出队时，弹出栈2的值。（此时栈2的栈顶元素就是我们要弹出的元素）我们就很容易解决这个问题了template<typename T>class CQueue{public: CQueue(void); ~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){ stack.push(node);}template<typename T>T CQueue<T>::deleteHead(){ //把栈1元素全部弹出，压入栈2 if (stack2.size() <= 0) { while (stack1.size() > 0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if (stack2.size() == 0) { throw std:; exception("Invalid input."); } T head=stack2.top(); stack2.pop(); return head;}

上一篇：【uestc 1425 D Farey Sequence Length】+ 打表

下一篇：数字三角形（顺推2维，逆推，顺推1维）