在面向对象的程序设计里，一般都提供了实现队列（queue）和栈（stack）的方法，我们可以通过数组的相关操作，来实现队列和栈的功能。
1.栈方法
栈是一种LIFO（Last-In-First-Out，后进先出）的数据结构。
栈中项的插入和移除，只发生在一个位置----栈的顶部。
ECMA为数组专门提供了push()和pop()方法，以便实现类似栈的行为。
push()方法可以接收任意数量的参数，把他们逐个添加到数组末尾，并返回修改后数组的长度；
pop()方法从数组末尾移除最后一项，减少数组的length，然后返回移除的项；
如下图所示：
2.队列方法
队列数据结构的访问规则是（First-In-First-Out,先进先出）。
对列在列表的末端添加项，从列表的前端移除项。
结合使用shift()和push()方法，可以像使用队列一样使用数组。
shift()方法，能移除数组中的第一个项并返回该项，同时数组的长度减1；
2.1反向队列：
ECMA还为数组提供了一个unshift()方法。
同时使用unshift()和pop()方法，可以从相反的方向来模拟队列，即在数组的前端添加项，从数组末端移除项。
unshift()它能在数组前端添加任意个项并返回新数组的长度；
2.2 实现队列
function LinkedQueue () {
//节点结构定义
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
front,//队首指针
rear;//队尾指针
//入队操作
this.push = function(element){
var node = new Node(element),
current;
if(length == 0){
front = node;
rear = node;
length++;
return true;
}else{
current = rear;
current.next = node;
rear = node;
length++;
return true;
}
}
//出队操作
this.pop = function(){
if(!front){
return 'Queue is null';
}else{
var current = front;
front = current.next;
current.next = null;
length--;
return current;
}
}
//获取队长
this.size = function(){
return length;
}
//获取队首
this.getFront = function(){
return front;
}
//获取队尾
this.getRear = function(){
return rear;
}
this.toString = function(){
var str = '',
current = front;
while(current){
str += current.element;
current = current.next;
}
return str;
}
//清除队列
this.clear = function(){
front = null;
rear = null;
length = 0;
return true;
}
}
2.3实现栈
function LinkedStack(){ /*链栈的JS实现*/
//节点结构定义
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
top; //栈顶指针
this.push = function(element){ //压栈操作
var node = new Node(element),
current;
if(!top){
top = node;
length++;
return true;
}else{
node.next = top;
top = node;
length++;
return true;
}
}
this.pop = function(){ //退栈操作
var current = top;
if(top){
top = current.next;
current.next = null;
length--;
return current;
}else{
return 'null stack';
}
}
//获取栈顶节点
this.top = function(){
return top;
}
//获取栈长
this.size = function(){
return length;
}
this.toString = function(){
var string = '',
current = top;
while(current){
string += current.element;
current = current.next;
}
return string;
}
this.clear = function(){ //清空栈
top = null;
length = 0;
return true;
}
}
function ArrayStack(){ //顺序栈的JS实现 这里直接使用了JS内置的Array对象
var arr = [];
this.push = function(element){ //压栈操作
arr.push(element);
}
this.pop = function(){ //退栈操作
return arr.pop();
}
this.top = function(){ //获取栈顶元素
return arr[arr.length-1];
}
this.size = function(){ //获取栈长
return arr.length;
}
this.clear = function(){ //清空栈
arr = [];
return true;
}
this.toString = function(){
return arr.toString();
}
}
2.4 两个队列实现一个栈
2.4 两个栈实现一个队列
以后补充，懒得写了
网友评论