C++实现队列--数组实现和链表实现

时间：2023-01-27 17:37:18

队列是一个简单的等待序列，在尾部加入元素时队列加长，在前端删除数据时队列缩短。与栈不同，队列是一种两端的结构：一端用来加入新元素，另一端用来删除元素。因此，元素必须等到排在它之前的所有元素删除之后才能操作。队列是FIFO（first in first out)结构。


一：队列的数组实现


 我们用 first 和 last 存储队列首元素和尾元素的下标。 *当队列为空时，习惯上设置 first 和 last 的值为-1。当数据入队时, 必须先++相应的下标，然后再存入数据。
*判断队列是否为空：这时只需要看 first 就可以，如果 first == -1 ， 队列即为空。
*判断队列是否已满：队列满队，有两种情况： 1.当队列首次按顺序存满数据时，它的 first 等于0，指向storge数组第一个元素位置storge[0]，而它的last 等于size-1，指向storge数组最后一个元素storge[size-1]，此时队列已满。 2.另外一种情况就是，但我们首次队列满时，将一些元素出队，由于队列是FIFO结构，从头部开始出队，这样在队列元素未全部出队的情况下，first 指向后移。当我们再次将一些数据入队时，last 从storge[size-1] 再次回到 storge[0]，然后按照队列顺序入队，当last = first -1 时，队列再次满队。
*入队操作： 1.首先入队操作首先判断队列是否已满，队列已满则不入队。 2.其次，我们要注意到特殊情况，当队列由空队开始存入第一个数据时，以及last 等于 size-1 时，我们下一个数据入队会被存储在storge[0]的位置，此时需要令 last = 0，不要忘了如果 first 等于-1，同时要令 first = 0;  3.其他情况++last，然后入队即可。
*出队操作： 1.首先判断队列是否空，若为空，则不能出队。 2.重点：当 first等于last 时，说明队列中只有一个元素，此时出队后队列为空，切记将 first ，last值 赋为-1，表示队列空。 3.特殊情况：当 first 等于size-1 时，它处于storge数组尾部，事实上由于它是队列此状态下的首元素，队列的第二个元素是storge数组storge[0]，所以此时进行出队操作后，须将 first 的值设置为0。 4.其他情况 直接出队，++first即可。   队列数组实现代码如下： 
#ifndef _ARRAY_QUEUE_H
#define _ARRAY_QUEUE_H

#include <iostream>
using namespace std;

template<typename T, int size = 0>
class Queue{
public:
Queue();

bool is_empty()const;
bool is_full()const;

void enqueue(const T&);
T dequeue();

void traverse()const;
private:
T storge[size];
int first;
int last;
};

template<typename T, int size>
Queue<T, size>::Queue()
{
first = last = -1;
}

template<typename T, int size>
bool Queue<T, size>::is_empty()const
{
return first == -1;
}

template<typename T, int size>
bool Queue<T, size>::is_full()const
{
return first == 0 && last == size - 1 || last == first - 1;
}

template<typename T, int size>
void Queue<T, size>::enqueue(const T& elem)
{
if(!is_full()){
if(last == -1 || last == size -1){
storge[0] = elem;
last = 0;
if(first == -1)
first = 0;
}
else storge[++last] = elem;
}
else{
cout << "Queue full." << endl;
exit(EXIT_FAILURE);
}
}

template<typename T, int size>
T Queue<T, size>::dequeue()
{
if(is_empty()){
cout << "Queue empty." << endl;
exit(EXIT_FAILURE);
}

T tmp;

tmp = storge[first];
if(first == last)
last = first = -1;
else if(first == size - 1)
first = 0;
else ++first;

return tmp;
}

template<typename T, int size>
void Queue<T, size>::traverse()const
{
for(auto i=first; i<=last; ++i)
cout << storge[i] << " ";
cout << endl;
}

#endif
下面是测试程序：
#include "array_queue.h"

int main()
{
Queue<int, 3> queue;

queue.enqueue(10);
queue.enqueue(10);
+/-queue.enqueue(10);
cout << queue.is_full() <<endl;

queue.traverse();

queue.dequeue();
queue.dequeue();
queue.dequeue();

queue.is_empty();
queue.traverse();
}

测试结果如图：

C++实现队列--数组实现和链表实现

二：队列的链表实现

由于链表实现和数组实现类似，不做仔细介绍，在这里链表采用的是STL标准模版库中的list。 队列的链表实现代码如下： 
#ifndef _LIST_QUEUE_H
#define _LIST_QUEUE_H

#include <list>
#include <iostream>
using namespace::std;

template<class T>
class Queue{
public:
Queue() = default;

bool is_empty()const;
T& front();

T dequeue();
void enqueue(const T&);

size_t size()const;
void clear();
private:
list<T> lst;
};

template<class T>
bool Queue<T>::is_empty()const
{
return lst.is_empty();
}

template<typename T>
T& Queue<T>::front()
{
return lst.front();
}

template<typename T>
T Queue<T>::dequeue()
{
if(!lst.size()){
cout << "Queue empty." << endl;
exit(EXIT_FAILURE);
}

T tmp = lst.front();
lst.pop_front();

return tmp;
}

template<typename T>
void Queue<T>::enqueue(const T& elem)
{
lst.push_back(elem);
}

template<typename T>
void Queue<T>::clear()
{
lst.clear();
}

template<typename T>
size_t Queue<T>::size()const
{
return lst.size();
}

#endif

*本文所有程序均经过测试。
标签：

相关文章