01-線性結構-數組-棧結構

線性結構（Linear List)是由n（n>=0)個數據元素（結點） a[0], a[1], a[2], a[3],...,a[n-1]組成的有限序列

數組

通常數組的內存是連續的，所以在知道數組下標的情況下，訪問效率是非常高的

可在數組的任意位置插入和刪除數據

棧結構

簡介

• 是一種受限的線性結構，先進后出
• 僅允許在表的一端進行插入和刪除運算，即棧頂；另一端為棧底。
• 必須按照順序來進出棧

習題練習：

題目

有六個元素6,5,4,3,2,1的順序進棧，問下列哪一個不是合法的出棧序列？（C ）

A. 5 4 3 6 1 2 B. 4 5 3 2 1 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

答案解析：

A：65進棧，5出棧，4進棧出棧，3進棧出棧，6出棧，21進棧，1出棧，2出棧

B：654進棧，4出棧，5出棧，3進棧出棧，2進棧出棧，1進棧出棧，6出棧

D：65432進棧，2出棧，3出棧，4出棧，1進棧出棧，5出棧，6出棧

實現棧結構

// 封裝一個棧
class ArrayStack {// 定義一個數組/鏈表。用于存儲數據private data: any[] = []// 實現棧中相關的操作方法// 1.push方法：將一個元素壓入到棧中push(element: any):void {this.data.push(element)}// 2.pop方法：將棧頂的元素彈出棧（返回出去，并且移除該項）pop():any {return this.data.pop()}// 3peek方法：看一眼棧頂元素，但是不進行任何操作peek(): any {return this.data[this.data.length - 1]}// 4.isEmpty：判斷棧是否為空isEmpty(): boolean {return this.data.length === 0}// 5.size：返回棧的數據個數size(): number {return this.data.length}
}

對上述代碼進行測試：

// 創建stack實例
const stack1 = new ArrayStack()
stack1.push("aaa")
stack1.push("bbb")
stack1.push("ccc")console.log(stack1.peek());//ccc
console.log(stack1.pop());//ccc
console.log(stack1.pop());//bbb
console.log(stack1.pop());//aaaconsole.log(stack1.isEmpty());//true
console.log(stack1.size());//0

相關應用

十進制轉二進制

import ArrayStack from "./02-實現棧結構Stacks(重構)"function decimalToBinary(decimal: number): string {// 1.創建一個棧，用于存放余數const stack = new ArrayStack<number>()/* 2.使用循環 // while:不確定次數，只知道循環結束跳轉// for:知道循環的次數*/while(decimal > 0) {const result = decimal % 2stack.push(result)decimal = Math.floor(decimal / 2)}//  3.所有的余數都已經放在stack中，依次取出即可let binary = ''while(!stack.isEmpty()) {binary += stack.pop()}return binary
}console.log(decimalToBinary(35));//100011
console.log(decimalToBinary(100));//1100100

有效的括號

20. 有效的括號 - 力扣（LeetCode）（考察棧）

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應的相同類型的左括號。

解題：

import ArrayStack from "./02-實現棧結構Stacks(重構)"function isValid(s:string): boolean {// 1.創建一個棧結構const stack = new ArrayStack<string>()// 2.變量s中的所有括號for(let i = 0; i < s.length; i++) {const c = s[i]switch(c) {case "(":stack.push(")")breakcase "{":stack.push("}")breakcase "[":stack.push("]")breakdefault:if(c !== stack.pop()) return falsebreak}}return stack.isEmpty()
}console.log(isValid("()"));
console.log(isValid("()[]{}["));

02-隊列結構-面試題

• 隊列（queue)是一種先進先出的線性結構
• 數據元素按照順序依次進入隊列，最先進入的元素最先離開隊列
• 類似于現實中的排隊場景，比如排隊買票，先到的人先離開隊列
• 常見的隊列結構

實現隊列結構

1.定義隊列結構接口

interface IQueue<T> {// 入隊方法enqueue(element: T): void// 出隊方法dequeue(): T | undefined// peek 方法peek(): T | undefined// 判斷是否為空isEmpty(): boolean// 元素個數size(): number
}export default IQueue

2.實現隊列結構

import IQueue from "./IQueue"
class ArrayQueue<T> implements IQueue<T> {// 內部通過數組或鏈表保存數據private data: T[] = []enqueue(element: T): void {this.data.push(element)}dequeue(): T | undefined {return this.data.shift()}peek(): T | undefined {return this.data[0]}isEmpty(): boolean {return this.data.length === 0}size(): number {return this.data.length}
}export default ArrayQueue

3.測試代碼：

import ArrayQueue from "./01-實現隊列結構";const queue = new ArrayQueue<number>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.dequeue());//1
console.log(queue.dequeue());//2
console.log(queue.size());//1

擊鼓傳花

要求：一群人圍成一圈，獲取最后剩下的人位置或名字

import ArrayQueue from "./01-實現隊列結構"
function hotPotatao (names:string[],num:number) {if(names.length === 0) return -1// 創建隊列結構const queue = new ArrayQueue<string>()// 2.將所有name入隊操作for (const name of names) {queue.enqueue(name)}// 3.淘汰的規則while(queue.size()>1){// 1、2淘汰for(let i = 1;i<num; i++) {const name = queue.dequeue()if(name) queue.enqueue(name)}// 3淘汰queue.dequeue()}// return queue.dequeue()const Leftname = queue.dequeue()!// 拿到當前名字的索引return names.indexOf(Leftname)
}const leftName = hotPotatao(["張三","李四","王五","趙六","錢七"],3)
console.log(leftName);

約瑟夫環

0，1，...,n-1個數字圍城一個圈，從數字0開始，每次刪除圓圈中第m個數字（刪除后從下一個數字計數）。求該圓圈剩下的最后一個數字。

import ArrayQueue from "./01-實現隊列結構"
function lastRemaining(n:number,m:number) {// 輸入參數校驗if (n <= 0 || m <= 0) {throw new Error("參數 n 和 m 必須大于 0");}// 1.創建隊列const queue = new ArrayQueue<number>()// 2.將所有數組加入到隊列中for (let i = 0; i < n; i++) {queue.enqueue(i)}// 3.判斷隊列中是否還有數字while(queue.size()>1) {for(let i = 1; i<m; i++) {queue.enqueue(queue.dequeue()!)}queue.dequeue()}return queue.dequeue()!
}console.log(lastRemaining(5,3));//3console.log(lastRemaining(10,17));//2

動態規劃思想實現：

function lastRemainingOptimized(n: number, m: number): number {if (n <= 0 || m <= 0) {throw new Error("參數 n 和 m 必須大于 0");}let result = 0;for (let i = 2; i <= n; i++) {result = (result + m) % i;}return result;
}// 測試用例
console.log(lastRemainingOptimized(5, 3)); // 輸出: 3
console.log(lastRemainingOptimized(10, 17)); // 輸出: 2