一, 介绍
队列(Queue), 是一种线性存储结构. 它有以下几个特点:
(01) 队列中数据是按照 "先进先出(FIFO, First-In-First-Out)" 方式进出队列的.
(02) 队列只允许在 "队首" 进行删除操作, 而在 "队尾" 进行插入操作.
队列通常包括的两种操作: 入队列 和 出队列.
二, 实现
C++ 的 STL 中本身就包含了 list 类, 基本上该 list 类就能满足我们的需求, 所以很少需要我们自己来实现. 本部分介绍 2 种 C++ 实现.
1. C++ 实现一: 数组实现的队列, 能存储任意类型的数据.
2. C++ 实现二: C++ 的 STL 中自带的 "队列"(list)的示例.
1.C++ 实现一: 数组实现的队列, 能存储任意类型的数据.
实现代码:.h
- #ifndef ARRAY_QUEUE_HXX
- #define ARRAY_QUEUE_HXX
- #include <iostream>
- using namespace std;
- template<class T> class ArrayQueue{
- public:
- ArrayQueue();
- ~ArrayQueue();
- void add(T t);
- T front();
- T pop();
- int size();
- int is_empty();
- private:
- T *arr;
- int count;
- };
- // 创建 "队列", 默认大小是 12
- template<class T>
- ArrayQueue<T>::ArrayQueue()
- {
- arr = new T[12];
- if (!arr)
- {
- cout<<"arr malloc error!"<<endl;
- }
- }
- // 销毁 "队列"
- template<class T>
- ArrayQueue<T>::~ArrayQueue()
- {
- if (arr)
- {
- delete[] arr;
- arr = NULL;
- }
- }
- // 将 val 添加到队列的末尾
- template<class T>
- void ArrayQueue<T>::add(T t)
- {
- arr[count++] = t;
- }
- // 返回 "队列开头元素"
- template<class T>
- T ArrayQueue<T>::front()
- {
- return arr[0];
- }
- // 返回并删除 "队列末尾的元素"
- template<class T>
- T ArrayQueue<T>::pop()
- {
- int i = 0;;
- T ret = arr[0];
- count--;
- while (i++<count)
- arr[i-1] = arr[i];
- return ret;
- }
- // 返回 "队列" 的大小
- template<class T>
- int ArrayQueue<T>::size()
- {
- return count;
- }
- // 返回 "队列" 是否为空
- template<class T>
- int ArrayQueue<T>::is_empty()
- {
- return count==0;
- }
- #endif
- View Code
测试代码: .cpp
- #include <iostream>
- #include "ArrayQueue.h"
- using namespace std;
- /**
- * C++ : 数组实现 "队列", 能存储任意数据.
- *
- * @author skywang
- * @date 2013/11/07
- */
- int main()
- {
- int tmp=0;
- ArrayQueue<int> *astack = new ArrayQueue<int>();
- // 将 10, 20, 30 依次推入队列中
- astack->add(10);
- astack->add(20);
- astack->add(30);
- // 将 "队列开头元素" 赋值给 tmp, 并删除 "该元素"
- tmp = astack->pop();
- cout<<"tmp="<<tmp<<endl;
- // 只将 "队列开头的元素" 赋值给 tmp, 不删除该元素.
- tmp = astack->front();
- cout<<"tmp="<<tmp<<endl;
- astack->add(40);
- cout<<"is_empty()="<<astack->is_empty()<<endl;
- cout<<"size()="<<astack->size()<<endl;
- while (!astack->is_empty())
- {
- tmp = astack->pop();
- cout<<tmp<<endl;
- }
- return 0;
- }
- View Code
2. C++ 实现二: C++ 的 STL 中自带的 "队列"(list)的示例
- #include <iostream>
- #include <queue>
- using namespace std;
- /**
- * C++ : STL 中的队列 (queue) 的演示程序.
- *
- * @author skywang
- * @date 2013/11/07
- */
- int main ()
- {
- int tmp=0;
- queue<int> iqueue;
- // 将 10, 20, 30 依次加入队列的末尾
- iqueue.push(10);
- iqueue.push(20);
- iqueue.push(30);
- // 删除队列开头的元素
- iqueue.pop();
- // 将 "队列开头的元素" 赋值给 tmp, 不删除该元素.
- tmp = iqueue.front();
- cout<<"tmp="<<tmp<<endl;
- // 将 40 加入到队列的末尾
- iqueue.push(40);
- cout << "empty()=" << iqueue.empty() <<endl;
- cout << "size()=" << iqueue.size() <<endl;
- while (!iqueue.empty())
- {
- tmp = iqueue.front();
- cout<<tmp<<endl;
- iqueue.pop();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2798471.html