文章目錄

• • 1 使用隊列實現棧
  • • 1.1 問題分析
    • 1.2 解決方案設計
    • 1.3 實現思路
    • 1.4 代碼實現
    • 1.5 分析

1 使用隊列實現棧

1.1 問題分析

本質為，用隊列“先進先出”的特性實現?！昂筮M先出”的特性！

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)，所以無實際工程意義。

總結

以上是生活随笔為你收集整理的QueueToStack的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。