數組是一種隨機訪問數據結構，其中每個元素都可以在恒定時間內直接訪問。隨機訪問的一個典型例子是一本書——這本書的每一頁都可以獨立于其他頁面打開。隨機訪問對許多算法至關重要，例如二分搜索。

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

在本說明中，我們考慮順序數據結構的一個子案例，即所謂的受限訪問數據結構 。

堆棧

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

堆棧是一種遞歸數據結構。這是一個堆棧的結構定義：

一個棧要么是空的，要么

是由一個棧頂和其余棧組成;

應用

堆棧的最簡單應用是反轉一個字。您將一個給定的單詞壓入堆棧 - 一個字母一個字母 - 然后從堆棧中彈出字母。

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

執行

在標準類庫中，數據類型棧是一個適配器類，這意味著棧是建立在其他數據結構之上的。堆棧的底層結構可以是數組、向量、ArrayList、鏈表或任何其他集合。無論底層數據結構的類型如何，堆棧都必須實現相同的功能。這是通過提供一個獨特的界面來實現的：

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

下圖展示了組合實現的思想。

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

基于數組的實現

在基于陣列的實現中，我們維持以下字段：一個默認大小(≥1)中，變量的陣列頂引用在堆棧的頂部元件和容量，指的數組的大小。變量 top從 -1 變為capacity - 1. 我們說當 時棧是空的，當 時top = -1棧是滿的top = capacity-1。

在固定大小的堆棧抽象中，容量保持不變，因此當top達到容量時，堆棧對象會拋出異常。

在動態堆棧抽象中，當top達到容量時，我們將堆棧大小加倍。

基于鏈表的實現

基于鏈表的實現提供了最好的(從效率的角度來看)動態堆棧實現。

隊列

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

堆棧和隊列之間的區別在于刪除。在堆棧中，我們刪除最近添加的項目;在隊列中，我們刪除最近最少添加的項目。

執行

在標準類庫中，數據類型隊列是一個適配器類，這意味著隊列建立在其他數據結構之上。隊列的底層結構可以是數組、向量、ArrayList、LinkedList 或任何其他集合。無論底層數據結構的類型如何，隊列都必須實現相同的功能。這是通過提供獨特的界面來實現的。

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

上述每個基本操作都必須以恒定時間 O(1) 運行。下圖展示了組合實現的思路。

循環隊列

給定一個默認大小 (≥ 1) 的數組 A 有兩個引用back和front，最初分別設置為 -1 和 0。每次我們插入(入隊)一個新項目時，我們都會增加反向索引;當我們刪除(出隊)一個項目時 - 我們增加了前面的索引。下圖展示了經過幾步后的模型：

從圖中可以看出，隊列在數組中從左到右在邏輯上移動。幾次后退到達終點，沒有空間添加新元素

但是，在前面的索引之前有一個空閑空間。我們將使用該空間來排隊新項目，即下一個條目將存儲在索引 0，然后是 1，直到front。這樣的模型稱為環繞隊列或循環隊列

最后，當back到達front 時，隊列已滿。處理滿隊列有兩種選擇：a) 拋出異常;b) 將數組大小加倍。

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