棧(stack)
限定僅在表尾進(jìn)行插入和刪除操作的線性表(一個線性表是
n個具有相同特性的數(shù)據(jù)元素的有限序列,線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系)乘盼，表尾為棧頂阐虚，表頭稱為棧底。
椛芑妫基本操作（以數(shù)組為例）
1. 一個空棧
var Stack = [ ]; //字面量方式
var Stack = new Array() //構(gòu)造函數(shù)模式
2.清空棧
// 1. length
StackA.length = 0;
// 2. 賦值[ ]
StackA = [ ];
//3.刪除元素绎橘，并向數(shù)組添加新元素
splice()
//arr.splice( index, howmany , itemq, .... ,itemx)
//index : 必需，整數(shù)骑脱，規(guī)定添加/刪除項(xiàng)目的位置菜枷，使用負(fù)數(shù)可從數(shù)組結(jié)尾處規(guī)定位置
//howmany : 必需，要刪除的項(xiàng)目的數(shù)量叁丧，如果設(shè)置為0啤誊，則不會刪除項(xiàng)目
//item, ...., itemX : 可選岳瞭，向數(shù)組中添加新的項(xiàng)目
StackA.splice( -1 , StackA.length) //從尾部(索引為-1)刪除元素
3.判斷是否為空棧，返回true/false
function isEmpty( stack ){
if(stack.length == 0){
return false
} else {
return true
}
}
4.返回棧的元素個數(shù)
function stackLength ( stack ) {
return stack.length
}
5. 刪除棧頂元素
//刪除數(shù)組最后一個元素蚊锹，把數(shù)組長度減1瞳筏，并且返回它刪除的元素的值
// 如果數(shù)組已為空，則pop()不改變數(shù)組牡昆，并返回undefined 值
pop ( )
function popTop ( stack) {
return stack.pop()
}
6. 插入新的棧頂元素
push ( ) //向數(shù)組的末尾添加一個或多個元素姚炕，并返回新的長度
//items為要添加的新元素構(gòu)成的數(shù)組
function pushItem ( stack , items) {
stack.push (...items)
}
隊(duì)列
和 棧 相反，隊(duì)列 是一種先進(jìn)先出（
FIFO）的線性表丢烘，只允許在表的一端進(jìn)行插入柱宦，而在另一端進(jìn)行刪除元素，最早進(jìn)入隊(duì)列的元素最早離開播瞳。允許插入的一端稱為隊(duì)尾掸刊，允許刪除的一端稱為隊(duì)頭
隊(duì)列操作
1.構(gòu)造一個空隊(duì)列 （以數(shù)組為例）
var Queue = [ ] ;
var Queue = new Array();
2.清空隊(duì)列
// 1. length
QueueA.length = 0;
// 2. 賦值
QueueA = [ ];
// 3. splice（）
Queue.splice( 0 , QueueA.length) //從頭部刪除元素
// 4.判斷是否為空
function isEmpty( queue ){
if(queue.length == 0){
return false
} else {
return true
}
}
// 5.返回元素個數(shù)
return queue.length
// 6. 刪除隊(duì)頭元素
//將數(shù)組第一個元素從其中刪除，并返回第一個元素的值赢乓，如果數(shù)組為空忧侧，將不進(jìn)行任何操作，并返回undefined
shift ( )
queue.shift( )
// 7. 插入新的隊(duì)尾元素
push ( ) //向數(shù)組的末尾添加一個或多個元素牌芋，并返回新的長度
//items為要添加的新元素構(gòu)成的數(shù)組
function pushItem ( queue , items) {
queue.push (...items)
}
3.樹和二叉樹
以分支關(guān)系定義的層次結(jié)構(gòu)苍柏。樹 是
n (n>=0)個結(jié)點(diǎn)的有限集
在任意一棵非空樹中：
（1） 有且僅有一個特定的稱為 **根（root） **的結(jié)點(diǎn) ；
（2） 當(dāng) n>1 時姜贡，其余結(jié)點(diǎn)可分為m (m>0) 個互不相交的有限集T1,T2,...,Tm, 其中每一個集合本身又是一棵樹，并且稱為根的 子樹 棺棵。
如圖 是有6個結(jié)點(diǎn)的樹楼咳，其中A 是根，其余結(jié)點(diǎn)分為2個互不相交的子集烛恤，T1= {B, D, E} , T2 = { C, F} ,T1 , T2 都是根A 的子樹母怜，且本身也是一棵樹，如T1的根為B缚柏，而T11 = {D } , T12 = {E}苹熏，則T11,T22都是B的子樹，是只有一個根結(jié)點(diǎn)的樹
二叉樹
二叉樹的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩課子樹（即二叉樹中不存在深度大于2的結(jié)點(diǎn)）币喧。并且轨域，二叉樹的子樹有左右之分，其次序不能任意顛倒
1. 二叉樹的第i層上至多有2^(i-1)個結(jié)點(diǎn) （i>=1）
2. 深度為K的二叉樹至多有(2^k)-1個結(jié)點(diǎn)
二叉樹分類
1. 滿二叉樹：一棵深度為k且有2^k - 1個節(jié)點(diǎn)的二叉樹稱為滿二叉樹
2. 完全二叉樹：完全二叉樹是指最后一層左邊是滿的杀餐，右邊可能滿也可能不滿干发，然后其余層都是滿的二叉樹稱為完全二叉樹(滿二叉樹也是一種完全二叉樹)
二叉樹的存儲結(jié)構(gòu)
- 順序存儲結(jié)構(gòu)
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)
二叉樹遍歷
1.先序遍歷（前序遍歷）
若二叉樹非空，則依次執(zhí)行如下操作：
⑴ 訪問根結(jié)點(diǎn)史翘；
⑵ 遍歷左子樹枉长；
⑶ 遍歷右子樹冀续。
2.中序遍歷
若二叉樹非空，則依次執(zhí)行如下操作：
⑴ 遍歷左子樹必峰；
⑵ 訪問根結(jié)點(diǎn)洪唐；
⑶ 遍歷右子樹。
3. 后序遍歷
若二叉樹非空吼蚁，則依次執(zhí)行如下操作：
⑴ 遍歷左子樹凭需；
⑵ 遍歷右子樹；
⑶ 訪問根結(jié)點(diǎn)桂敛。
二叉查找樹(二叉搜索樹)
滿足以下性質(zhì)的二叉樹
1. 若它的左子樹不空功炮，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2. 若它的右子樹不空术唬，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值薪伏；
3. 它的左、右子樹也分別為二叉查找樹粗仓。
