线性结构 队列与栈
线性结构 队列与栈
栈
栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。
栈的操作
方法 | 操作 |
|---|---|
push | 添加新元素到栈顶 |
pop | 移除并返回栈顶元素 |
peek | 返回栈顶元素 |
size | 返回栈大小 |
clear | 移除栈内所有元素 |
isEmpty | 判断栈是否为空 |
Python实现栈
# 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 == []JavaScript实现栈
// 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)原则的有序列表。队列在尾部添加新元素，从顶部移除元素。最新添加的元素必须排列在队列的末尾。
队列操作
方法 | 操作 |
|---|---|
enqueue | 添加新元素到队列尾部 |
dequeue | 移除并返回队首元素 |
front | 返回队首元素 |
size | 返回队列大小 |
clear | 移除队列内所有元素 |
isEmpty | 判断队列是否为空 |
Python实现队列
# 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 == []JavaScript实现队列
// 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;
}
}栈的应用
回文检索
回文是指一种现象，一个单词、短语或数字，从前往后和从后往前都是一样的。
# 单词
dad
racecar
# 数字
1001使用栈，可以轻松判断一个字符串是否是回文。将字符串的每个字符按顺序亚入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串。通过弹出栈内每个字母可以得到一个新字符，只需要比较两个字符串即可。
# 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;
}简单括号匹配
在表达式中，括号必须以匹配的方式出现。括号匹配意味着每个开始符号具有相应的结束符号，并且括号能被正确嵌套。
(5+6)*(7+8)/(4+3) # 括号匹配
(2+3)+24/12+(4-2 # 括号不匹配栈可以用来判断一个表达式中的括号是否匹配。从空栈开始，从左到右处理表达式。如果一个符号是一个开始符号，将其作为一个信号，对应的结束符号稍后会出现。另一方面，如果符号是结束符号，弹出栈，只要弹出栈的开始符号可以匹配每个结束符号，则括号保持匹配状态。如果任何时候栈上没有出现符合开始符号的结束符号，则字符串不匹配。最后，当所有符号都被处理后，栈应该是空的。
# 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();
}进制转换
在生活中，我们主要使用十进制数。但在计算科学中，二进制非常重要，因为计算机里的内容都是用二进制数字表示的(0和1)。如果没有进制转化的能力，与计算机交流就会非常困难。
要把十进制数转化成二进制的算法，将十进制数与2相除，并取余数。
10 => 1010
10/2 = 5, rem = 0
5/2 = 2, rem = 1
2/2 = 1, rem = 0
1/2 = 0, rem = 1Python实现
# 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同理，我们可以推导出十进制数转化八进制和十六进制算法。以下是完整的进制转换算法。
# 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;
}