队列(c++实现)
程序员文章站
2024-02-11 23:24:34
...
队列的特点是先进先出,跟栈的c++实现类似,队列的c++实现同样有两种方式:
Queue是一个接口类,封装了队列相关的所有操作:
//Queue.h
#ifndef __QUEUE_H__
#define __QUEUE_H__
#include <exception>
template<typename T>
class Queue
{
public:
virtual void add(const T& e) = 0; //向队列增加元素
virtual void remove() = 0; //删除队列(头)元素
virtual T front() const = 0; //获取队列(头)元素
virtual void clear() = 0; //清空队列
virtual int length() const = 0; //获取队列长度
};
#endif /* __QUEUE_H__ */
队列数据结构其实就是前面讲的环形缓冲区,核心是两个循环计数的指针分别表示读/写位置。
队列空间是静态分配的数组:
//StaticQueue.h
#ifndef __STATICQUEUE_H__
#define __STATICQUEUE_H__
#include "Queue.h"
template <typename T, int N>
class StaticQueue : public Queue<T>
{
protected:
T m_space[N];
int m_write;
int m_read;
int m_length;
public:
StaticQueue() : m_write(0), m_read(0), m_length(0)
{
}
int capacity() const
{
return N;
}
void add(const T& e)
{
if (m_length < N)
{
m_space[m_write] = e;
m_write = (m_write + 1) % N;
++m_length;
}
else
throw(std::runtime_error("No space in current queue"));
}
void remove()
{
if (m_length > 0)
{
m_read = (m_read + 1) % N;
--m_length;
}
else
throw(std::runtime_error("No element in current queue"));
}
T front() const
{
if (m_length > 0)
return m_space[m_read];
else
throw(std::runtime_error("No element in current queue"));
}
void clear()
{
m_write = 0;
m_read = 0;
m_length = 0;
}
int length() const
{
return m_length;
}
};
#endif /* __STATICQUEUE_H__ */
测试:
//main.cpp
int main(void)
{
StaticQueue<int, 6> queue;
for (int i = 0; i < 6; ++i)
{
queue.add(i);
}
while (queue.length() > 0)
{
std::cout << queue.front() << std::endl;
queue.remove();
}
getchar();
return 0;
}
用链表实现队列空间,这里采用Linux内核链表来实现:
//LinkQueue.h
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
#include "linux_list.h"
#include "Queue.h"
template<typename T>
class LinkQueue : public Queue<T>
{
protected:
struct Node_t
{
list_head head;
T value;
};
list_head m_head;
int m_length;
public:
LinkQueue()
{
m_length = 0;
INIT_LIST_HEAD(&m_head);
}
void add(const T& e)
{
Node_t *node = new Node_t();
if (node)
{
node->value = e;
list_add_tail(&node->head, &m_head);
++m_length;
}
else
throw(std::runtime_error("No memory in create queue"));
}
void remove()
{
if (m_length > 0)
{
list_head* toDel = m_head.next;
list_del(toDel);
--m_length;
delete list_entry(toDel, Node_t, head);
}
else
throw(std::runtime_error("No element in current queue"));
}
T front() const
{
if (m_length > 0)
{
return list_entry(m_head.next, Node_t, head)->value;
}
else
throw(std::runtime_error("No element in current queue"));
}
void clear()
{
while (m_length > 0)
remove();
}
int length() const
{
return m_length;
}
~LinkQueue()
{
clear();
}
};
#endif /* __LINKQUEUE_H__ */