数据结构与算法javascript描述-第四章（栈）

• 栈是一种特殊的列表，栈内元素只能通过列表的一端访问，这一端称为栈顶。
• 在第三章中，通过front()和end()函数，可以对列表的两端进行访问。
• 栈是一种后入先出的数据结构。
  不要局限于日常开发中使用到数组的push和pop方法，那只是特殊情况

1、栈的抽象数据类型定义

属性：

• 记录栈顶的位置(top)

功能：

• 将元素压入栈（push）
• 将元素弹出栈(pop)
• 返回栈顶元素而不删除(peek)
• 清除栈内所有元素（clear）
• 栈内元素的个数（length）

2、栈的实现

// 定义栈的构造函数，Stack类
function Stack() {
    this.top = 0;
    this.dataStore = []; // 保存栈内元素
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.length = length;
    this.clear = clear;
}

function push(ele) {
    this.dataStore[this.top] = ele;
    this.top++;
    console.log('top = ', this.top)
}

function pop() {
    this.top--;
    console.log('pop top = ', this.top)
    let popedEle = this.dataStore[this.top] // 这里是我自己加的，书中代码pop之后，dataStore数组的值没有变少。
    this.dataStore.length = this.top
    return popedEle;
}

function peek() {
    return this.dataStore[this.top - 1]; // 这里只是预览，数组长度不变
}

function length() {
    return this.top;
}

function clear() {
    this.top = 0
    this.dataStore.length = this.top; // 清空，dataStore数组应该也为空
}
// 测试栈
var s = new Stack()
s.push('a')
s.push('b')
s.push('c')
s.push('d')
console.log('after push s = ', s.dataStore)
var poped = s.pop()
console.log('poped ele = ', poped)
console.log('after poped s = ', s.dataStore)
var peeked = s.peek()
console.log('peeked ele = ', peeked)
console.log('after peeked s = ', s.dataStore)
var len = s.length()
console.log('s.length = ', len)
s.clear()
console.log('after clear s = ', s.top)

测试结果如图：