36数据结构-队列的概念与实现（上)

发表于

一.队列的概念与与特性

1.1 队列的概念

队列是一种特殊的线性表，仅仅可以再线性表的两端进行操作，为队头队尾

  • 队头(front):取出的数据的一端
  • 队尾(rear):插入数据的一端

1.2 队列的特性

队列的特性先进先出，类似于生活中的排队
在这里插入图片描述

二.队列的实现要点

2.1 队列的顶层父类实现

Queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码#ifndef QUEUE_H
#define QUEUE_H

#include "Object.h"

namespace DTLib
{

template < typename T >
class Queue : public Object
{
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

2.2 队列的继承关系

队列分为静态队列和链式队列，继承顶层父类即可
在这里插入图片描述

2.3 静态队列的实现要点

  • 使用原生数组作为队列的存储空间
  • 使用模板参数作为队列的最大容量
  • front是队头标识
  • rear表示队尾标识
    在这里插入图片描述

三.静态队列的接口实现

3.1 初始化

1
2
3
4
5
6
c复制代码staticQueue()
{
	m_front = 0;
	m_rear = 0;
	m_length = 0;
}

3.2 入队列

先判断队列长度是否大于容量,没有则在队尾标识的位置出插入元素，队尾标识往后移一位

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码void add(const T& e)
{
	if (m_length < N)
	{
		m_space[m_rear] = e;
		m_rear = (m_rear + 1) % N;
		m_length++;
	}
	else
	{
		cout << "not space to add" << endl;
	}
}

3.3 出队列

先判断队列是否有元素，如果有，那么直接将队头m_front指向的元素加1，表示队头元素被移出队列

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码void remove()
{
	if (m_length > 0)
	{
		m_front = (m_front + 1) % N;//标识m_front指向的元素出队列了
		m_length--;
	}
	else
	{
		cout << "not elem to remove" << endl;
	}
}

3.4 获取队头元素

1
2
3
4
5
6
7
8
9
10
11
c复制代码T front() const
{
	if (m_length > 0)
	{
		return m_space[m_front];
	}
	else
	{
		cout << "not elem to get" << endl;
	}
}

3.5 清空操作/队列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码void clear()
{
	if (m_length > 0)
	{
		m_front = 0;
		m_rear = 0;
	}
}

int size()
{
	return m_length;
}

3.6 队满

表示长度为N,由于是循环计数所以还需要加上队头与队尾相等

1
2
3
4
c复制代码bool full()
{
	return (m_length == N) && (m_front == m_rear);
}

3.7 队空

1
2
3
4
c复制代码bool empty()
{
	return (m_length == 0)&&(m_front == m_rear);
}

四.完整代码

Queue.h

1
2
3
4
5
6
7
8
9
10
11
c复制代码#pragma once
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  size() = 0;
};

staticQueue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
c复制代码#pragma once
#include "Queue.h"
#include <iostream>

using namespace std;

template<class T,int N>
class staticQueue :public Queue<T>
{
protected:
	T m_space[N];
	int m_front;
	int m_rear;
	int m_length;
public:
	staticQueue()
	{
		m_front = 0;
		m_rear = 0;
		m_length = 0;
	}


	void add(const T& e)
	{
		if (m_length < N)
		{
			m_space[m_rear] = e;
			m_rear = (m_rear + 1) % N;
			m_length++;
		}
		else
		{
			cout << "not space to add" << endl;
		}
	}

	void remove()
	{
		if (m_length > 0)
		{
			m_front = (m_front + 1) % N;//标识m_front指向的元素出队列了
			m_length--;
		}
		else
		{
			cout << "not elem to remove" << endl;
		}
	}

	T front() const
	{
		if (m_length > 0)
		{
			return m_space[m_front];
		}
		else
		{
			cout << "not elem to get" << endl;
		}
	}

	void clear()
	{
		if (m_length > 0)
		{
			m_front = 0;
			m_rear = 0;
		}
	}

	int size()
	{
		return m_length;
	}

	bool empty()
	{
		return (m_length == 0)&&(m_front == m_rear);
	}

};

测试代码
staticQueue.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码#include <iostream>
#include "staticQueue.h"

int main()
{
	staticQueue<int, 5> queue;

	for (int i = 0; i < 5; i++)
	{
		queue.add(i);
	}

	for (int i = 0; i < 5; i++)
	{
		cout << queue.front() << endl;
		queue.remove();
	}

	return 0;
}

结果：

image.png

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%