栈和队列

是限定仅在表尾进行插入或删除操作的线性表。因此对于栈来说,表尾端有其特殊含义,称为栈顶(top), 表头端称为栈底(base)。因此,栈又称为后进先出的线性表。

栈的应用举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//行编辑器
function lineEdit(str) {
var stack = [];
for (var i = 0; i < str.length; i++) {
switch (str.charAt(i)) {
case "#": //#代表退一个
console.log("出栈" + stack.pop());
break;
case "@": //清空
console.log("清空" + stack);
stack = [];
break;
default: //压入
stack.push(str.charAt(i));
}
}
console.log(stack.join(""));
}
lineEdit("nihaoyaa#wohenhao");
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
//表达式求值
/*
四则运算的法则
1.先乘除,后加减
2. 从左算到右
3. 先括号内,再括号外
*/
function evaluateExpression(str) {
var num = {
"+": 0,
"-": 1,
"*": 2,
"/": 3,
"(": 4,
")": 5,
"#": 6
};
var pri = [ //各个运算符的优先级
[1, 1, -1, -1, -1, 1, 1],
[1, 1, -1, -1, -1, 1, 1],
[1, 1, 1, 1, -1, 1, 1],
[1, 1, 1, 1, -1, 1, 1],
[-1, -1, -1, -1, -1, 0, null],
[1, 1, 1, 1,null, 1, 1],
[-1,-1,-1,-1,-1,null,0]
];
function precede(firChar, secChar) { //比较输入的两个字符的优先级
var firNum = num[firChar],
secNum = num[secChar];
return pri[firNum][secNum];
}
var opNum = [], //操作数
opChar = ["#"], //操作符
i = 0;
while (str.charAt(i)!="#" || opChar[opChar.length-1]!="#") { //查询到最后的#则表示运算表达式结束
var numPush=""; //要压入的数字 可能是任何位数的数字
while (!(str.charAt(i) in num)) {
numPush+=str.charAt(i++); //拼接数字
}
if (numPush!=="") {
opNum.push(numPush); //如果numPush不为空,则压入
}
if ((str.charAt(i) in num)){ //如果当前位为运算符
var tmp = opChar[opChar.length - 1];
switch (precede(opChar[opChar.length - 1],str.charAt(i))) { //调用precede方法比较运算符优先级
case -1: //小于,则将运算符压入
opChar.push(str.charAt(i++));
break;
case 0:
opChar.pop(); //将运算符推出
i++;
break;
case 1:
var firstNum = opNum.pop(),
secondeNum = opNum.pop(),
optionChar = opChar.pop(),
var result = eval(secondeNum+optionChar+firstNum); //拼接运算表达式
opNum.push(result);
break;
}
}
}
return opNum[opNum.length-1];
}
console.log(evaluateExpression("1+2+2*(2+6/2)#"));

栈与递归的实现

通常,当在一个函数内,调用另外一个函数时,在运行被调用函数前,系统必须先完成3件事情,

  1. 将所有的实参,返回地址等信息传递给被调用函数保存
  2. 为被调用函数的局部变量分配存储区
  3. 将控制转移到被调用函数的入口
  4. 而被调用函数返回调用函数之前,系统也应该完成3件事情。
  5. 保存被调用函数的计算结果
  6. 释放被调用函数的数据区
  7. 依照被调用函数保存的返回地址将控制转移到调用函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//n阶汉尼塔
// n代表总共的圆盘数量,x,y,z代表3个hanoi塔
// 将x上的n个圆盘移到z上,并以y为辅助
function hanoi(n, x, y, z) {
if (n == 1) {
move(x, z);
} else {
hanoi(n - 1, x, z, y);
move(x, z);
hanoi(n-1, y, x, z);
}
}
var x = [9,8,7,6,5,4,3, 2, 1],
y = [],
z = [];
function move(x, z) {
var tmp = x.pop();
z.push(tmp);
}
hanoi(9, x, y, z);

队列 queue

和栈相反,队列是一种先进先出的线性表。他只允许在表的一端进行插入,而在另一端进行删除元素。 允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front)

链队列

循环队列

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
var waitQueue = [
[],
[],
[],
[]
], //等待队列
closeTime,
totolCus=0,
eventQueue = [], //事件列表
customQueue = [];
function Custom() {
this.arrivalTime = new Date();
this.nextCustom = Math.floor(Math.random() * 5);
this.duration = Math.floor(Math.random() * 30);
this.queue = ""; //排哪一队
this.leaveTime = function() {
this.leaveTime = new Date();
};
this.totalTime = function() {
if (typeof this.leaveTime !== "function") {
this.totalTime = Math.floor((this.leaveTime - this.arrivalTime) / 1000);
} else {
alert("离开时间尚未设定");
}
};
}
function Event(type) {
this.type = type;
this.custom = function() {
this.custom = new Custom();
};
}
//用户到达事件处理函数
function arrEvent(custom, waitQueue) {
var tmp = 0;
for (var i = 0; i < waitQueue.length; i++) {
if (waitQueue[tmp].length > waitQueue[i].length) {
tmp = i;
}
}
custom.queue = tmp; //达到后,将其插入排队
waitQueue[tmp].push(custom);
if (waitQueue[tmp].length == 1) {
setTimeout(function () {
leaveCus(waitQueue[tmp][0]);
}, waitQueue[tmp][0].duration);
}
}
// 用户离开事件处理函数
function leaveEvent(custom, waitQueue) {
custom.leaveTime(); //标志离开时间
custom.totalTime(); //计算总时间
customQueue.push(waitQueue[custom.queue].shift()); //将离开的用户压入用户数组中
if (waitQueue[custom.queue]) {
setTimeout(leaveCus(waitQueue[custom.queue][0]),waitQueue[custom.queue][0].duration);
}
}
//银行开业,初始化顾客
function openBank() {
var firEvent = new Event(0);
firEvent.custom();
eventQueue.push(firEvent);
startCus(firEvent.custom);
}
//生成用户到达事件,递归生成
function startCus(custom) {
setTimeout(function() {
var eventTmp = new Event(0);
eventTmp.custom(); //新建客户
if (eventTmp.custom.arrivalTime.getTime()>closeTime) {
console.log("不欢迎新顾客");
return "不欢迎新顾客";
}
eventQueue.push(eventTmp);
totolCus++;
startCus(eventTmp.custom);
}, custom.nextCustom);
}
// 生成用户离开事件,递归离开
function leaveCus(custom) {
var eventTmp = new Event(1);
eventTmp.custom = custom;
eventQueue.push(eventTmp);
// setTimeout(leaveCus(waitQueue[eventTmp.custom.queue][1]), waitQueue[eventTmp.custom.queue][1].duration);
}
function bankInit() {
closeTime = new Date();
closeTime = closeTime.getTime() + 1000;
openBank();
while (eventQueue) {
var ev = eventQueue.shift();
switch (ev.type) {
case 0:
arrEvent(ev.custom, waitQueue);
break;
case 1:
leaveEvent(ev.custom, waitQueue);
break;
default:
alert("事件无效");
}
}
}
分享 留言