Cấu trúc dữ liệu Stack

Stack Data Structure (Cấu trúc dữ liệu ngăn xếp)

Trong hướng dẫn này, bạn sẽ học về cấu trúc dữ liệu ngăn xếp và nó sẽ được thực hiện trong ngôn ngữ Javascript.

Ngăn xếp (Stack) là 1 cấu trúc dữ liệu tuyến tính theo nguyên tắc Last In First Out (LIFO) Nhập sau, xuất trước. Điều này nghĩa là phần tử cuối cùng được chèn bên trong ngăn xếp cũng là phần tử đầu tiên được loại bỏ.

Bạn có thể hình dung cấu trúc dữ liệu ngăn xếp như chồng đĩa được chồng lên nhau.

Bạn có thể:

• Đặt một đĩa mới lên đầu
• Loại bỏ đĩa trên cùng khỏi chồng đĩa.

Và, nếu bạn muốn chiêc đĩa ở vị trí cuối cùng, thì bạn phải loại bỏ tất cả những chiếc đĩa khác trên nó. Điều này mô tả cách chính xác cách cấu trúc dữ liệu ngăn xếp hoạt động.

Nguyên tắc LIFO của ngăn xếp (Stack)

Trong các thuật ngữ của lập trình, đặt một item lên trên ngăn xếp được gọi là push và loại bỏ một mục được gọi là pop.

Trong ảnh trên, có 2 phần tử 1 và 2 được đặt vào trước, và 3 được đặt sau cùng, tuy nhiên nó lại được loại bỏ đầu tiên.

Chúng tôi có thể thực hiện 1 ngăn xếp cho bất kỳ ngôn ngữ lập trình nào, nhưng đặc điểm kỹ thuật là khá giống nhau.

Hoạt động cơ bản của ngăn xếp

Có một vài hoạt động cơ bản cho phép chúng tôi thực hiện các hành động khác nhau trên một ngăn xếp.

• Push: Thêm 1 phần tử lên đầu của ngăn xếp
• Pop: Loại bỏ 1 phần tử ở vị trí đầu tiên của ngăn xếp
• IsEmpty: Kiểm tra nếu ngăn xếp trống
• IsFull: Kiểm tra nếu ngăn xếp đầy
• Peek: Lấy giá trị của phần tử đầu tiên mà không loại bỏ nó

Làm việc với Cấu trúc dữ liệu ngăn xếp

Ngăn xếp hoạt động như sau:

1. Một con trỏ được gọi là TOP được sử dụng để theo dõi phần tử trên cùng của ngăn xếp.
2. Khi khởi tạo ngăn xếp, chúng tôi đặt giá trị của nó thành -1 để chúng tôi có thể kiểm tra xem ngăn xếp có trống không bằng cách so sánh TOP == -1.
3. Khi push 1 phần tử, chúng tôi tăng giá trị của TOP và đặt phần tử mới vào vị trí mà TOP chỉ đến.
4. Khi pop một phần tử, chúng tôi trả về phần tử được trỏ đến bởi TOP và giảm giá trị của nó.
5. Trước khi push, kiểm tra nếu ngăn xếp là đã đầy chưa
6. Trước khi pop, kiểm tra ngăn xếp có trống không

Ngăn xếp được triển khai qua ngôn ngữ lập trình

Cách triển khai ngăn xếp phổ biến nhất là sử dụng mảng, nhưng nó cũng có thể được triển khai bằng cách sử dụng danh sách.

// Stack implementation in Javascript

// Creating a stack
function createStack () {
    stack = [];
    return stack;
};

// Creating an empty stack
function checkEmpty (stack) {
    return stack.length === 0;
};

// Adding items into the stack
function push(stack, item) {
    stack.push(item);
    console.log('pushed item: ', item);
};

// Removing an element from the stack
function pop(stack) {
    if (checkEmpty(stack)) {
        return 'Stack is empty'
    }
    return stack.pop();
};

const stack = createStack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
console.log("popped item: " + pop(stack));
console.log("stack after popping an element: " + stack.toString());

Độ phức tạp của thời gian ngăn xếp

Đối với việc triển khai ngăn xếp dựa trên mảng, các hoạt động push và pop mất thời gian không đổi, tức là O(1).

Ứng dụng của cấu trúc dữ liệu ngăn xếp

Mặc dù ngăn xếp là một cấu trúc dữ liệu đơn giản để triển khai, nhưng nó rất mạnh mẽ. Các ứng dụng phổ biến nhất của ngăn xếp là:

• Đảo ngược một từ - Đặt tất cả các chữ cái trong một ngăn xếp và bật chúng ra. Vì thứ tự LIFO của ngăn xếp, bạn sẽ nhận được các chữ cái theo thứ tự ngược lại.

• Trong trình biên dịch - - Các trình biên dịch sử dụng ngăn xếp để tính giá trị của các biểu thức như 2 + 4/5 * (7 - 9) bằng cách chuyển đổi biểu thức sang dạng tiền tố hoặc hậu tố.

• Trong trình duyệt - Nút quay lại trong trình duyệt lưu tất cả các URL bạn đã truy cập trước đó trong một ngăn xếp. Mỗi lần bạn truy cập một trang mới, nó sẽ được thêm vào trên cùng của ngăn xếp. Khi bạn nhấn nút quay lại, URL hiện tại sẽ bị xóa khỏi ngăn xếp và URL trước đó sẽ được truy cập.

Tham khảo:

• https://www.programiz.com/dsa/stack