数据结构-队列

      本次队列用到的Node.cpp

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
template<typename T>
class Node {
public:
Node() {}
Node(T data, Node<T> *nextptr) :data(data), next(nextptr) {
}
~Node() {}
T getData();
void setData(T newData);
Node<T> *getNext();
void setNext(Node<T> *ptr);
private:
T data;
Node<T> *next;
};
template<typename T>
T Node<T>::getData() {
return data;
}
template<typename T>
void Node<T>::setData(T newData) {
data = newData;
}
template<typename T>
Node<T> *Node<T>::getNext() {
return next;
}
template<typename T>
void Node<T>::setNext(Node<T> *ptr) {
next = ptr;
}

      LinkQueue.cpp

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
83
84
85
86
87
88
89
90
91
92
#include"Node.cpp"
#include<iostream>
template<typename T>
class LinkQueue {
public:
LinkQueue();
LinkQueue(T array[], int n);
~LinkQueue();
void EnQueue(T x);
T DeQueue();
T GetQueue();
bool QueueEmpty();
private:
Node<T> *front; //队头指针,指向头节点
Node<T> *rear; //队尾指针,指向终端节点
};
template<typename T>
LinkQueue<T>::LinkQueue() {
Node<T> *s = new Node<T>;
s->setNext(NULL);
front = s;
rear = s;
}
template<typename T>
LinkQueue<T>::LinkQueue(T array[], int n) {
Node<T> *s;
front = new Node<T>;
rear = front;
rear->setNext(NULL);
for (int i = 0; i < n; i++) {
s = new Node<T>;
s->setData(array[i]);
s->setNext(NULL);
rear->setNext(s);
rear = s;
}
}
template<typename T>
LinkQueue<T>::~LinkQueue() {
Node<T> *p = front;
Node<T> *q = p->getNext();
while (q != NULL) {
delete p;
p = q;
q = q->getNext();
}
delete p; //删除最后一个节点
}
template<typename T>
void LinkQueue<T>::EnQueue(T x) {
Node<T> *s = new Node<T>;
s->setData(x);
s->setNext(NULL);
rear->setNext(s);
rear = s;
}
template<typename T>
T LinkQueue<T>::DeQueue() {
Node<T> *s;
if (rear == front) {
throw "链表为空!";
}
else {
s = front->getNext();
T x = s->getData();
front->setNext(s->getNext());
if (s->getNext() == NULL) {
rear = front;
}
delete s;
return x;
}
}
template<typename T>
T LinkQueue<T>::GetQueue() {
if (rear == front) {
throw "链表为空!";
}
else {
return front->getNext()->getData();
}
}
template<typename T>
bool LinkQueue<T>::QueueEmpty() {
if (front == rear) {
return true;
}
else {
return false;
}
}

      CirQueue.cpp

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
const int QueueSize = 5;
template<typename T>
class CirQueue {
public:
CirQueue();
~CirQueue() {};
void EnQueue(T x);
T DeQueue();
T GetQueue();
private:
T data[QueueSize];
int front, rear;
};
template<typename T>
CirQueue<T>::CirQueue() {
rear = front = QueueSize - 1;
}
template<typename T>
void CirQueue<T>::EnQueue(T x) {
if ((rear + 1) % QueueSize == front) {
throw "队列已满!";
}
else {
rear = (rear + 1) % QueueSize;
data[rear] = x;
}
}
template<typename T>
T CirQueue<T>::DeQueue() {
if (rear == front) {
throw "队列已空!";
}
else {
front = (front + 1) % QueueSize;
return data[front];
}
}
template<typename T>
T CirQueue<T>::GetQueue() {
if (rear == front) {
throw "队列已空!";
}
else {
int i = (front + 1) % QueueSize;
return data[i];
}
}

文章目录
|