StackToQueue

文章目录

1 使用栈实现队列1.1 问题分析1.2 解决方案设计1.3 实现思路1.4 代码实现1.5 分析

1 使用栈实现队列

1.1 问题分析

用栈实现队列等价于用“后进先出”的特性实现“先进先出”的特性。

1.2 解决方案设计

1.3 实现思路

1.4 代码实现

StackToQueue.h：

#ifndef STACKTOQUEUE_H #define STACKTOQUEUE_H #include "LinkStack.h" #include "Queue.h" namespace LemonLib { template <typename T> class StackToQueue : public Queue<T> { protected: mutable LinkStack<T> m_stack_in; mutable LinkStack<T> m_stack_out; void move() const { if (m_stack_out.size() == 0) { while (m_stack_in.size() > 0) { m_stack_out.push(m_stack_in.top()); m_stack_in.pop(); } } } public: void add(const T& e) { m_stack_in.push(e); } void remove() { move(); if (m_stack_out.size() > 0) { m_stack_out.pop(); } else { THROW_EXCEPTION(InvalidOperationException, "stack to queue remove error, queue is empty"); } } T front() const { move(); if (m_stack_out.size() > 0) { return m_stack_out.top(); } else { THROW_EXCEPTION(InvalidOperationException, "stack to queue front error, queue is empty"); } } void clear() { m_stack_in.clear(); m_stack_out.clear(); } int size() const { return m_stack_in.size() + m_stack_out.size(); } }; } #endif // STACKTOQUEUE_H

1.5 分析

使用的栈实现队列的方式时间复杂度出现了很多个O(n)，所以无实际工程意义。