在我們的日常工作中，前端不可避免的要與算法打交道愧膀，可能很多人都會有疑問，那就是我們真的用到了算法了嗎谣光？其實仔細相信檩淋，我們給數組排序以及從數組中找到需要的元素等等操作，是不是就是所謂的算法的一種呢？在今天這章里蟀悦，我們一起探討下算法的基礎知識中的棧和隊列
棧
棧是一種遵從先進后出（First in last out）原則的有序集合媚朦，新添加的以及待刪除的元素都保存在棧的同一端，我們把他稱作棧頂日戈。相反另一端我們稱之為棧底询张。在日常生活中我們可以拿堆盤子舉例，如圖：
1648385615(1).jpg
就跟我們去堆盤子一樣浙炼，我們只能從最上面放份氧，同時也從最上面拿，如果從下面拿那就可能直接讓整個盤子堆直接掉下來弯屈。
那么我們就可以思考下蜗帜，如果我們自己要實現棧，我們需要有那些方法呢资厉？從我的角度來看厅缺，至少需要以下幾個方法
| 方法名 | 描述 |
|---|---|
| push(item) | 添加一個元素到隊列中 |
| pop() | 移除棧頂元素并返回 |
| peek() | 移除棧頂元素不返回 |
| isEmpty() | 返回隊列是否為空 |
| clear() | 清除隊列 |
| size() | 返回隊列大小 |
是不是感覺挺熟悉的？沒錯宴偿，大多數都是我們數組本身有的方法湘捎，那么我們需要怎么實現一個自己的棧呢？首先肯定是數組窄刘，畢竟棧是一種集合窥妇。同時我們其實在前面數組中說到了，數組可以說是一種特殊的對象都哭，所以我們也可以通過對象來實現秩伞。下面我們依次來看具體的實現逞带。
數組實現棧
export default class Stack {
public items: Array<any>;
constructor() {
this.items = [];
}
/**
* @name: 添加
* @param {any} item
* @return {*}
*/
public push(item: any) {
this.items.push(item);
}
/**
*
* @private 移除棧頂元素
* @returns
* @memberof Stack
*/
public pop() {
return this.items.pop();
}
/**
*
*
* @private 返回棧頂的值
* @returns
* @memberof Stack
*/
public peek() {
return this.items[this.size() - 1];
}
/**
*
*
* @private 返回是否是空的
* @returns {boolean}
* @memberof Stack
*/
public isEmpty():boolean {
return this.size() === 0
}
/**
* @private
* @memberof Stack
*/
public clear() {
this.items = [];
}
/**
*
*
* @private 返回數組size
* @returns
* @memberof Stack
*/
public size() {
return this.items.length;
}
}
對象實現棧
export default class StackObject {
private count: number;
private items: any;
constructor() {
this.count = 0;
this.items = {};
}
/**
* 添加
* @param {*} item
* @memberof StackObject
*/
public push(item: any) {
this.items[this.count] = item;
this.count++;
}
/**
* 移除棧頂元素
* @returns
* @memberof StackObject
*/
public pop() {
if (!this.isEmpty()) {
this.count--;
let result = this.items[this.count];
delete this.items[this.count];
return result;
} else {
return undefined;
}
}
/**
* 返回棧頂
*
* @returns
* @memberof StackObject
*/
public peek() {
if (!this.isEmpty()) {
return this.items[this.count - 1];
} else {
return undefined;
}
}
/**
* 判讀是否為空
* @returns {boolean}
* @memberof StackObject
*/
public isEmpty(): boolean {
return this.count === 0;
}
/**
* 返回size
*
* @returns
* @memberof StackObject
*/
public size() {
return this.count;
}
/**
* 清空
*
* @memberof StackObject
*/
public clear() {
this.items = {};
this.count = 0;
}
/**
* 從任意位置移除
*
* @param {*} item
* @memberof StackObject
*/
public remove(item: any): any {
let index = this.findIndex(item);
if (index === this.size() - 1) {
this.pop();
} else {
let result = this.items[index];
delete this.items[index];
this.count--;
return result;
}
}
/**
* 判斷兩個對象是否相同
*
* @param {*} firstObj
* @param {*} secondObj
* @returns
* @memberof StackObject
*/
public judgeObjectSame(firstObj: any, secondObj: any) {
const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
if (aProps.length !== bProps.length) {
return false;
}
for (let i = 0; i < aProps.length; i++) {
const propName = aProps[i]
const propA = firstObj[propName]
const propB = secondObj[propName]
if ((typeof (propA) === 'object') && propA !== null) {
if (this.judgeObjectSame(propA, propB)) {
} else {
return false;
}
} else if (propA !== propB) {
return false;
} else { }
}
return true;
}
/**
* 獲取所在位置
*
* @param {*} item
* @returns
* @memberof StackObject
*/
public findIndex(item: any | Function) {
let index: number | string = -1;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
index = key;
throw new Error();
}
}
}
} catch (error) {
}
return index;
}
/**
* 獲取當前item
*
* @param {(any | Function)} item
* @returns
* @memberof StackObject
*/
public findItem(item: any | Function) {
let result = undefined;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
return currentItem;
}
}
}
} catch (error) {
}
}
}
上面是兩種實現棧的方法欺矫，下面我們來看下隊列
隊列
隊列是一種遵從先進先出（First in First out）原則的有序項，隊列在尾部添加新元素展氓，并且從頂部移除元素穆趴，最新添加的元素必須排到隊列的末尾。同樣的在日常生活中我們也常遇到隊列的例子遇汞，例如排隊
image.png
我們只能從隊伍的最后進入未妹，從隊伍的前面退出。如果非要反著來空入，我想應該會被后面的人打死吧络它。同棧一樣，要實現隊列歪赢，具體需要哪些方法呢化戳？
| 方法名 | 描述 |
|---|---|
| enQueue(item) | 添加一個元素到隊列中 |
| deQueue：any， | 從隊列頂部移除元素埋凯，并返回 |
| peek()： | 返回隊列頂元素点楼，不移除 |
| isEmpty()：Boolean | 返回隊列是否為空 |
| remove： | 從隊列尾部移除 |
| size() | 返回隊列大小 |
| clear() | 清空隊列 |
| findItem(item) | 返回查找的元素 |
| findIndex(item)：any | 返回的查找元素所在的位置 |
是不是也很熟悉扫尖，沒錯，數組中同樣有類似的方法掠廓，那么我們就通過數組來實現一個自己的隊列
export default class Queue {
private count: number;
private topCount: number;
public items: any;
constructor() {
this.count = 0;
this.topCount = 0;
this.items = {};
}
/**
* 從隊列尾部添加
*
* @param {*} item
* @memberof Queue
*/
public enQueue(item: any) {
this.items[this.count] = item;
this.count++;
}
/**
*
* 從隊列頭部移除
* @returns
* @memberof Queue
*/
public deQueue() {
if (!this.isEmpty()) {
let result = this.items[this.topCount];
delete this.items[this.topCount];
this.topCount++;
return result;
} else {
return undefined;
}
}
/**
* 返回隊列頭部數據
*
* @returns
* @memberof Queue
*/
public peek() {
if (this.isEmpty()) {
return undefined;
} else {
return this.items[this.topCount];
}
}
/**
* 返回隊列的數量
*
* @returns {number}
* @memberof Queue
*/
public size(): number {
return this.count - this.topCount;
}
/**
* 從隊列任何一個地方移除
*
* @param {*} item
* @returns {*}
* @memberof Queue
*/
public remove(item: any): any {
let index = this.findIndex(item);
if (index === this.topCount) {
this.deQueue();
} else {
let result = this.items[index];
delete this.items[index];
this.count--;
return result;
}
}
/**
* 判斷是否是空
*
* @returns
* @memberof Queue
*/
public isEmpty() {
return this.size() === 0
}
/**
* 清空隊列
*
* @memberof Queue
*/
public clear() {
this.count = 0;
this.topCount = 0;
this.items = {};
}
/**
* 判斷兩個對象是否相同
*
* @param {*} firstObj
* @param {*} secondObj
* @returns
* @memberof StackObject
*/
public judgeObjectSame(firstObj: any, secondObj: any) {
const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
if (aProps.length !== bProps.length) {
return false;
}
for (let i = 0; i < aProps.length; i++) {
const propName = aProps[i]
const propA = firstObj[propName]
const propB = secondObj[propName]
if ((typeof (propA) === 'object') && propA !== null) {
if (this.judgeObjectSame(propA, propB)) {
} else {
return false;
}
} else if (propA !== propB) {
return false;
} else { }
}
return true;
}
/**
* 獲取所在位置
*
* @param {*} item
* @returns
* @memberof StackObject
*/
public findIndex(item: any | Function) {
let index: number | string = -1;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
index = key;
throw new Error();
}
}
}
} catch (error) {
}
return index;
}
public findItem(item: any | Function) {
let result = undefined;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
return currentItem;
}
}
}
} catch (error) {
}
}
}
那么隊列在日常生活中有哪些可以用到呢换怖？我們來舉一個例子，那就是擊鼓傳花的游戲蟀瞧，我想大家應該就明白了沉颂。
image.png
我們現在仔細把規(guī)則給解讀下，一群人圍坐一排或者一圈帆赢，那么我們可以用隊列來將這個數據存儲小压，第一個人或其中一個人拿小物品開始依次傳遞，那么我們假設A現在拿到花椰于，那么A可以假定在隊列的頂部怠益，當把花移交給下一位的時候，A肯定不會被淘汰瘾婿，那么我們可以先將A從頂部移除蜻牢，然后將A加到隊列尾部，那么花就在了B手上偏陪，這個時候B就為隊列頭抢呆，如果這個時候聲音停了，那么B就要被淘汰笛谦，那么淘汰就是被移除的意思抱虐。所以我們的實現方法就可以出來了。
const drumFlowerFun = () => {
let names = ['小明', '小紅', '小綠', '小藍', '小白'];
let result = drumFlower(names, 10);
ShopArr.value.drumFlowerData = result;
}
const drumFlower = (list: Array<string>, num: number): {
passList: Array<string>,
winner: string
} => {
let queue = new Queue();
let passList: Array<string> = [];
// 將list傳入到隊列中
list.forEach(item => {
queue.enQueue(item);
})
// 當多余一個人的時候饥脑，首先需要將頭部的人添加到末尾,當數據到了傳遞的次數(也就是鼓停)將當前隊列第一的人淘汰
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enQueue(queue.deQueue());
}
passList.push(queue.deQueue())
}
return {
passList: passList,
winner: queue.deQueue()
}
}
至此隊列我們也結束了嗎恳邀，但是在實際的生活中，同樣是排隊灶轰，人們可以在隊伍的尾部進入谣沸，然后從隊伍的尾部走開，同樣的也可以在隊伍的頭部走開笋颤，但是剛走出去再折回問下問題乳附。那么就涉及到雙端隊列了
雙端隊列
雙端隊列，是在隊列的基礎上允許可以從隊列的前端和后端添加和移除元素的特殊隊列
雙端隊列
那么雙端隊列的方法同樣的，僅僅是在隊列的基礎上增加了兩個方法即可许溅。下面我們來看下具體的實現代碼
/**
* peek() 返回頭部
* isEmpty() 判斷是否為空
* size() 返回size
* remove()移除
* findItem() 獲取item
* addFront() 從隊列頭部添加
* removeFront() 從隊列頭部刪除
* addBackend() 從隊列尾部添加
* removeBackend() 從隊列尾部刪除
* @export
* @class Queue
*/
export default class Queue {
private count: number;
private topCount: number;
public items: any;
constructor() {
this.count = 0;
this.topCount = 0;
this.items = {};
}
/**
* 從隊列尾部添加
*
* @param {*} item
* @memberof Queue
*/
public addBackend(item: any) {
this.items[this.count] = item;
this.count++;
}
/**
* 從隊列頭部添加
*
* @param {*} item
* @memberof Queue
*/
public addFront(item: any) {
if (this.isEmpty()) {
this.addBackend(item);
} else if (this.topCount > 0) {
this.topCount--;
this.items[this.topCount] = item;
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.topCount = 0;
this.items[0] = item;
}
}
/**
*
* 從隊列頭部移除
* @returns
* @memberof Queue
*/
public removeFront() {
if (!this.isEmpty()) {
let result = this.items[this.topCount];
delete this.items[this.topCount];
this.topCount++;
return result;
} else {
return undefined;
}
}
/**
*
* 從隊列尾部移除
* @returns
* @memberof Queue
*/
public removeBackend() {
if (!this.isEmpty()) {
this.count--;
let result = this.items[this.count];
delete this.items[this.count];
return result;
} else {
return undefined;
}
}
/**
* 返回隊列頭部數據
*
* @returns
* @memberof Queue
*/
public peek() {
if (this.isEmpty()) {
return undefined;
} else {
return this.items[this.topCount];
}
}
/**
* 返回隊列的數量
*
* @returns {number}
* @memberof Queue
*/
public size(): number {
return this.count - this.topCount;
}
/**
* 從隊列任何一個地方移除
*
* @param {*} item
* @returns {*}
* @memberof Queue
*/
public remove(item: any): any {
let index = this.findIndex(item);
if (index === this.topCount) {
this.removeFront();
} else {
let result = this.items[index];
delete this.items[index];
this.count--;
return result;
}
}
/**
* 判斷是否是空
*
* @returns
* @memberof Queue
*/
public isEmpty() {
return this.size() === 0
}
/**
* 清空隊列
*
* @memberof Queue
*/
public clear() {
this.count = 0;
this.topCount = 0;
this.items = {};
}
/**
* 判斷兩個對象是否相同
*
* @param {*} firstObj
* @param {*} secondObj
* @returns
* @memberof StackObject
*/
public judgeObjectSame(firstObj: any, secondObj: any) {
const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
if (aProps.length !== bProps.length) {
return false;
}
for (let i = 0; i < aProps.length; i++) {
const propName = aProps[i]
const propA = firstObj[propName]
const propB = secondObj[propName]
if ((typeof (propA) === 'object') && propA !== null) {
if (this.judgeObjectSame(propA, propB)) {
} else {
return false;
}
} else if (propA !== propB) {
return false;
} else { }
}
return true;
}
/**
* 獲取所在位置
*
* @param {*} item
* @returns
* @memberof StackObject
*/
public findIndex(item: any | Function) {
let index: number | string = -1;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
index = key;
throw new Error();
}
}
}
} catch (error) {
}
return index;
}
public findItem(item: any | Function) {
let result = undefined;
try {
for (const key in this.items) {
if (Object.prototype.hasOwnProperty.call(this.items, key)) {
let currentItem = this.items[key];
if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
return currentItem;
}
}
}
} catch (error) {
}
}
}
