javascript数据结构--列表和栈的创建
文章目录
一
列表是一组有序的数据。每个列表中的数据项称为元素。在 JavaScript 中,列表中的元素 可以是任意数据类型。列表中可以保存多少元素并没有事先限定,实际使用时元素的数量 受到程序内存的限制。
不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的 length。在内部实 现上,用一个变量 listSize 保存列表中元素的个数。可以在列表末尾 append 一个元素, 也可以在一个给定元素后或列表的起始位置 insert 一个元素。使用 remove 方法从列表中 删除元素,使用 clear 方法清空列表中所有的元素。
列表的抽象数据类型定义(后续列表上传)
代码:
function List() {
this.listSize = 0;
this.pos = 0;
this.dataStore = [];
this.clear = clear;
this.find = find;
this.toString = toString;
this.insert = insert;
this.append = append;
this.remove = remove;
this.front = front;
this.end = end;
this.prev = prev;
this.next = next;
this.length = length;
this.currPos = currPos;
this.moveTo = moveTo;
this.getElement = getElement;
this.length = length;
this.contains = contains;
}
function front() {
this.pos = 0;
}
function end() {
this.pos = this.listSize-1;
}
function prev() {
if (this.pos > 0) {
--this.pos;
}
}
function next() {
if (this.pos < this.listSize-1) {
++this.pos;
}
}
function currPos() {
return this.pos;
}
function moveTo(position) {
this.pos = position;
}
function getElement() {
return this.dataStore[this.pos];
}
二
栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。咖啡厅内 的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞 在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。
由于栈具有后入先出的特点,所以任何不在栈顶的元素都无法访问。为了得到栈底的元 素,必须先拿掉上面的元素。
对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push() 方法,出 栈使用 pop() 方法。
另一个常用的操作是预览栈顶的元素。pop() 方法虽然可以访问栈顶的元素,但是调用该方 法后,栈顶元素也从栈中被永久性地删除了。peek() 方法则只返回栈顶元素,而不删除它。
push()、pop() 和 peek() 是栈的 3 个主要方法,但是栈还有其他方法和属性。clear() 方法 清除栈内所有元素,length 属性记录栈内元素的个数。我们还定义了一个 empty 属性,用 以表示栈内是否含有元素,不过使用 length 属性也可以达到同样的目的。
代码
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 peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论