1 棧
棧是一種后入先出（LIFO）的線性邏輯存儲(chǔ)結(jié)構(gòu)。只允許在棧頂進(jìn)行進(jìn)出操作。
1.1 棧基本操作
基本操作包括：入棧（push）/出棧（pop）/獲取棧頂元素（peek）。
棧的實(shí)現(xiàn)主要有兩種： 1. 數(shù)組實(shí)現(xiàn)，即順序棧 2. 鏈表實(shí)現(xiàn)，即鏈?zhǔn)綏?/p>
無論是以數(shù)組還是以鏈表實(shí)現(xiàn)，入棧、出棧的時(shí)間復(fù)雜度都是O(1)。
棧的應(yīng)用比如函數(shù)執(zhí)行/括號(hào)匹配/表達(dá)式計(jì)算/瀏覽器前進(jìn)后退。
?
??
1.2 設(shè)計(jì)棧
1.2.1 數(shù)組實(shí)現(xiàn)棧
class ArrayStack<T> {
items: T[];
constructor() {
this.items = [];
}
/**
* 入棧
* @param item
*/
push(item: T) {
this.items.push(item);
}
/**
* 出棧
* @returns
*/
pop() {
if (this.isEmpty()) throw new Error('棧空');
return this.items.pop();
}
/**
* 獲取棧頂元素
* @returns
*/
peek() {
if (this.isEmpty()) throw new Error('?？?);
return this.items[this.items.length - 1];
}
/**
* 判空
* @returns
*/
isEmpty() {
return this.items.length === 0;
}
/**
* 獲取棧元素的個(gè)數(shù)
* @returns
*/
getSize() {
return this.items.length;
}
}1.2.2?鏈表實(shí)現(xiàn)棧
class LinkStack<T> {
// 棧的長度
size: number;
// 棧頂指針
top: LinkNode<T> | null;
constructor() {
this.size = 0;
this.top = null;
}
/**
* 入棧
* @param item
*/
push(val: T) {
let node = new LinkNode(val);
if (this.top === null) {
// 棧空
this.top = node;
} else {
// 棧非空
node.next = this.top;
this.top = node;
}
this.size = this.size + 1;
}
/**
* 出棧
* @returns
*/
pop() {
if (this.top === null) {
// 棧空
throw new Error('?？?);
} else {
// 棧非空
const data = this.top.val; // 棧頂元素值
this.top = this.top.next; // 新棧頂
this.size = this.size - 1;
return data;
}
}
/**
* 獲取棧頂元素
* @returns
*/
peek() {
if (this.top === null) {
// ?？? throw new Error('棧空');
} else {
return this.top.val;
}
}
/**
* 判空
* @returns
*/
isEmpty() {
return this.top === null;
}
/**
* 獲取棧元素的個(gè)數(shù)
* @returns
*/
getSize() {
return this.size;
}
}
1.3 劍指 offer 棧算法題（ typescript 版）
包含min函數(shù)的棧
棧的壓入、彈出序列
2 隊(duì)列
隊(duì)列是一種先入先出（FIFO）的線性邏輯存儲(chǔ)結(jié)構(gòu)。只允許在隊(duì)首進(jìn)行出隊(duì)（即delete刪除）操作，隊(duì)尾進(jìn)行入隊(duì)（即insert插入）操作。
2.1 隊(duì)列基本操作
隊(duì)列的基本操作包括：入隊(duì) （enqueue）/ 出隊(duì) （dequeue）/ 獲取隊(duì)頭元素（peek）
隊(duì)列的實(shí)現(xiàn)主要有兩種： 1. 數(shù)組實(shí)現(xiàn)，即順序隊(duì)列 2. 鏈表實(shí)現(xiàn)，即鏈?zhǔn)疥?duì)列。
無論是以數(shù)組還是以鏈表實(shí)現(xiàn)，入隊(duì)、出隊(duì)的時(shí)間復(fù)雜度都是O(1)。
隊(duì)列的應(yīng)用比如線程池、資源池、消息隊(duì)列、異步隊(duì)列。
2.2 設(shè)計(jì)隊(duì)列
2.2.1 數(shù)組順序隊(duì)列
使用數(shù)組實(shí)現(xiàn)，使用shift出隊(duì)時(shí)每次都要移動(dòng)隊(duì)列元素，效率不高。改進(jìn)方案是可以隊(duì)列初始化時(shí)就需要規(guī)定隊(duì)列長度，通過判斷隊(duì)尾是否有空間，有就讓元素一直入隊(duì)，直到隊(duì)尾沒有空間位置，然后進(jìn)行整體進(jìn)行一次搬移，這樣優(yōu)化了入隊(duì)的效率，平均時(shí)間復(fù)雜度還是 O(1)。
class ArrayQueue<T> {
items: T[];
constructor() {
this.items = [];
}
/**
* 入隊(duì)
* @param item
*/
push(item: T) {
this.items.push(item);
}
/**
* 出隊(duì)
* @returns
*/
pop() {
if (this.isEmpty()) throw new Error('隊(duì)列空');
return this.items.shift();
}
/**
* 獲取隊(duì)頂元素
* @returns
*/
peek() {
if (this.isEmpty()) throw new Error('隊(duì)列空');
return this.items[0];
}
/**
* 判空
* @returns
*/
isEmpty() {
return this.items.length === 0;
}
/**
* 獲取隊(duì)元素的個(gè)數(shù)
* @returns
*/
getSize() {
return this.items.length;
}
}2.2.2 數(shù)組循環(huán)隊(duì)列
數(shù)組實(shí)現(xiàn)，初始化需指定隊(duì)列容量capacity，留一個(gè)空位，隊(duì)空條件 head = tail，隊(duì)滿條件 head =( tail + 1) % capacity，隊(duì)列元素個(gè)數(shù)(tail - head + capacity) % capacity）。
class LoopQueue {
// 存放元素的數(shù)組
values: (number | undefined)[];
// 當(dāng)前元素個(gè)數(shù)
count: number;
// 隊(duì)的長度
capacity: number;
// 隊(duì)尾
head: number;
// 隊(duì)尾
tail: number;
constructor(capacity: number) {
this.head = 0;
this.tail = 0;
this.capacity = capacity;
this.count = 0;
this.values = new Array(capacity);
}
/**
* 入隊(duì)
* @param item
*/
enQueue(val: number) {
if (this.isFull()) {
throw new Error('隊(duì)滿');
}
this.values[this.tail] = val;
this.tail = (this.tail + 1) % this.capacity;
this.count = this.count + 1;
return true;
}
/**
* 出隊(duì)
* @returns
*/
deQueue(): number {
if (this.isEmpty()) {
throw new Error('隊(duì)空');
}
const value = this.values[this.head] as number;
this.values[this.head] = undefined;
this.head = (this.head + 1) % this.capacity;
this.count = this.count - 1;
return value;
}
/**
* 獲取隊(duì)頭元素
* @returns
*/
peek() {
if (this.isEmpty()) {
throw new Error('隊(duì)空');
}
const value = this.values[this.head];
return value;
}
/**
* 判空
* @returns
*/
isEmpty() {
// 或 return this.head === this.tail
return this.count === 0;
}
/**
* 判滿
* @returns
*/
isFull() {
// 或 return this.head === (this.tail + 1) % this.capacity
return this.count === this.capacity - 1;
}
/**
* 獲取隊(duì)元素的個(gè)數(shù)
* @returns
*/
getSize() {
return this.count;
}
/**
* 清空隊(duì)列
* @returns
*/
clear() {
this.head = 0;
this.tail = 0;
this.count = 0;
this.values = new Array(this.capacity);
return true;
}
}2.2.3 鏈?zhǔn)巾樞蜿?duì)列
鏈表實(shí)現(xiàn)，鏈表尾入隊(duì)，鏈表頭出隊(duì)文章來源：http://www.zghlxwxcb.cn/news/detail-512740.html
class LinkQueue<T> {
// 隊(duì)的長度
size: number;
// 隊(duì)尾指針
head: LinkNode<T> | null;
// 隊(duì)尾指針
tail: LinkNode<T> | null;
constructor() {
this.size = 0;
this.head = null;
this.tail = null;
}
/**
* 入隊(duì)
* @param item
*/
enQueue(val: T) {
let node = new LinkNode(val);
if (this.size === 0) {
this.head = node;
this.tail = node;
} else {
this.tail!.next = node;
this.tail = this.tail!.next;
}
this.size = this.size + 1;
}
/**
* 出隊(duì)
* @returns
*/
deQueue() {
if (this.size === 0) {
// 隊(duì)空
throw new Error('隊(duì)空');
} else {
// 隊(duì)非空
const node = this.head;
this.head = node!.next;
this.size = this.size - 1;
return node!.val;
}
}
/**
* 獲取隊(duì)頭元素
* @returns
*/
peek() {
if (this.size === 0) {
// 隊(duì)空
throw new Error('隊(duì)空');
} else {
return this.head!.val;
}
}
/**
* 判空
* @returns
*/
isEmpty() {
return this.size === 0;
}
/**
* 獲取隊(duì)元素的個(gè)數(shù)
* @returns
*/
getSize() {
return this.size;
}
}
2.3 劍指 offer 隊(duì)列算法題（ typescript 版）
兩個(gè)棧實(shí)現(xiàn)隊(duì)列文章來源地址http://www.zghlxwxcb.cn/news/detail-512740.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法：棧和隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
