上周還說寫寫markdown的學(xué)習(xí)，但是看了一遍博客發(fā)現(xiàn)似乎沒什么可說的寂殉，看了一圈教程發(fā)現(xiàn)似乎只要模仿就好了囚巴，參考鏈接
http://www.reibang.com/p/q81RER
所以這周想隨便寫寫。
兩種數(shù)據(jù)結(jié)構(gòu)
棧和隊(duì)列友扰，兩種我們用的最多也是最常見的兩種數(shù)據(jù)結(jié)構(gòu)彤叉。讓我回憶一下，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候村怪，一開始介紹了順序表秽浇，鏈表，然后就是棧和隊(duì)列甚负，再然后就是樹柬焕，圖一類的比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)审残。而棧和隊(duì)列，可以說是比較常用的兩種斑举，因?yàn)槠鋵?shí)現(xiàn)方式簡單搅轿，很多語言把這兩種數(shù)據(jù)結(jié)構(gòu)專門封裝了庫，而且這兩種本身也和程序的執(zhí)行有關(guān)（調(diào)用棧等等）富玷。
區(qū)別與共同點(diǎn)
從這里開始我將結(jié)合js做一些常用點(diǎn)的討論璧坟。首先，棧和隊(duì)列赎懦，無論在當(dāng)時(shí)進(jìn)行編寫的時(shí)候還是后來用js進(jìn)行練習(xí)雀鹃，我都認(rèn)為，順序表励两，鏈表褐澎，棧和隊(duì)列都可以理解為數(shù)組，甚至樹和圖也可以這么理解伐蒋。不過他們會(huì)有很多自己的特性工三，以至于他們不能完全像數(shù)組那么隨意。
就今天的主角——棧和隊(duì)列來說先鱼，他們的共同特點(diǎn)就是俭正，只能從首尾進(jìn)行插入和刪除，棧是只能從頭進(jìn)行插入和刪除焙畔，隊(duì)列是要從頭進(jìn)行插入掸读，從尾部進(jìn)行刪除。棧和隊(duì)列這樣的特性宏多，決定了他們的各自數(shù)據(jù)插入刪除的結(jié)構(gòu)儿惫，棧必須是后進(jìn)先出，因?yàn)樗挥袟ｍ斠粋€(gè)出入口伸但，隊(duì)列是先進(jìn)先出肾请，靈魂繪圖。更胖。铛铁。：
所以無論何時(shí)我們做任何操作的時(shí)候，我們必須記住兩個(gè)各自的特性却妨，從刪除到添加饵逐，從搜索到遍歷，從逆序到交換等各種操作都得講究這種先進(jìn)先出彪标，后進(jìn)先出的特性倍权。比如我要在棧或者中刪除B捞烟，那么絕對不可以像數(shù)組刪除一樣直接從中間干掉就好薄声，需要滿足兩者的特性当船，棧必須B移到棧頂刪除，隊(duì)列必須到隊(duì)列尾刪除奸柬，交換的時(shí)候不能破壞棧與隊(duì)列的結(jié)構(gòu)生年，或者也可以一個(gè)一個(gè)的pop，然后再一個(gè)一個(gè)的push進(jìn)來廓奕。
未完抱婉。。桌粉。蒸绩。
更復(fù)雜的形式（鏈棧，鏈隊(duì)列铃肯，循環(huán)隊(duì)列）
手寫js的棧與隊(duì)列
今天再填一個(gè)坑患亿，手寫了js的棧和隊(duì)列，當(dāng)然使用了typescript押逼，所以從形式上是更直觀的面向?qū)ο?/p>
------
interface ObjectT {
? value: string,
}
class Stack {
? private stackContent: ObjectT[]
? private stackTop?: ObjectT
? private objectNumber: number
? constructor(stack:ObjectT[]) {
? ? this.stackContent = stack || []
? ? this.objectNumber = this.stackContent.length
? ? if(this.objectNumber != 0) {
? ? ? this.stackTop = this.stackContent[0]
? ? }
? }
? public push(obj: ObjectT) {
? ? this.objectNumber++
? ? for(let i = this.objectNumber-1;i >= 0;i--) {
? ? ? if(i == 0) {
? ? ? ? this.stackContent[i] = obj
? ? ? }
? ? ? else {
? ? ? ? this.stackContent[i] = this.stackContent[i-1]
? ? ? }
? ? }
? ? this.stackTop = this.stackContent[0]
? ? console.log(this.stackContent)
? ? console.log(this.stackTop)
? }
? public pop() {
? ? if(this.objectNumber > 0) {
? ? ? for(let i = 0;i < this.objectNumber-1;i++) {
? ? ? ? this.stackContent[i] = this.stackContent[i+1]
? ? ? }
? ? ? let result = this.stackTop
? ? ? this.stackTop = this.stackContent[0]
? ? ? delete this.stackContent[this.objectNumber-1]
? ? ? this.objectNumber--
? ? ? return result
? ? }
? }
}
class Queue {
? private queueContent: ObjectT[]
? private queueTop?: ObjectT
? private queueTail?: ObjectT
? private objectNumber: number
? constructor(queue: ObjectT[]) {
? ? this.queueContent = queue || []
? ? this.objectNumber = this.queueContent.length
? ? if(this.objectNumber != 0) {
? ? ? this.queueTop = this.queueContent[0]
? ? ? this.queueTail = this.queueContent[this.objectNumber-1]
? ? }
? }
? public push(obj:ObjectT) {
? ? this.objectNumber++
? ? for(let i = this.objectNumber-1;i >= 0;i--) {
? ? ? if(i == 0) {
? ? ? ? this.queueContent[i] = obj
? ? ? }
? ? ? else {
? ? ? ? this.queueContent[i] = this.queueContent[i-1]
? ? ? }
? ? }
? ? this.queueTop = this.queueContent[0]
? ? this.queueTail = this.queueContent[this.objectNumber-1]
? ? console.log(this.queueContent)
? ? console.log(this.queueTop)
? ? console.log(this.queueTail)
? }
? public pop() {
? ? if(this.objectNumber > 0) {
? ? ? let result = this.queueTail
? ? ? delete this.queueContent[this.objectNumber-1]
? ? ? this.objectNumber--
? ? ? this.queueTail = this.queueContent[this.objectNumber-1]
? ? ? console.log(this.queueContent)
? ? ? return result
? ? }
? }
}
-----------
