摘要:線性結構隊列與棧棧棧是一種遵循先進后出原則的有序列表,新添加或待刪除的元素都保存在棧的一端,這一端被稱作為棧頂,另一端被稱作為棧底。將字符串的每個字符按順序亞入棧。
線性結構 隊列與棧 棧
棧(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; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/44807.html
摘要:和三個方法的時間復雜度必須為兩種解法,解法一,將最小值存入自有的數據結構中,如下所示原本的值最小值解法二,用兩個棧 堆棧和隊列統稱線性表 簡單的線性結構 數組和鏈表可以實現這兩種數據結構 堆棧 基本理解 DFS 深度優先---按深度遍歷 遞歸轉非遞歸 隊列 基本理解 BFS 廣度優先---按層序遍歷 出入棧的合法性模擬出入棧的過程,不是入棧,就是...
摘要:程序設計數據結構算法數據結構數據結構就是關系,沒錯,就是數據元素相互之間存在的一種或多種特定關系的集合。物理結構是指數據的邏輯結構在計算機中的存儲形式。 程序設計=數據結構+算法 數據結構 數據結構就是關系,沒錯,就是數據元素相互之間存在的一種或多種特定關系的集合。 傳統上,我們把數據結構分為邏輯結構和物理結構。 邏輯結構:是指數據對象中數據元素之間的相互關系,也是我們今后最...
摘要:棧和隊列是開發中最常用的兩種數據結構。如果又有數據入棧,的值將增加到。如果一個數據從棧中被取出,的值將會減少為。隊列與棧類似,隊列也是一個線性數據結構。與棧不同的是,隊列只刪除最先添加的數據。現在,讓我們將棧大小的實現應用到隊列中。 翻譯:瘋狂的技術宅英文:https://code.tutsplus.com/art...說明:本文翻譯自系列文章《Data Structures With...
閱讀 2888·2021-11-15 11:39
閱讀 1513·2021-08-19 10:56
閱讀 1093·2019-08-30 14:12
閱讀 3731·2019-08-29 17:29
閱讀 719·2019-08-29 16:21
閱讀 3418·2019-08-26 12:22
閱讀 1515·2019-08-23 16:30
閱讀 1015·2019-08-23 15:25