把原來第n-1個結點至第i個結點依次往后移一個數(shù)組元素位置;

　　把新結點放在第i個位置上;

　　修正線性表的結點個數(shù)。

　　(5)棧

　　堆棧的工作原理是采用后進先出(LIFO)技術，棧頂由中央處理器中的堆棧指示器(SP)指出。在執(zhí)行PUSH操作中SP減量，而在POP操作中SP增量。

　　下面從數(shù)據結構的角度，進一步說明堆棧的基本概念與操作。需要說明的是，其工作原理與前面所介紹的是一致的，不同的是脫離了硬件背景，例如，棧頂指針不是中央處理器的某個寄存器的內容，而是一個抽象的數(shù)據結構。

　　(6)隊列

　　隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素。隊列的最后一個元素一定是最新入隊的元素。因此隊列又稱先進先出表(First-In-First-Out)。

　　日常生活中排隊購物就是隊列應用的例子:新來的顧客排在隊尾等待，排在隊頭的顧客購物后離開隊伍。隊列的基本操作有:

　　①create(Q)建立一個空隊列。

　　②empty(Q)測試隊列是否為空隊列。③full(Q)測試隊列是否為滿。④front(Q)取隊頭元素。

　　⑤enq(X，Q)向隊列中插入一個元素X。⑥enq(Q)刪除隊頭元素。

　　三、數(shù)組

　　線性表(包括棧和隊列)都是線性結構，結構中的每個元素只是無結構的數(shù)據元素。我們對線性表作進一步的推廣，使結構中的元素本身也可以是具有某種結構(如向量)的數(shù)據，從而引出了數(shù)組這一種新的數(shù)據結構。

　　(1)數(shù)組的定義和運算

　　類似于線性表，一個二維數(shù)組(或稱矩陣)可以看成是由m個行向量所組成的向量，也可以看成是由n個列向量所組成的向量。

　　對于數(shù)組的運算，主要有檢索或存取數(shù)組中某個元素。

　　(2)數(shù)組的順序存儲結構

　　由于對數(shù)組一般不作插入或刪除運算，因此，一旦數(shù)組被建立，則結構中的元素個數(shù)和元素之間的關系就不再發(fā)生變動。對這種情況采用順序存儲結構表示數(shù)組是比較恰當?shù)摹?/p>

　　2.樹的基本運算包括:

　　①求根ROOT(T)，引用型運算，其結果是結點X在樹T的根結點。

　　②求雙親PARENT(T，X)，引用型運算，其結果是結點X在樹T上的雙親結點;若X是樹T的根或X不在T上，則結果為一特殊標志。

　　③求孩子CHILD(T，X，i)，引用型運算，其結果是樹T上的結點X的第i個孩子;若X不在T上或X沒有第i個孩子，則結果為一特殊標志。

　　④建樹CREATE(X，T 1 ，…，T k )k≥1，加工型運算，其作用是建立一棵以X為根，以T 1 ，…，T k 為第1，…k棵子樹的樹。

　　⑤剪枝DELETE(T，X，i)，加工型運算，其作用是刪除樹T上結點X的第i棵子樹;若T無第i棵子樹，則為空操作。

　　3.二叉樹

　　(1)二叉樹的基本概念

　　二叉樹是結點的有窮集合，它或者是空集，或者同時滿足下述兩個條件:(1)有且僅有一個稱為根的結點:

　　(2)其余結點分為兩個互不相交的集合T 1 、T 2 ，T 1 與T 2 都是二叉樹，并且T 1 與T 2 有順序關系(T 1 在T 2 之前)，它們分別稱為根的左子樹和右子樹。

　　二叉樹是一類與樹不同的樹形結構。它們的區(qū)別是:第一，二叉樹可以是空集，這種二叉樹稱為空二叉樹。第二，二叉樹的任一結點都有兩棵子樹(當然，它們中的任何一個可以是空子樹)，并且這兩棵子樹之間有次序關系，也就是說，它們的位置不能交換。相應地，二叉樹上任一結點左、右子樹的根分別稱為該結點的左孩子和右孩子。另外，二叉樹上任一結點的度定義為該結點的孩子數(shù)(即非空子樹數(shù))。除這個幾個術語之外，樹的其它術語也適用于二叉樹。

　　特別值得注意的是，由于二叉樹上任一結點的子樹有左、右之分，因此即使一結點只有一棵非空子樹，仍須區(qū)別它是該結點的左子樹還是右子樹，這是與樹不同的。

　　(2)二叉樹的性質

　　在某些情況下，了解二叉樹的下列性質是有幫助的。

　　4.二叉樹的存儲結構

　　二叉樹通常有兩類存儲結構，順序存儲結構和鏈式存儲結構。

　　(1)二叉樹的鏈式存儲結構

　　二叉樹有不同的鏈式存儲結構，其中最常用的是二叉樹鏈表與三叉鏈表。