【www.bbyears.com--网页配色】
javascript： 栈
列表是一种最自然的数据组织方式。栈就是和列表类似的一种数据结构，它可以用来解决计算机世界里很多的问题。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言的方方面面，从表达式求值到处理函数调用。
一：对栈的操作
栈是一种特殊列表，栈内的元素只能通过列表的一端访问，这一端被称为栈顶。咖啡厅的一摞盘子是现实世界中最常见的栈的例子。只能从上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈被称为一种后入先出（LIFO,last-in-first-out）的数据结构。
由于栈具有后入先出的特点，所有任何不在栈顶的元素都无法访问，为了拿到栈底的元素，必选先拿掉上面的元素。如图：
对于栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈，入栈使用push()方法。出栈使用pop()方法。
另外一个常用操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶的元素也从栈中永久的删除了。peek()方法则只返回栈顶元素，而不删除它。
为了记录栈顶元素的位置，同时也为了标记哪里可以增加新的元素。我们使用变量top,当向栈内压入元素时，该变量增大，从栈内弹出元素时，该变量减小。
push(),pop()和peek()是栈的三个主要操作方法，但是栈还有其他的方法和属性。clear()方法清除栈内所有元素，length属性记录栈内元素的个数。我们还定义了一个empty属性，用于表示栈内是否还有元素（使用length也可以达到同样的目的）。
二：栈的实现：
实现一个栈，当务之急是决定存储数据的底层数据结构。这里采用的是数组。
我们实现以Stack类的构造函数开始：
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
}
我们使用数组dataStore保存栈内元素，构造函数将其初始化为一个空数组，变量top记录栈顶的位置，被构造的函数初始化为0，表示栈顶对于数组的起始位置为0.如果有元素压入栈，该变量的值随之变化。
先来实现push()方法。当向栈内压入一个新元素时，需要将其保存在数组中top所对应的位置，然后将top加1.让其指向数组中的下一个空位置。
function push (element) {
this.dataStore[this.top++] = element;
}
这里特别要注意++操作符的位置，它放在this.top的后面，这样新入栈的元素就被放在top的当前值对应的位置，然后再将top值加1.指向下一个位置。
pop()方法恰好与push()方法相反,它返回栈顶元素，同时将变量top的值减1.
function pop() {
return this.dataStore[--this.top]
}
peek()方法返回数组的第top-1个位置的元素，即栈顶元素：
function peek() {
return this.dataStore[this.top - 1]
}
如果对空数组调用peek()方法，结果为undefined。这是因为栈是空的，栈顶没有任何元素。
有时候需要知道栈内存储了多个元素。length()方法通过返回变量top值返回栈内元素的个数；
function length() {
return this.top
}
最后，可以将top的值设置为0，轻松清空一个栈。
function clear() {
this.top = 0;
}
附：测试代码
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
//压入栈
function push (element) {
this.dataStore[this.top++] = element;
}
//弹出栈
function pop() {
return this.dataStore[--this.top]
}
//栈顶元素
function peek() {
// if (this.dataStore[this.top - 1] == undefined) {
// return "none"
// }
return this.dataStore[this.top - 1]
}
//清空栈
function clear() {
this.top = 0;
}
//栈元素个数
function length() {
return this.top
}
var newstak = new Stack();
newstak.push("牛牛")
newstak.push("豆豆")
newstak.push("花花")
console.log(newstak.length())
console.log(newstak.peek())
var poped = newstak.pop();
console.log(poped);//
console.log(newstak.peek());//
newstak.clear();
console.log(newstak.length())
console.log(newstak.peek());
newstak.push("羊羊");
console.log(newstak);
console.log(newstak.peek());
三.使用Stack类
有一些问题特别适合用栈来解决，先介绍几个例子：
1.数制间互相转换
可以利用栈将一个数字从一种数值转换成另一种数制。假设想将数字n转换为以b为基数的数字。实现转换算法如下：
1.最高位为 n % b ,将此位压入栈
2.使用n / b 代替n
3.重复步骤1和2，直到n等于0,且没有余数。
4.持续将栈内元素弹出，直到栈为空。依次将这些元素排列，就得到转换后数字的字符串形式。
（此算法只征对基数为2-9的情况）
使用栈，在javascript中实现该算法就很容易，下面就是该函数的定义，可以将数字转化为二至九进制的数字。
function mulBase(num, base) {
var s = new Stack();
do {
s.push(num % base);
num = Math.floor(num /= base);
} while (num > 0);
var converted = "";
while(s.length() > 0) {
converted += s.pop()
}
return converted;
}
下面展示了如果使用该方法将数字转换为二进制和八进制数。
将数字转换为二进制和八进制。
function mulBase(num, base) {
var s = new Stack();
do {
s.push(num % base);
num = Math.floor(num /= base);
} while (num > 0);
var converted = "";
while(s.length() > 0) {
converted += s.pop()
}
return converted;
}
var num = 32;
var base = 2;
var newNum = mulBase(num, base);
//32 converted to base 2 is 100000
console.log(num + " converted to base " + base + " is " + newNum)
num = 125;
base = 8;
var newNum = mulBase(num, base);
//125 converted to base 8 is 175
console.log(num + " converted to base " + base + " is " + newNum)
2.回文。
回文是这样一种现象：一个单词，短语或数字，从前往后写和往后写都是一样的。比如： 单词"dad","racecar"就是回文。如果忽略空格和标点符号，下面的句子也是回文。“A man, a plan, a canal:Panama”; 数字1001也是回文。
使用栈，可以轻松判断一个字符串是否回文。我们将拿到的自字符串的每个字符按照从左至右的顺序压入栈。当字符串的字符都入栈后，栈内就保存了一个反转的字符串，最后的字符串在栈顶，第一个字符串在栈底。
字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需比较两个字符串即可。如果他们相等，就是一个回文。
例子：判断给定字符串是否回文。
function isPalindrome(word) {
var s = new Stack();
for (var i = 0; i < word.length; ++i) {
s.push(word[i]);
}
var word = "";
while(s.length() > 0) {
rword += s.pop();
}
if (word == rword) {
return true;
}
else {
return false;
}
}
var word = "hello";
if (isPalindrome(word)) {
console.log(word + " 是回文的");
} else {
console.log(word + " 不是回文的")
}
var word = "racecar";
if (isPalindrome(word)) {
console.log(word + " 是回文的");
} else {
console.log(word + " 不是回文的")
}
三：递归演示；
栈常用来实现编程语言，使用栈实现递归即为一例（这里只用栈来模拟递归过程）。
为了演示如何用栈实现递归，考虑以下求阶乘的递归定义。首先看看5的阶乘是如何定义的
5! = 5*4*3*2*1 = 120
下面是一个递归函数，可以计算任何数字的阶乘
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1)
}
}
使用栈来模拟计算5的阶乘，返回120
使用栈来模拟计算5！的过程，首先将数字从5到1压入栈，然后使用一个循环，将数字弹出连乘，就得到了5 的阶乘
function fact(n) {
var s = new Stack();
while (n > 1) {
s.push(n--);
}
var product = 1;
while(s.length() > 0) {
product *= s.pop()
}
return product;
}
javascript：队列
队列是一种列表，不同的是队列只能在末尾插入元素，在队首删除元素。队列用于存储俺顺序排列的数据。先进先出。这点和栈不一样，在栈中，最后入栈的元素反被优先处理。可以将队列想象成银行排队办理业务的人，排队在第一个的人先办理业务，其它人只能排着，直到轮到他们为止。
队列是一种先进先出（FIFO）的数据结构。队列被用在很多地方。比如提交操作系统执行一系列进程。打印任务池等。一些仿真系统用来模拟银行或杂货店里排队的顾客。
一，队列的操作。
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队。删除元素也叫做出队。入队是在末尾插入新元素，出队是删除队头的元素。
队列的另外一项操作是读取队头的元素，这个操作叫peek()。该操作返回队头的元素，但不把它从队列中删除。除了读取队头的元素，我们想知道队列中有多少元素，可以使用length属性满足要求；要想清空队列中所有元素。可以使用clear()方法来实现。
二，一个数组实现的队列。
使用数组来实现队列看起来顺理成章。javascript中的数组具有其它编程语言中没有的优点，数组的push()可以在数组末尾加入元素，数组的shift()方法则可以删除数组的第一个元素。
push()方法将它的参数插入数组中第一个开放的位置，该位置总在数组的末尾，即使是个空数组也是如此。
names = [];
names.push("Cny");
names.push("Jen");
console.log(names);//["Cny", "Jen"]
然后使用shift()方法删除数组的第一个元素：
names.shift();
console.log(names);//["Jen"]
准备开始实现Queue类。先从构造函数开始：
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
enqueue()方法向队末尾添加一个元素：
function enqueue(element) {
this.dataStore.push(element)
}
dequeue方法删除队首的元素
function dequeue() {
return this.dataStore.shift();
}
可以使用以下方法读取队首和队末的元素
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1]
}
还需要toString()方法显示队列内的所有元素
function toString() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i ) {
retStr += this.dataStore[i] + "\n";
}
return retStr
}
最后，需要一个方法判断队列是否为空
function empty() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
Queue类的定义和测试
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
//向队末尾添加一个元素
function enqueue(element) {
this.dataStore.push(element)
}
//删除队首的元素
function dequeue() {
return this.dataStore.shift();
}
function front() { //读取队首和队末的元素
return this.dataStore[0];
}
function back() { ////读取队首和队末的元素
return this.dataStore[this.dataStore.length - 1]
}
//显示队列内的所有元素
function toString() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i ) {
retStr += this.dataStore[i] + "\n";
}
return retStr
}
//队列是否为空
function empty() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
//测试程序
var q = new Queue();
q.enqueue("Me");
q.enqueue("Her");
q.enqueue("His");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("第一个元素是： " + q.front());
console.log("最后一个元素是： " + q.back())
三，使用队列，方块舞和舞伴的分配问题
前面我们提到过，经常用队列模拟排队的人。下面，我们使用队列来模拟跳方块舞的人。当男男女女来到舞池，他们按照自己的性别排成两队。当舞池中有地方空出来的时候，两个队列中的第一个人组成舞伴。他们身后的人各自向前一位，组成新的队首。当一对新的舞伴进入舞池时，主持人会大喊出他们的名字。当一对舞伴走出舞池，且两队队伍任意一队没有人时，主持人会把这个情况告诉大家。
为了模拟这个情况，我们将男男女女姓名存储在一个文本文件。
女 小李
男 福来
男 强子
男 李勇
女 小梅
男 来福
女 艾丽
男 张帆
男 文强
男 丁力
女 娜娜
每个舞者的信息都被保存在一个Dancer对象中：
function Dancer(name, sex) {
this.name = name;
this.sex = sex;
}
我们需要一个函数，将舞者的信息读到程序中来。
function getDancers(males, females) {
//var names = _names.split("\n");
var names = _names.split("**");
for (var i = 0; i < names.length; ++i) {
names[i] = names[i].trim();
}
for (var i = 0; i < names.length; ++i) {
var dancer = names[i].split(" ");
var sex = dancer[0];
var name = dancer[1];
if (sex == "女") {
females.enqueue(new Dancer(name, sex));
} else {
males.enqueue(new Dancer(name, sex))
}
}
}
此函数将舞者按照性别分在不同的队列中。
下一个函数将男性和女性组成舞伴，并宣布配对结果:
function dance(males, females) {
console.log("这组舞伴是:")
while (!females.empty() && !males.empty()) {
person = females.dequeue();
console.log("女舞者是" + person.name);
person = males.dequeue();
console.log("男舞者是" + person.name);
}
}
我们可能对该程序做修改，想显示排队时男性女性的数量，队列中目前没有显示元素个数的方法。现在加入
function count(){
return this.dataStore.length;
}
综合测试：
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
//向队末尾添加一个元素
function enqueue(element) {
this.dataStore.push(element)
}
//删除队首的元素
function dequeue() {
return this.dataStore.shift();
}
function front() { //读取队首和队末的元素
return this.dataStore[0];
}
function back() { ////读取队首和队末的元素
return this.dataStore[this.dataStore.length - 1]
}
//显示队列内的所有元素
function toString() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i ) {
retStr += this.dataStore[i] + "\n";
}
return retStr
}
//队列是否为空
function empty() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
//队列个数
function count(){
return this.dataStore.length;
}
function Dancer(name, sex) {
this.name = name;
this.sex = sex;
}
function getDancers(males, females) {
//var names = _names.split("\n");
var names = _names.split("**");
for (var i = 0; i < names.length; ++i) {
names[i] = names[i].trim();
}
for (var i = 0; i < names.length; ++i) {
var dancer = names[i].split(" ");
var sex = dancer[0];
var name = dancer[1];
if (sex == "女") {
females.enqueue(new Dancer(name, sex));
} else {
males.enqueue(new Dancer(name, sex))
}
}
}
function dance(males, females) {
console.log("这组舞伴是:")
while (!females.empty() && !males.empty()) {
person = females.dequeue();
console.log("女舞者是" + person.name);
person = males.dequeue();
console.log("男舞者是" + person.name);
}
}
//测试程序
var _names = "女 小李**男 福来**男 强子**男 李勇**女 小梅**男 来福**女 艾丽**男 张帆**男 文强**男 丁力**女 娜娜";
var names = _names.split("**");
//测试程序
var maleDancer = new Queue();
var femaleDancer = new Queue();
getDancers(maleDancer, femaleDancer);
dance(maleDancer, femaleDancer)
if (!femaleDancer.empty()) {
console.log(femaleDancer.front().name + "正在等待跳舞")
}
if (!maleDancer.empty()) {
console.log(maleDancer.front().name + "正在等待跳舞")
}
//显示等待跳舞的人个数
var nanDancers = new Queue();
var nvDancers = new Queue();
getDancers(nanDancers, nvDancers)
dance(nanDancers,nvDancers);
if (nanDancers.count() > 0) {
console.log("有" + nanDancers.count() + "男舞者等待")
}
if (nvDancers.count() > 0) {
console.log("有" + mvDancers.count() + "女舞者等待")
}
四：使用队列对数据进行排序
队列不仅用于执行显示生活中与排队有关的操作，还可以用于对数据进行排序。计算机刚出现时，程序是通过穿孔卡输入主机的，每张卡包含一条程序语句。这些穿孔卡装在一个盒子里，经过一个继续装置进行排序。我们可以使用一组队列来模拟这一过程。这种技术叫基数排序。它不是最快的排序算法，但是它展示了一些有趣的队列使用方法。
对于0-99的数字，基数排序将数据扫描两次。第一次按个位上的数字进行排序，第二次按照十位上的数字进行排序。每个数字根据对于位上的数值被分在不同的盒子里。假设有如下数字：
91,46,85,15,92,35,31,22
经过基数排序第一次扫描后，数字被分配到以下盒子里
Bin 0 :
Bin 1 : 91, 31
Bin 2 : 82, 22
Bin 3 :
Bin 4 :
Bin 5 : 85, 35
Bin 6 : 46
Bin 7 :
Bin 8 :
Bin 9 :
根据盒子的顺序，对数字第一次排序的结果如下
91,31,92,22,85,15,25,46
根据十位上的数字，再次排序。
Bin 0 :
Bin 1 : 15
Bin 2 : 22
Bin 3 : 31, 35
Bin 4 : 46
Bin 5 :
Bin 6 :
Bin 7 :
Bin 8 : 85
Bin 9 : 91, 92
最后，将盒子中的数字去除，组成一个新的列表，该列表即为排好序的数字：
15, 22, 31, 35, 46, 85, 91, 92
使用队列代表盒子，可以实现这个算法。我们需要9个队列，每一个对应一个数字。所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应队列，根据个位数值对其从新排序，然后根据十位上的数值进行排序。结果即为排列好的数字
下面是根据 相应位(个位或十位)上的数值，将数字分配到相应队列的函数：
function distribute(nums, queues, n, digit) { //digit表示个位和十位上的值
for (var i = 0 ; i < n ; ++i) {
if (digit == 1) {
queues[nums[i]%10].enqueue(nums[i]);
} else {
queues[Math.floor(nums[i]/10).enqueue(nums[i])]
}
}
}
下面是从队列中收集数字的函数
function collect(queues, nums){
var i = 0;
for (var digit = 0; digit < 10; ++digit) {
while(!queues[digit].empty()){
nums[i++] = queues[digit].dequeue()
}
}
}
附上测试代码
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
//向队末尾添加一个元素
function enqueue(element) {
this.dataStore.push(element)
}
//删除队首的元素
function dequeue() {
return this.dataStore.shift();
}
function front() { //读取队首和队末的元素
return this.dataStore[0];
}
function back() { ////读取队首和队末的元素
return this.dataStore[this.dataStore.length - 1]
}
//显示队列内的所有元素
function toString() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i ) {
retStr += this.dataStore[i] + "\n";
}
return retStr
}
//队列是否为空
function empty() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
//队列个数
function count(){
return this.dataStore.length;
}
//基础排序程序
function distribute(nums, queues, n, digit) { //digit表示个位和十位上的值
for (var i = 0 ; i < n ; ++i) {
if (digit == 1) {
queues[nums[i]%10].enqueue(nums[i]);
} else {
queues[Math.floor(nums[i] / 10)].enqueue(nums[i])
}
}
}
function collect(queues, nums){
var i = 0;
for (var digit = 0; digit < 10; ++digit) {
while(!queues[digit].empty()){
nums[i++] = queues[digit].dequeue()
}
}
}
function dispArray(arr) {
for (var i = 0; i < arr.length; ++i) {
console.log(arr[i] + " ")
}
}
//主程序
var queues = []
for (var i = 0; i < 10; ++i) {
queues[i] = new Queue();
}
var nums = []
for (var i = 0; i < 10; ++i){
nums[i] = Math.floor(Math.floor(Math.random() * 101))
}
console.log("之前的基数：")
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums,queues, 10 ,10);
collect(queues, nums);
console.log("之后的基数：")
dispArray(nums)