61 lines
1.6 KiB
C++
61 lines
1.6 KiB
C++
#ifndef QUEUE2STACK_H
|
|
#define QUEUE2STACK_H
|
|
|
|
#include "LinkedQueue.h"
|
|
#include "Stack.h"
|
|
#include <initializer_list>
|
|
|
|
namespace Kylin {
|
|
template <typename T>
|
|
class QueueToStack : public Stack<T> {
|
|
public:
|
|
QueueToStack(std::initializer_list<T> init) {
|
|
for (auto &value : init) push(value);
|
|
}
|
|
void push(const T &value) final {
|
|
makeOutQueueEmpty();
|
|
m_inQueue.enqueue(value);
|
|
}
|
|
|
|
T pop() final {
|
|
if (size() <= 0)
|
|
THROW_EXCEPTION(InvalidOperationException, "There is no element in QueueToStack ...");
|
|
if (m_outQueue.size() > 0) return m_outQueue.dequeue();
|
|
moveAnElementToEmptyOutQueue();
|
|
return m_outQueue.dequeue();
|
|
}
|
|
|
|
virtual T &top() {
|
|
if (size() <= 0) THROW_EXCEPTION(InvalidOperationException, "There is no element in stack...");
|
|
if (m_outQueue.size() > 0) return m_outQueue.head();
|
|
moveAnElementToEmptyOutQueue();
|
|
return m_outQueue.head();
|
|
}
|
|
|
|
virtual void clear() {
|
|
m_inQueue.clear();
|
|
m_outQueue.clear();
|
|
}
|
|
|
|
virtual size_t size() const { return m_inQueue.size() + m_outQueue.size(); }
|
|
|
|
protected:
|
|
void moveAnElementToEmptyOutQueue() {
|
|
while (m_inQueue.size() > 1) m_outQueue.enqueue(m_inQueue.dequeue());
|
|
m_inQueue.swap(m_outQueue);
|
|
}
|
|
|
|
void makeOutQueueEmpty() {
|
|
while (!m_outQueue.empty()) {
|
|
m_inQueue.enqueue(m_outQueue.dequeue());
|
|
}
|
|
}
|
|
|
|
private:
|
|
LinkedQueue<T> m_inQueue;
|
|
LinkedQueue<T> m_outQueue;
|
|
};
|
|
} // namespace Kylin
|
|
|
|
#endif // QUEUE2STACK_H
|