QueueToStack

文章目录

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

1 使用队列实现栈

1.1 问题分析

本质为，用队列“先进先出”的特性实现栈“后进先出”的特性！

1.2 解决方案设计

1.3 实现思路

1.4 代码实现

QueueToStack.h：

#ifndef QUEUETOSTACK_H #define QUEUETOSTACK_H #include "LinkQueue.h" #include "Stack.h" namespace LemonLib { template <typename T> class QueueToStack : public Stack<T> { protected: LinkQueue<T> m_queue1; LinkQueue<T> m_queue2; LinkQueue<T>* m_queue_in; LinkQueue<T>* m_queue_out; void move() const { int len = m_queue_in->size() - 1; while (len > 0) { m_queue_out->add(m_queue_in->front()); m_queue_in->remove(); len--; } } void swap() { LinkQueue<T>* tmp; tmp = m_queue_in; m_queue_in = m_queue_out; m_queue_out = tmp; } public: QueueToStack() { m_queue_in = &m_queue1; m_queue_out = &m_queue2; } void push(const T& e) { m_queue_in->add(e); } void pop() { move(); if (m_queue_in->size() > 0) { m_queue_in->remove(); swap(); } else { THROW_EXCEPTION(InvalidOperationException, "queue to stack pop error, stack is empty"); } } T top() const { move(); if (m_queue_in->size() > 0) { return m_queue_in->front(); } else { THROW_EXCEPTION(InvalidOperationException, "queue to stack top error, stack is empty"); } } int size() const { return m_queue_in->size() + m_queue_out->size(); } void clear() { m_queue_in->clear(); m_queue_out->clear(); } }; } #endif // QUEUETOSTACK_H

1.5 分析

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