摘要:线性结构队列与栈栈栈是一种遵循先进后出原则的有序列表,新添加或待删除的元素都保存在栈的一端,这一端被称作为栈顶,另一端被称作为栈底。将字符串的每个字符按顺序亚入栈。
线性结构 队列与栈 栈
栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表,新添加或待删除的元素都保存在栈的一端,这一端被称作为栈顶,另一端被称作为栈底。在栈里,新元素都靠近栈顶,旧元素都靠近栈底。
栈的操作方法 | 操作 |
---|---|
push | 添加新元素到栈顶 |
pop | 移除并返回栈顶元素 |
peek | 返回栈顶元素 |
size | 返回栈大小 |
clear | 移除栈内所有元素 |
isEmpty | 判断栈是否为空 |
# 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 | 判断队列是否为空 |
# 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 = 1
Python实现
# 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; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/98423.html
摘要:和三个方法的时间复杂度必须为两种解法,解法一,将最小值存入自有的数据结构中,如下所示原本的值最小值解法二,用两个栈 堆栈和队列统称线性表 简单的线性结构 数组和链表可以实现这两种数据结构 堆栈 基本理解 DFS 深度优先---按深度遍历 递归转非递归 队列 基本理解 BFS 广度优先---按层序遍历 出入栈的合法性模拟出入栈的过程,不是入栈,就是...
摘要:程序设计数据结构算法数据结构数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。物理结构是指数据的逻辑结构在计算机中的存储形式。 程序设计=数据结构+算法 数据结构 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。 传统上,我们把数据结构分为逻辑结构和物理结构。 逻辑结构:是指数据对象中数据元素之间的相互关系,也是我们今后最...
摘要:栈和队列是开发中最常用的两种数据结构。如果又有数据入栈,的值将增加到。如果一个数据从栈中被取出,的值将会减少为。队列与栈类似,队列也是一个线性数据结构。与栈不同的是,队列只删除最先添加的数据。现在,让我们将栈大小的实现应用到队列中。 翻译:疯狂的技术宅英文:https://code.tutsplus.com/art...说明:本文翻译自系列文章《Data Structures With...
阅读 2846·2021-11-15 11:39
阅读 1484·2021-08-19 10:56
阅读 1060·2019-08-30 14:12
阅读 3652·2019-08-29 17:29
阅读 623·2019-08-29 16:21
阅读 3388·2019-08-26 12:22
阅读 1487·2019-08-23 16:30
阅读 967·2019-08-23 15:25