數(shù)組是一種隨機(jī)訪問數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)元素都可以在恒定時(shí)間內(nèi)直接訪問。隨機(jī)訪問的一個(gè)典型例子是一本書——這本書的每一頁(yè)都可以獨(dú)立于其他頁(yè)面打開。隨機(jī)訪問對(duì)許多算法至關(guān)重要，例如二分搜索。

鏈表是一種順序訪問數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)元素只能按特定順序訪問。順序訪問的一個(gè)典型例子是一卷紙或膠帶——所有先前的材料必須展開才能獲得您想要的數(shù)據(jù)。

在本說明中，我們考慮順序數(shù)據(jù)結(jié)構(gòu)的一個(gè)子案例，即所謂的受限訪問數(shù)據(jù)結(jié)構(gòu) 。

堆棧

堆棧是根據(jù)后進(jìn)先出 (LIFO) 原則插入和移除的對(duì)象的容器。在下推堆棧中只允許兩種操作：將 項(xiàng)目推入堆棧，并將項(xiàng)目彈出堆棧。堆棧是一種訪問受限的數(shù)據(jù)結(jié)構(gòu) - 元素只能在堆棧頂部添加和刪除。push將一個(gè)項(xiàng)目添加到堆棧的頂部， pop從頂部刪除該項(xiàng)目。一個(gè)有用的比喻是想想一堆書;您可以只刪除頂部的書，也可以在頂部添加新書。

堆棧是一種遞歸數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)堆棧的結(jié)構(gòu)定義：

一個(gè)棧要么是空的，要么

是由一個(gè)棧頂和其余棧組成;

應(yīng)用

堆棧的最簡(jiǎn)單應(yīng)用是反轉(zhuǎn)一個(gè)字。您將一個(gè)給定的單詞壓入堆棧 - 一個(gè)字母一個(gè)字母 - 然后從堆棧中彈出字母。

另一個(gè)應(yīng)用是文本編輯器中的“撤消”機(jī)制;此操作是通過將所有文本更改保存在堆棧中來完成的。

執(zhí)行

在標(biāo)準(zhǔn)類庫(kù)中，數(shù)據(jù)類型棧是一個(gè)適配器類，這意味著棧是建立在其他數(shù)據(jù)結(jié)構(gòu)之上的。堆棧的底層結(jié)構(gòu)可以是數(shù)組、向量、ArrayList、鏈表或任何其他集合。無論底層數(shù)據(jù)結(jié)構(gòu)的類型如何，堆棧都必須實(shí)現(xiàn)相同的功能。這是通過提供一個(gè)獨(dú)特的界面來實(shí)現(xiàn)的：

public interface StackInterface<AnyType>
{
   public void push(AnyType e);
   public AnyType pop();
   public AnyType peek();
   public boolean isEmpty();
}

下圖展示了組合實(shí)現(xiàn)的思想。

另一個(gè)實(shí)現(xiàn)要求(除了上述接口之外)是所有堆棧操作必須在恒定時(shí)間 O(1) 內(nèi)運(yùn)行。恒定時(shí)間意味著存在一些常數(shù) k，這樣無論堆棧大小如何，操作都需要 k 納秒的計(jì)算時(shí)間。

基于數(shù)組的實(shí)現(xiàn)

在基于陣列的實(shí)現(xiàn)中，我們維持以下字段：一個(gè)默認(rèn)大小(≥1)中，變量的陣列頂引用在堆棧的頂部元件和容量，指的數(shù)組的大小。變量 top從 -1 變?yōu)閏apacity - 1. 我們說當(dāng) 時(shí)棧是空的，當(dāng) 時(shí)top = -1棧是滿的top = capacity-1。

在固定大小的堆棧抽象中，容量保持不變，因此當(dāng)top達(dá)到容量時(shí)，堆棧對(duì)象會(huì)拋出異常。

在動(dòng)態(tài)堆棧抽象中，當(dāng)top達(dá)到容量時(shí)，我們將堆棧大小加倍。

基于鏈表的實(shí)現(xiàn)

基于鏈表的實(shí)現(xiàn)提供了最好的(從效率的角度來看)動(dòng)態(tài)堆棧實(shí)現(xiàn)。

隊(duì)列

隊(duì)列是根據(jù)先進(jìn)先出 (FIFO) 原則插入和刪除的對(duì)象(線性集合)的容器。排隊(duì)的一個(gè)很好的例子是加州大學(xué)美食廣場(chǎng)的一排學(xué)生。在隊(duì)列后面添加新的一行，而刪除(或服務(wù))發(fā)生在前面。在隊(duì)列中只允許入隊(duì)和出隊(duì)兩個(gè)操作 。Enqueue 意味著將一個(gè) item 插入到隊(duì)列的后面，dequeue 意味著移除前面的 item。該圖演示了 FIFO 訪問。

堆棧和隊(duì)列之間的區(qū)別在于刪除。在堆棧中，我們刪除最近添加的項(xiàng)目;在隊(duì)列中，我們刪除最近最少添加的項(xiàng)目。

執(zhí)行

在標(biāo)準(zhǔn)類庫(kù)中，數(shù)據(jù)類型隊(duì)列是一個(gè)適配器類，這意味著隊(duì)列建立在其他數(shù)據(jù)結(jié)構(gòu)之上。隊(duì)列的底層結(jié)構(gòu)可以是數(shù)組、向量、ArrayList、LinkedList 或任何其他集合。無論底層數(shù)據(jù)結(jié)構(gòu)的類型如何，隊(duì)列都必須實(shí)現(xiàn)相同的功能。這是通過提供獨(dú)特的界面來實(shí)現(xiàn)的。

interface QueueInterface?AnyType>
{
   public boolean isEmpty();
   public AnyType getFront();
   public AnyType dequeue();
   public void enqueue(AnyType e);
   public void clear();
}

上述每個(gè)基本操作都必須以恒定時(shí)間 O(1) 運(yùn)行。下圖展示了組合實(shí)現(xiàn)的思路。

循環(huán)隊(duì)列

給定一個(gè)默認(rèn)大小 (≥ 1) 的數(shù)組 A 有兩個(gè)引用back和front，最初分別設(shè)置為 -1 和 0。每次我們插入(入隊(duì))一個(gè)新項(xiàng)目時(shí)，我們都會(huì)增加反向索引;當(dāng)我們刪除(出隊(duì))一個(gè)項(xiàng)目時(shí) - 我們?cè)黾恿饲懊娴乃饕Ｏ聢D展示了經(jīng)過幾步后的模型：

從圖中可以看出，隊(duì)列在數(shù)組中從左到右在邏輯上移動(dòng)。幾次后退到達(dá)終點(diǎn)，沒有空間添加新元素

但是，在前面的索引之前有一個(gè)空閑空間。我們將使用該空間來排隊(duì)新項(xiàng)目，即下一個(gè)條目將存儲(chǔ)在索引 0，然后是 1，直到front。這樣的模型稱為環(huán)繞隊(duì)列或循環(huán)隊(duì)列

最后，當(dāng)back到達(dá)front 時(shí)，隊(duì)列已滿。處理滿隊(duì)列有兩種選擇：a) 拋出異常;b) 將數(shù)組大小加倍。

循環(huán)隊(duì)列的實(shí)現(xiàn)是通過使用模運(yùn)算符(表示為 %)來完成的，它是通過取除法的余數(shù)來計(jì)算的(例如，8%5 是 3)。通過使用模運(yùn)算符，我們可以將隊(duì)列視為一個(gè)循環(huán)數(shù)組，其中“環(huán)繞”可以模擬為“back % array_size”。除了前后索引之外，我們還維護(hù)了另一個(gè)索引：cur - 用于計(jì)算隊(duì)列中元素的數(shù)量。擁有這個(gè)索引簡(jiǎn)化了實(shí)現(xiàn)的邏輯。