摘要：線性結(jié)構(gòu)隊(duì)列與棧棧棧是一種遵循先進(jìn)后出原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。將字符串的每個(gè)字符按順序亞入棧。

棧(Stack)是一種遵循先進(jìn)后出(LIFO)原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。

# python3
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def size(self):
        return len(self.items)

    def clear(self):
        self.items = []

    def is_empty(self):
        return self.items == []

// ES6
class Stack {
    constructor() {
        this.items = [];
    }
    push(item) {
        this.items.push(item);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[-1];
    }
    size() {
        return this.items.length;
    }
    clear() {
        this.items = [];
    }
    isEmpty() {
        return this.items.length === 0;
    }
}

隊(duì)列(Queue)是一種遵循先進(jìn)先出(FIFO)原則的有序列表。隊(duì)列在尾部添加新元素，從頂部移除元素。最新添加的元素必須排列在隊(duì)列的末尾。

# python3
class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def front(self):
        return self.items[0]

    def size(self):
        return len(self.items)

    def clear(self):
        self.items = []
    
    def is_empty(self):
        return self.items == []

// ES6
class Queue {
    constructor() {
        this.items = [];
    }
    enqueue(item) {
        this.items.push(item);
    }
    dequeue() {
        return this.items.shift();
    }
    front() {
        return this.items[0];
    }
    size() {
        return this.items.length;
    }
    def clear() {
        this.items = [];
    }
    isEmpty () {
        return this.items.length === 0;
    }
}

回文是指一種現(xiàn)象，一個(gè)單詞、短語或數(shù)字，從前往后和從后往前都是一樣的。

# 單詞
dad
racecar
# 數(shù)字
1001

使用棧，可以輕松判斷一個(gè)字符串是否是回文。將字符串的每個(gè)字符按順序亞入棧。當(dāng)字符串中的字符都入棧后，棧內(nèi)就保存了一個(gè)反轉(zhuǎn)后的字符串。通過彈出棧內(nèi)每個(gè)字母可以得到一個(gè)新字符，只需要比較兩個(gè)字符串即可。

# python3
def palindrome(word):
    s = Stack()
    word = str(word)
    rword = ""

    for i in word:
        s.push(i)

    while not s.is_empty():
        rword += s.pop()
    
    return word == rword

// ES6
function palindrome(word) {
    let s = new Stack();
    word = String(word);
    let rword = "";
    for (i of word) {
        s.push(i);
    }
    while (! s.isEmpty()) {
        rword += s.pop();
    }
    return word === rword;
}

在表達(dá)式中，括號(hào)必須以匹配的方式出現(xiàn)。括號(hào)匹配意味著每個(gè)開始符號(hào)具有相應(yīng)的結(jié)束符號(hào)，并且括號(hào)能被正確嵌套。

(5+6)*(7+8)/(4+3)  # 括號(hào)匹配
(2+3)+24/12+(4-2   # 括號(hào)不匹配

?？梢杂脕砼袛嘁粋€(gè)表達(dá)式中的括號(hào)是否匹配。從空棧開始，從左到右處理表達(dá)式。如果一個(gè)符號(hào)是一個(gè)開始符號(hào)，將其作為一個(gè)信號(hào)，對(duì)應(yīng)的結(jié)束符號(hào)稍后會(huì)出現(xiàn)。另一方面，如果符號(hào)是結(jié)束符號(hào)，彈出棧，只要彈出棧的開始符號(hào)可以匹配每個(gè)結(jié)束符號(hào)，則括號(hào)保持匹配狀態(tài)。如果任何時(shí)候棧上沒有出現(xiàn)符合開始符號(hào)的結(jié)束符號(hào)，則字符串不匹配。最后，當(dāng)所有符號(hào)都被處理后，棧應(yīng)該是空的。

# python3
def par_checker(expression):
    s = Stack()
    balanced = True
    index = 0
    while index < len(expression) and balanced:
        symbol = expression[index]
        if symbol == "(":
            s.push(symbol)
        elif symbol == ")":
            item = s.pop()
            if item != "(":
                balanced = False
        index += 1
    return balanced and s.is_empty()

// ES6
function parChecker(expression) {
    let s = new Stack();
    let balanced = true;
    let index = 0;
    while (index < expression.length && balanced) {
        symbol = expression[index]
        if (symbol === "(") {
            s.push(symbol);
        } else if (symbol === ")") {
            let item = s.pop();
            if (item !== "(") {
                balanced = false;
            }
        }
        index += 1;
    }
    return balanced && s.isEmpty();
}

在生活中，我們主要使用十進(jìn)制數(shù)。但在計(jì)算科學(xué)中，二進(jìn)制非常重要，因?yàn)橛?jì)算機(jī)里的內(nèi)容都是用二進(jìn)制數(shù)字表示的(0和1)。如果沒有進(jìn)制轉(zhuǎn)化的能力，與計(jì)算機(jī)交流就會(huì)非常困難。

要把十進(jìn)制數(shù)轉(zhuǎn)化成二進(jìn)制的算法，將十進(jìn)制數(shù)與2相除，并取余數(shù)。

10 => 1010
10/2 = 5, rem = 0
 5/2 = 2, rem = 1
 2/2 = 1, rem = 0
 1/2 = 0, rem = 1

Python實(shí)現(xiàn)

# python3
def divide_by2(dec_str):
    s = Stack()
    dec_num = int(dec_str)
    bin_str = ""
    while dec_num > 0:
        rem = dec_num % 2
        s.push(rem)
        dec_num //= 2

    while not s.is_empty():
        bin_str += str(s.pop())

    return bin_str

同理，我們可以推導(dǎo)出十進(jìn)制數(shù)轉(zhuǎn)化八進(jìn)制和十六進(jìn)制算法。以下是完整的進(jìn)制轉(zhuǎn)換算法。

# python3
def base_converter(dec_str, base):
    s = Stack()
    digits = "0123456789ABCDEF"
    dec_num = int(dec_str)
    new_str = ""

    while dec_num > 0:
        rem = dec_num % base
        s.push(rem)
        dec_num //= base

    while not s.is_empty():
        new_str += digits[s.pop()]

    return new_str

// ES6
function baseConverter(decStr, base) {
    let s = new Stack();
    let digits = "0123456789ABCDEF";
    let decNum = Number(decStr);
    let newStr = "";
    while (decNum > 0) { 
        rem = decNum % base;
        s.push(rem)
        decNum = Math.floor(decNum/base);
    }
    while (! s.isEmpty()) {
        newStr += digits[s.pop()]
    }
    return newStr;
}