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

棧(Stack)是一種遵循先進后出(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;
    }
}

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

# 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)象，一個單詞、短語或數(shù)字，從前往后和從后往前都是一樣的。

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

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

# 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;
}

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

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

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

# 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();
}

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

要把十進制數(shù)轉(zhuǎ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實現(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

同理，我們可以推導出十進制數(shù)轉(zhuǎ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;
}