Ngăn xếp (Stack)

Ngăn xếp (Stack) là một cấu trúc dữ liệu trong lập trình, được sử dụng để lưu trữ các phần tử theo cách LIFO (Last-In-First-Out), nghĩa là phần tử cuối cùng được đưa vào sẽ là phần tử đầu tiên được lấy ra.

Ngăn xếp được biểu diễn dưới dạng một danh sách các phần tử, với hai hoạt động chính là đẩy (push) và lấy (pop). Khi một phần tử được đưa vào ngăn xếp, nó sẽ được đặt trên đầu ngăn xếp. Khi một phần tử được lấy ra khỏi ngăn xếp, phần tử trên đầu ngăn xếp sẽ được lấy ra và ngăn xếp sẽ trở thành ngăn xếp mới với phần tử tiếp theo trên đầu ngăn xếp.

Các hoạt động khác của ngăn xếp bao gồm xem phần tử đầu tiên trên đỉnh ngăn xếp mà không xóa nó (peek), kiểm tra xem ngăn xếp có trống hay không (isEmpty) và xóa toàn bộ các phần tử khỏi ngăn xếp (clear).

Ngăn xếp được sử dụng rộng rãi trong các thuật toán về đệ quy, phân tích cú pháp, trình biên dịch và các ứng dụng khác trong lập trình.

Để sử dụng ngăn xếp trong Python, chúng ta có thể sử dụng cấu trúc dữ liệu stack được tích hợp sẵn trong thư viện của Python hoặc tự tạo một class ngăn xếp.

Dưới đây là một ví dụ đơn giản về cách sử dụng list trong Python để tạo ngăn xếp và thực hiện các hoạt động cơ bản:

stack = [] # tạo một list rỗng để lưu trữ các phần tử trong ngăn xếp

# Kiểm tra xem ngăn xếp có trống hay không
def is_empty():
    return len(stack) == 0

# Thêm một phần tử vào đầu ngăn xếp
def push(item):
    stack.append(item)

# Lấy phần tử trên đầu ngăn xếp và xóa nó khỏi ngăn xếp
def pop():
    if is_empty():
        return "Ngăn xếp đã trống"
    else:
        return stack.pop()

# Xem phần tử đầu tiên trên đỉnh ngăn xếp mà không xóa nó
def peek():
    if is_empty():
        return "Ngăn xếp đã trống"
    else:
        return stack[-1]

# Xóa toàn bộ các phần tử khỏi ngăn xếp
def clear():
    stack.clear()

# Thực hiện các hoạt động với ngăn xếp
push(1)
push(2)
push(3)
print(stack) # [1, 2, 3]
print(peek()) # 3
print(pop()) # 3
print(stack) # [1, 2]
clear()
print(stack) # []

Để sử dụng ngăn xếp trong C++, chúng ta có thể sử dụng cấu trúc dữ liệu stack được tích hợp sẵn trong thư viện STL (Standard Template Library) hoặc tự tạo một class ngăn xếp.

Dưới đây là ví dụ về cách tạo một class ngăn xếp trong C++:

#include <iostream>
#include <stack>
using namespace std;

class Stack {
private:
    stack<int> st;
public:
    bool is_empty() {
        return st.empty();
    }
    void push(int x) {
        st.push(x);
    }
    void pop() {
        if (!is_empty()) {
            st.pop();
        }
    }
    int top() {
        if (!is_empty()) {
            return st.top();
        }
        return -1;
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << "Top element: " << s.top() << endl;
    s.pop();
    cout << "Top element after pop: " << s.top() << endl;
    s.pop();
    s.pop();
    if (s.is_empty()) {
        cout << "Stack is empty." << endl;
    }
    else {
        cout << "Stack is not empty." << endl;
    }
    return 0;
}

Trong ví dụ trên, chúng ta định nghĩa một class ngăn xếp và sử dụng class stack trong thư viện STL để lưu trữ các phần tử trong ngăn xếp. Chúng ta định nghĩa các phương thức is_empty(), push(), pop(), top() để kiểm tra xem ngăn xếp có trống hay không, thêm phần tử vào đỉnh ngăn xếp, lấy phần tử trên đỉnh ngăn xếp và xóa nó khỏi ngăn xếp, xem phần tử đầu tiên trên đỉnh ngăn xếp mà không xóa nó. Trong hàm main(), chúng ta tạo một đối tượng ngăn xếp và sử dụng các phương thức đã định nghĩa để thực hiện các hoạt động trên ngăn xếp.

Dưới đây là một ví dụ về cách sử dụng ngăn xếp trong C++ không dùng class:

#include <iostream>
#define MAX_SIZE 100
using namespace std;

int stack[MAX_SIZE];
int top = -1;

bool is_empty() {
    return top == -1;
}

bool is_full() {
    return top == MAX_SIZE - 1;
}

void push(int x) {
    if (!is_full()) {
        top++;
        stack[top] = x;
    }
}

void pop() {
    if (!is_empty()) {
        top--;
    }
}

int top_element() {
    if (!is_empty()) {
        return stack[top];
    }
    return -1;
}

int main() {
    push(1);
    push(2);
    push(3);
    cout << "Top element: " << top_element() << endl;
    pop();
    cout << "Top element after pop: " << top_element() << endl;
    pop();
    pop();
    if (is_empty()) {
        cout << "Stack is empty." << endl;
    }
    else {
        cout << "Stack is not empty." << endl;
    }
    return 0;
}

Trong ví dụ này, chúng ta sử dụng một mảng đơn giản để lưu trữ các phần tử trong ngăn xếp. Chúng ta định nghĩa các hàm is_empty(), is_full(), push(), pop(), top_element() để kiểm tra xem ngăn xếp có trống hay không, kiểm tra xem ngăn xếp đã đầy chưa, thêm phần tử vào đỉnh ngăn xếp, lấy phần tử trên đỉnh ngăn xếp và xóa nó khỏi ngăn xếp, xem phần tử đầu tiên trên đỉnh ngăn xếp mà không xóa nó. Trong hàm main(), chúng ta sử dụng các hàm đã định nghĩa để thực hiện các hoạt động trên ngăn xếp.

Lập trình C/C++, Lập trình Python

Ngăn xếp (Stack)

Trả lời Hủy