棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。

棧

允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素稱為空棧。棧是后進(jìn)先出的線性表，稱為 LIFO 結(jié)構(gòu)。
棧的插入操作，叫作進(jìn)棧(壓?；蛉霔?，棧的刪除操作，叫作出棧(彈棧)。

棧的順序存儲(chǔ)結(jié)構(gòu)

js 代碼

class SqStack {
    constructor() {
        this.data = [];
        this.top = 0;
    }
}

function push(sqStack, e) {
    sqStack.top += 1
    sqStack.data.push(e);
}

function pop(sqStack, e) {
    if (sqStack.top === 0) {
        throw new Error('已經(jīng)到棧底')
    }
    sqStack.top-=1;
    return sqStack.data.pop();
}

push 和 pop 的時(shí)間復(fù)雜度都是 O(1)。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈棧。

js 代碼

class StackNode {

    constructor(data, next) {
        this.data = data;
        this.next = next;
    }
}

class LinkStack {
    constructor(top) {
        this.top;
        this.count = 0;
    }
}

function createLinkStack() {
    let linkStack = new LinkStack(null);
    return linkStack;
}

function push(linkStack, e) {
    let newNode = new StackNode(e);
    newNode.next = linkStack.top;
    linkStack.top = newNode;
    linkStack.count += 1;
}

function pop(linkStack) {
    if (linkStack.count === 0) {
        throw new Error('已經(jīng)到棧底');
    }
    let data = linkStack.top.data;
    linkStack.top = linkStack.top.next;
    linkStack.count-=1;
    return data;
}

let linkStack = createLinkStack();
push(linkStack, 10);
push(linkStack, 5);

console.log(pop(linkStack));
console.log(pop(linkStack));

鏈棧的 push 和 pop 的事件復(fù)雜度都是 O(1)。

如果棧的使用過(guò)程中元素變化不可預(yù)測(cè)，有時(shí)很小，有時(shí)非常大，那么最好是用鏈棧，反之，如果它的變化在可控范圍內(nèi)，建議是用順序棧。

棧的應(yīng)用－－遞歸

一個(gè)直接調(diào)動(dòng)自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。
每個(gè)遞歸定義必須有一個(gè)條件，滿足時(shí)遞歸不再進(jìn)行，即不再引用自身而是返回值退出。