Ngăn xếp trong cấu trúc dữ liệu

Ngăn xếp (Stack) là một cấu trúc dữ liệu tuân theo nguyên tắc LIFO (Last In, First Out) – phần tử vào cuối cùng sẽ ra đầu tiên. Dưới đây là hai cách phổ biến để hiện thực ngăn xếp: sử dụng mảng và sử dụng danh sách liên kết đơn có nút đầu (head node).

1. Ngăn xếp dùng mảng

Ý tưởng chính:

• Sử dụng biến top để theo dõi vị trí đỉnh ngăn xếp, khởi tạo top = -1.
• Khi thêm phần tử (push): tăng top rồi gán giá trị vào stack[top].
• Khi lấy phần tử (pop): trả về stack[top] rồi giảm top.
• Duyệt ngăn xếp: lặp từ top về 0.

Triển khai mã nguồn

class StackUsingArray {
    private int capacity;
    private int[] data;
    private int topIndex;

    public StackUsingArray(int size) {
        this.capacity = size;
        this.data = new int[capacity];
        this.topIndex = -1;
    }

    public boolean isFull() {
        return topIndex == capacity - 1;
    }

    public boolean isEmpty() {
        return topIndex == -1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("Ngăn xếp đầy, không thể thêm!");
            return;
        }
        data[++topIndex] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Ngăn xếp rỗng!");
        }
        return data[topIndex--];
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("Không có dữ liệu để hiển thị.");
            return;
        }
        for (int i = topIndex; i >= 0; i--) {
            System.out.printf("Vị trí %d: %d\n", i, data[i]);
        }
    }
}

Chương trình kiểm thử

import java.util.Scanner;

public class ArrayStackTest {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        StackUsingArray stack = new StackUsingArray(4);
        boolean running = true;

        while (running) {
            System.out.println("\n--- Menu ---");
            System.out.println("1. Hiển thị ngăn xếp");
            System.out.println("2. Đưa phần tử vào (push)");
            System.out.println("3. Lấy phần tử ra (pop)");
            System.out.println("4. Thoát");
            System.out.print("Lựa chọn: ");
            int choice = input.nextInt();

            switch (choice) {
                case 1:
                    stack.display();
                    break;
                case 2:
                    System.out.print("Nhập giá trị cần thêm: ");
                    int val = input.nextInt();
                    stack.push(val);
                    System.out.println("Thêm thành công!");
                    break;
                case 3:
                    try {
                        int result = stack.pop();
                        System.out.println("Phần tử lấy ra: " + result);
                    } catch (RuntimeException e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 4:
                    running = false;
                    System.out.println("Kết thúc chương trình.");
                    break;
                default:
                    System.out.println("Lựa chọn không hợp lệ.");
            }
        }
        input.close();
    }
}

2. Ngăn xếp dùng danh sách liên kết đơn

Ý tưởng chính:

• Sử dụng một nút đầu (top) trỏ đến phần tử đỉnh.
• Không giới hạn kích thước như mảng.
• Thêm phần tử: chèn vào đầu danh sách (head insertion).
• Lấy phần tử: loại bỏ và trả về nút đầu tiên sau nút header.
• Duyệt: bắt đầu từ top.next, di chuyển qua từng nút kế tiếp.

Định nghĩa lớp nút

class Node {
    private int data;
    private Node next;

    public Node(int value) {
        this.data = value;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int value) {
        this.data = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node node) {
        this.next = node;
    }
}

Hiện thực ngăn xếp

class StackUsingLinkedList {
    private Node top;

    public StackUsingLinkedList() {
        this.top = new Node(-1); // Nút giả làm điểm khởi đầu
    }

    public boolean isEmpty() {
        return top.getNext() == null;
    }

    public void push(Node newNode) {
        newNode.setNext(top.getNext());
        top.setNext(newNode);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Ngăn xếp rỗng!");
        }
        Node temp = top.getNext();
        top.setNext(temp.getNext());
        return temp.getData();
    }

    public void traverse() {
        if (isEmpty()) {
            System.out.println("Ngăn xếp đang trống.");
            return;
        }
        Node current = top.getNext();
        System.out.println("Các phần tử trong ngăn xếp:");
        while (current != null) {
            System.out.println("Dữ liệu: " + current.getData());
            current = current.getNext();
        }
    }
}

Chương trình kiểm thử danh sách liên kết

import java.util.Scanner;

public class LinkedListStackTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StackUsingLinkedList stack = new StackUsingLinkedList();
        boolean active = true;

        while (active) {
            System.out.println("\n=== Quản lý ngăn xếp ===");
            System.out.println("show  – Hiển thị tất cả phần tử");
            System.out.println("push  – Thêm phần tử mới");
            System.out.println("pop   – Lấy phần tử khỏi đỉnh");
            System.out.println("exit  – Thoát chương trình");
            System.out.print("Chọn thao tác: ");
            String command = scanner.next();

            switch (command) {
                case "show":
                    stack.traverse();
                    break;
                case "push":
                    System.out.print("Nhập giá trị muốn thêm: ");
                    int num = scanner.nextInt();
                    stack.push(new Node(num));
                    System.out.println("Đã thêm " + num + " vào ngăn xếp.");
                    break;
                case "pop":
                    try {
                        int removed = stack.pop();
                        System.out.println("Lấy ra giá trị: " + removed);
                    } catch (RuntimeException e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    active = false;
                    System.out.println("Chương trình đã thoát.");
                    break;
                default:
                    System.out.println("Lệnh không hợp lệ, vui lòng thử lại.");
            }
        }
        scanner.close();
    }
}