Tương tự, người ta mở rộng ra: mảng ba chiều,...,mảng n chiều.

Mỗi phần tử trong một danh sách thường là một bản ghi (gồm một hoặc nhiều trường). Ví dụ: danh mục điện thoại là một danh sách tuyến tính, mỗi phần tử của nó ứng với một đơn vị thuê bao, nó gồm ba trường:

-Tên đơn vị hoặc tên chủ hộ thuê bao.

-Địa chỉ

-Số điện thoại

Mỗi một phần tử được xác định bằng địa chỉ của chúng trong bộ nhớ trong. Thường thì có hai cách để xác định được địa chỉ của một phần tử trong danh sách. Cách thứ nhất là dựa vào những đặc tả của dữ liệu cần tìm. Địa chỉ thuộc loại này được gọi là địa chỉ tính được (computed ađress). Cách này thường hay được sử dụng trong các ngôn ngữ lập trình để tính địa chỉ các phần tử của vector, của ma trận để tính địa chỉ lệnh thực hiện tiếp theo trong quá trình thực hiện chương trình đích. Cách thứ hai là lưu trữ các địa chỉ cần thiết đó ở một chỗ nào đó trong bộ nhớ, khi cần xác định sẽ lấy ở đó ra. Loại địa chỉ này được gọi là con trỏ (pointer) hoặc móc nối (link).

Đối với một trang sách, ngoài phép bổ sung và loại bỏ còn có một số phép sau đây cũng hay được tác động:

- Ghép hai hoặc nhiều danh sách

- Tách một danh sách thành nhiều danh sách

- Sao chép một danh sách

- Sắp xếp các phần tử trong danh sách theo một thứ tự nhất định

- Tìm kiếm trong danh sách,...

Stack hay danh sách kiểu ngăn xếp

Stack là một kiểu danh sách tuyến tính đặc biệt mà phép bổ sung và phép loại bỏ luôn luôn thực hiện ở một đầu gọi là đỉnh (top). Bạn có thể hình dung nó như cơ cấu của một hộp chứa đạn súng. Lắp đạn vào hay lấy đạn ra cũng chỉ ở một đầu hộp. Viên đạn mới nạp vào sẽ nằm ở đỉnh còn viên nạp vào đầu tiên thì nằm ở đáy (bottom). Viên nạp vào sau cùng lại chính là viên lên nòng súng trước tiên.

Nguyên tắc vào sau ra trước như vậy của Stack được gọi là danh sách kiểu LIFO (Last-In-First-Out). Stack có thể rỗng hoặc bao gồm một số phần tử.

Lưu trữ Stack bằng mảng

Có thể lưu trữ stack bởi một vectơ lưu trữ S gồm n phần tử kế tiếp. Nếu T là địa chỉ của phần tử ở đỉnh của Stack thì T sẽ có giá trị biến đổi khi có giá trị biến đổi khi Stack hoạt động (vì vậy người ta gọi T là một biến trỏ). Khi Stack rỗng, ta quy ước T = 0 và mỗi lần bổ sung một phần tử mới vào Stack thì T sẽ tăng lên 1. Khi một phần tử bị loại ra khỏi Stack, T sẽ giảm đi 1.

Sau đây là thuật giải bổ sung và loại bỏ đối với Stack:

Procedure PUSH (S, T, X)

{

giải thuật này thực hiện bổ sung phần tử X vào Stack lưu trữ bởi vectơ S có n phần tử. T là con trỏ trỏ tới đỉnh Stack }

1. { Kiểm tra xem Stack có tràn không tức là khi S không còn chỗ để tiếp tục lữu trữ các phần tử của Stack nữa }

If T >= n then

Begin

writeln (Stack tràn);

return

end ;

2. {Chuyển con trỏ}

T:= T+1;

3. {Bổ sung phần tử mới X}

S[T]:= X;

4. return;

Function POP(S, T)

{hàm này thực hiện việc loại bỏ phần tử ở đỉnh Stack S đang trỏ tới T, phần tử loại bỏ sẽ được thu nhận và được đưa ra }

1. {kiểm tra xem Stack có cạn không khi Stack đã rỗng (empty) tức là không còn phần tử nào để loại bỏ nữa}

if T<=0 then

begin

writeln("Stack cạn !");

return

end;

2. {chuyển con trỏ }

T:=T-1;

3. {đưa phần tử bị loại ra}

POP:= S[T+1];

4. return;

Các bạn có thể khảo sát các ứng dụng của Stack thông qua các bài toán: Đổi cơ số từ số nguyên thập phân sang nhị phân,...

Theo nguồn THNT