赞
踩
队列是一种先进先出的数据结构,队列元素从队头出队,从队尾入队,如一组数入队顺序为:5 4 3 2 1,则出队顺序也为:5 4 3 2 1。
这里使用静态数组实现一个简易队列,该实现主要通过三个标识符标记队列元素
int m_length; //队列实际元素个数
int m_head; //下一次出队位置
int m_tail; //下一次入队位置
主要实现接口:
enqueue() | 元素入队 |
---|---|
front() | 返回队头元素 |
dequeue() | 元素出队 |
初始时队列为空,m_head
和m_tail
指向同一个位置,m_length
为0
入队示意:
可以看出队列满时m_head
和m_tail
指向的位置也相同,此时通过m_length
判断队列是满(N)或空(0)
出队示意:
通过示意图分析,实现思路如下:
使用enqueue()
接口
m_tail
(下一次入队位置)和m_length
(队列元素个数)m_tail
位置循环加1,m_length
自增1,m_length
等于最大容量 N 时队列满使用front()
接口
返回队头下标m_head
对应元素即可
使用dequeue()
接口
m_head
(下一次出队位置)和m_length
(队列元素个数)m_head
位置循环加1,m_length
自减1,m_length
等于 0 时队列空#include<iostream> #include<cassert> template<typename T, int N> class ArrayQueue { private: T m_array[N]; int m_length; int m_head; int m_tail; public: ArrayQueue() : m_length(0), m_head(0), m_tail(0) {} ~ArrayQueue() = default; void enqueue(const T& e) { if ( m_length < N ) { m_array[m_tail] = e; m_tail = (m_tail + 1) % N; m_length++; } } T front() const { if ( m_length > 0 ) { return m_array[m_head]; } else { throw std::out_of_range("no element in queue ..."); } } void dequeue() { if ( m_length > 0 ) { m_head = (m_head + 1) % N; m_length--; } } void clear() { m_head = 0; m_tail = 0; m_length = 0; } int capacity() const { return N; } int length() const { return m_length; } }; int main() { ArrayQueue<int, 5> array_queue; for ( int i = 5; i > 0; --i ) { array_queue.enqueue(i); } for ( int i = 0; i < 5; ++i ) { std::cout << array_queue.front() << " "; array_queue.dequeue(); } std::cout << std::endl; return 0; } //运行结果 5 4 3 2 1
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。