数据结构之队列

队列(Queue)是一种先进先出的数据结构,和栈(Stack)结构基本一致,只是修改了出栈逻辑,出栈改为从栈底出,而不是栈头。

相关解释可参考:文章

队列

主要方法

  • 入列 队列

  • 出列 队列

队列分类

和栈的分类一样,队列也可以分为顺序存储结构和链式存储结构,我们只需要将栈的出栈逻辑从后进先出改为先进先出即可。

顺序存储结构

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
function Queue() {

// 队列数据
this.data = [];

// 入列
this.push = function(data) {
this.data.push(data);
}

// 出列
this.pop = function() {
if (this.empty()) return null;
else return this.data.shift();
}

// 判断是否为空
this.empty = function() {
if (this.data.length == 0) return true;
else return false;
}

// 查看队列中元素总数
this.length = function() {
return this.data.length;
}

// 清空队列
this.clear = function() {
this.data = [];
}

this.toString = function() {
return this.data.join(',')
}

}

链式存储结构

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 栈(堆栈)stack
// 先进后出,后进先去

function Node(data) {
this.data = data;
this.next = null;
}

function LinkList() {

head = null;

length = 0;

// 在链表最后添加节点
this.push = function(data) {
var node = new Node(data);
if (head == null) {
head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
}

length++;
}


// 从链表头部移除节点
this.pop = function() {
next = head.next;
head = null;
head = next
length--;
}

// 清空节点
this.clear = function() {
var current = head;
var previous;
while(current.next) {
previous = current;
current = current.next;
// 清空前一个节点
previous = null;
head = current;
length--;
}
// 清空最后一个节点
current = null;
length--;
}

this.size = function() {
return length;
}

// 遍历节点
this.toString = function() {
var str = head.data;
var current = head.next;

while (current) {
str += ','+ current.data;
current = current.next;
}

return str;
}

}

function Queue() {

// 栈数据
this.data = new LinkList();

// 入栈
this.push = function(data) {
this.data.push(data);
}

// 出栈
this.pop = function() {
if (this.empty()) return null;
else return this.data.pop();
}

// 判断是否为空
this.empty = function() {
if (this.data.size() == 0) return true;
else return false;
}

// 查看栈中元素总数
this.length = function() {
return this.data.size();
}

// 清空栈
this.clear = function() {
this.data.clear();
}

this.toString = function() {
return this.data.toString();
}

}
有用就打赏一下作者吧!