C++利用兩個棧實現(xiàn)隊列的方法

更新時間：2019年05月19日 14:12:40 作者：alxe_made

這篇文章主要給大家介紹了關于C++利用兩個棧實現(xiàn)隊列的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C++具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧

1. 基礎

隊列：先進先出，即插入數(shù)據在隊尾進行，刪除數(shù)據在隊頭進行；

棧：后進先出，即插入與刪除數(shù)據均在棧頂進行。

2. 思路

兩個棧實現(xiàn)一個隊列的思想：用pushStack棧作為push數(shù)據的棧，用popStack棧作為pop數(shù)據的棧。

只要是對隊列進行push操作，就將數(shù)據push入pushStack棧中。
要實現(xiàn)隊列的pop操作，有二點原則，如果popStack為空的話那么我們就將pushStack所有的元素放到popStack中，然后取popStack棧頂元素就是隊列的隊頭；如果popStack不為空的話，我們就直接獲取popStack的棧頂元素。
對于top操作來說和pop操作類似，只是最后一步不用pop了。

3. 代碼

#include <iostream>
#include <stack>
#include <exception>

template<class T> class MyQueue {
 public:
 void push(const T& num); // 入隊列
 T pop(); // 出隊列
 T top();
 private:
 std::stack<T> pushStack;
 std::stack<T> popStack;
};
template<typename T>
void MyQueue<T>::push(const T& num) {
 pushStack.push(num);
}
template<typename T>
T MyQueue<T>::pop() {
 if (pushStack.empty() && popStack.empty()) { // 如果二個棧都為空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack為空,將pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 獲取pushStack棧頂元素
 pushStack.pop(); // 出棧
 popStack.push(data);
 }
 }
 T data = popStack.top();
 popStack.pop();
 return data;
}
template<typename T>
T MyQueue<T>::top() {
 if (pushStack.empty() && popStack.empty()) { // 如果二個棧都為空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack為空,將pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 獲取pushStack棧頂元素
 pushStack.pop(); // 出棧
 popStack.push(data);
 }
 } else { // 如果popStack不為空的話直接返回popStack棧頂
 T data = popStack.top();
 return data;
 }
}
int main() {
 MyQueue<int> myQueue1;
 myQueue1.push(1);
 myQueue1.push(2);
 myQueue1.push(3);
 myQueue1.push(4);
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;

 return 0;
}

4. 參考文獻

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。

您可能感興趣的文章: