Stack – Cấu trúc dữ liệu ngăn xếp | How Kteam

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Trong bài này, Kteam sẽ giới thiệu đến bạn một cấu trúc dữ liệu được sử dụng rất nhiều trong các bài toán –
đó chính là ngăn xếp – Stack. Cùng tìm hiểu xem
Stack là gì và cách sử dụng như thế nào nhé!

Nội dung

Để hoàn toàn có thể hiểu được bài học kinh nghiệm này một cách tốt nhất, những bạn nên có kiến thức và kỹ năng cơ bản về những phần :

Trong bài học này chúng ta sẽ tìm hiểu về:

  • Khái niệm stack
  • Cách cài đặt stack thủ công
  • Cách sử dụng stack có trong C++

Bài toán đặt ra

Ta có một bài toán như sau :
Cho một dãy số gồm n số nguyên dương ai ( n ≤ 106, ai ≤ 109 ). Với mỗi vị trí i, hãy in ra vị trí j gần nhất về phía bên trái thoả mãn ai < aj. Nếu như không có thành phần nào thoả mãn in ra - 1 . Ví dụ :

Input Output

7
2 1 3 2 8 5 7

 – 1 1 – 1 3 – 1 5 5

Phương hướng suy nghĩ

Thông thường, khi xử lý một bài toán, ta sẽ tiếp cận theo những bước sau :

  • Đề bài bảo gì ta sẽ đi làm cái đó, nỗ lực tâm lý ra một thuật toán đơn thuần nhất phân phối được nhu yếu đề bài mà không cần chăm sóc đến thời hạn hay bộ nhớ ( Cách này được gọi là “ chạy trâu ” ) .
  • Từ thuật toán bắt đầu, tìm kiếm những cấu trúc tài liệu để tối ưu thời hạn hoặc đưa ra những đặc thù, nhận xét để rút ra được một số ít đặc thù của bài toán .
  • Từ những nhận xét trên, tìm ra giải thuật tối ưu của bài toán

Lời giải ban đầu

Theo như để bài nhu yếu thì ta sẽ cần tìm thành phần gần nhất bên trái mà lớn hơn thành phần hiện tại. Do đó, theo cách tâm lý thường thì, với mỗi vị trí, ta sẽ duyệt từ phải qua trái từ vị trí hiện tại, thành phần tiên phong mà lớn hơn thành phần hiện tại chính là vị trí cần tìm .
Ta sẽ thực thi thuật toán như sau : Với mỗi vị trí i, ta sẽ duyệt ngược toàn bộ những vị trí j theo thứ tự từ i – 1 đến 0 ( Mảng trong C + + mở màn từ 0 ). Nếu gặp được một vị trí j mà aj > ai thì ta sẽ in ra hiệu quả và huỷ bỏ vòng lặp. Nếu như duyệt đến 0 mà vẫn không hề tìm ra j thoả mãn thì in ra – 1 .
Một chút quan tâm cho những bạn trước khi đọc code của mình. Trong suốt khoá học này, mình sẽ sử dụng đọc và ghi tài liệu lần lượt ra hai file text “ CTDL.inp ” và “ CTDL.out ”. Do đó, nếu những bạn copy code mình và muốn chạy trên máy bản thân thì cần tạo ra hai file này ở dạng text ở cùng thư mực chứa code của những bạn .
Cách này sẽ được code như sau :

#include
using namespace std;
 
const int MaxN = 1e6 + 1;
 
int n, a[MaxN];
 
int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    for(int i = 0 ; i < n ; ++i){
        int pos = -1; // Khởi tạo giá trị kết quả ban đầu
        for(int j = i - 1 ; j >= 0 ; --j)
        if(a[j] > a[i]){
            // Nếu tìm thấy vị trí j thoả mãn thì ghi lại và dừng vòng lặp
            pos = j;
            break;
        }
        // Kiểm tra xem có tồn tại vị trí j không, nếu có thì giá trị pos sẽ nằm trong đoạn [0, n – 1]
        // In ra phải cộng 1 do chỉ số mảng trong C++ bắt đầu từ 0
        if(pos >= 0) cout << pos + 1 << " ";
        else cout << -1 << " ";
    }
 
    return 0;
}

Sau khi chạy, ta thấy cách này là một cách trọn vẹn đúng. Tuy nhiên ta thấy chương trình sử dụng hai vòng lặp lồng nhau. Trong trường hợp xấu nhất, vòng lặp j sẽ phải lặp lại n-1 lần. Do đó, độ phức tạp của cách này lên tới O ( n2 ). Nếu trong những kì thi số lượng giới hạn thời hạn là 1 s cho mỗi chương trình và n = 106 thì cách này là không đủ tốt .

Nhận xét

Hãy xét một dãy như sau : [ 5, 1, 2, 3, 4 ]
Giả xử ta đang ở vị trí i = 4 ( ai = 4 ), theo như code bắt đầu của tất cả chúng ta thì ta sẽ phải xét cả những vị trí j = 1, 2. Ta thấy những giá trị tại j = 1, 2 còn nhỏ hơn tại j = 3 nên nếu j = 3 không thoả mãn thì xét qua những vị trí j = 1, 2 là trọn vẹn không có ý nghĩa. Do đó, ta nghĩ đến việc làm sao để chỉ xét những vị trí có năng lực thỏa mãn nhu cầu chứ không xét hàng loạt .

Cách giải cải tiến

Từ nhận xét trên, ta sẽ có một tập b gọi là “ ứng viên ” bộc lộ cho vị trí trong dãy a. Tập này sẽ có đặc thù sau :

 biabj
(∀i

Ví dụ : Dãy b là [ 2, 4, 6 ] thì a2 > a4 > a6 .
Khi đó, ta có một thuật toán như sau :

  • Với mỗi vị trí i, ta sẽ vô hiệu tổng thể những ứng viên j ở cuối tập mà aj < ai.
  • Xét tập ứng viên, ứng viên sau cuối trong tập chính là vị trí cần tìm. Nếu như tập rỗng có nghĩa là không sống sót vị trí thoả mãn .
  • Đẩy vị trí i vào cuối tập.

Hãy tưởng tượng luồng chạy của chương trình trong ví dụ trên :

  • Đầu tiên, xét i = 0. Hiện tại tập ứng viên đang rỗng. Do đó sẽ không có số nào lớn hơn a0 mà đứng trước nó. In ra – 1 và đẩy i = 0 vào tập ứng viên
  • Xét i = 1. Hiện tại, tập ứng viên đang có 1 đề cử là vị trí j = 0. Ta thấy đề cử thỏa mãn nhu cầu do a0 > a1. Do đó in ra đề cử và đẩy i = 1 vào tập ứng viên. Lúc này tập vẫn phân phối đặc thù nêu trên .
  • Xét i = 2. Hiện tại, tập ứng viên là [ 0, 1 ], đề cử cho vị trí i = 2 đang là vị trí j = 1. Sẽ có bạn đặt ra câu hỏi tại sao lại xét ứng viên sau cuối. Lí do là do dãy b tăng dần nên vị trí ở cuối sẽ là vị trí gần i nhất về phía bên trái. Tuy nhiên, vị trí j này không phân phối nhu yếu. Đây là lúc mà ta cần quan tâm. Do tổng thể những vị trí i về sau đều tìm về vị trí gần nhất bên trái nên một khi sống sót i sao cho ai> ajthì vị trí j sẽ không khi nào được lựa chọn. Thật vậy, nếu như có một vị trí k nhận vị trí j làm tác dụng mà không phải là vị trí i thì có nghĩa là ( aj> akvà ak> ai) hay aj> ai( Trái với giả thiết ). Do đó vô hiệu vị trí j = 1 ra khỏi tập. Tương tự với j = 0. Lúc này tập ứng viên rỗng. In ra – 1 và đẩy i = 2
    vào tập.
  • Cách triển khai với những giá trị i = 3, 4, 5, 6 là tựa như

Như vậy, chương trình của tất cả chúng ta sẽ yên cầu một cấu trúc tài liệu có năng lực phân phối những nhu yếu sau :

  • Cho một thành phần vào cuối dãy
  • Đẩy thành phần cuối dãy ra ngoài

Đó chính là lúc mà cấu trúc tài liệu stack phát huy sức mạnh của mình. Bây giờ hãy cùng nhau khám phá cụ thể về stack nhé .

Khái niệm stack

Stack là một cấu trúc tài liệu hoạt động giải trí theo nguyên tắc Last In First Out. Hiểu đơn thuần là thành phần sẽ được thêm vào cuối stack và khi lấy ra ta cũng sẽ lấy thành phần cuối stack ( thành phần được thêm vào gần nhất ) .
Một ví dụ trong thực tiễn của stack mà những bạn hoàn toàn có thể dễ tưởng tượng được đó chính là hộp cầu lông. Khi muốn cho cầu vào trong hộp ta sẽ cho cầu vào đáy hộp cầu và khi muốn lấy cầu ra thì ta sẽ lấy quả cầu gần nhất được cho vào .

Một stack sẽ tương hỗ những thao tác cơ bản sau :

Cách cài đặt stack thủ công

Cơ chế hoạt động của stack

Ta sẽ có mảng a giả làm stack và giá trị sz biểu lộ kích cỡ của stack như sau :

Ban đầu, mảng a rỗng và sz = 0

Chèn phần tử cuối stack

Để chèn thành phần cuối stack thì ta chỉ cần gán thành phần ở vị trí sz ( vị trí trống ở cuối ) giá trị cần thêm vào rồi tăng giá trị sz bộc lộ việc stack tăng size .
Ví dụ như khi ta thêm 3 vào stack thì ta được

Sau đó nếu như ta thêm 5 vào stack thì ta được

 

Loại bỏ phần tử cuối stack

Nếu muốn bỏ thành phần cuối stack thì đơn thuần là ta sẽ giảm giá trị sz đi 1. Khi này, nếu như chèn thành phần mới vào thì thành phần 5 tự nhiên sẽ bị vô hiệu .

Ở đây có chú ý quan tâm quan trọng cho những bạn : Phải bảo vệ stack không rỗng ( sz > 0 ). Nếu không, hoàn toàn có thể sz sẽ có giá trị âm dẫn đến Runtime Error ( mảng không có chỉ số âm ) .

Lấy giá trị cuối trong stack

Ta thấy giá trị cuối trong stack nằm ở vị trí sz – 1 nên đơn thuần là trả về thành phần ở vị trí sz – 1
Ở đây có chú ý quan tâm quan trọng cho những bạn : Phải bảo vệ stack không rỗng ( sz > 0 ). Nếu không, hoàn toàn có thể sz sẽ có giá trị âm dẫn đến Runtime Error ( mảng không có chỉ số âm ) .

Lấy kích thước stack

Ta thấy size chính là biến sz do đó chỉ cần trả về biến sz là được .

Code

struct CustomStack{
    int sz = 0; // Kích thước stack
    int a[int(1e6 + 1)]; // Mảng được giả làm stack với kích thước tối đa 1e6
 
    // Thêm phần tử vào stack
    void push(int element){
        a[sz] = element;
        sz++;
    }
 
    // Xoá phần tử khỏi stack
    void pop(){
        if(sz) sz--;
    }
 
    // Lấy giá trị cuối cùng trong stack
    int top(){
        if(sz) return a[sz - 1];
    }
 
    // Lấy kích thước stack
    int getSize(){
        return sz;
    }
};

Cách sử dụng stack có trong C++

Stack được setup ở trên là tương đối ổn. Tuy nhiên, trong C + + đã được thiết kế xây dựng sẵn stack với hiệu suất cao tốt nên việc thiết kế xây dựng trên là không thật sự thiết yếu trong đa số những trường hợp .

Khai báo stack

Thông thường để thêm stack vào chương trình, tất cả chúng ta sẽ thêm thư viện như sau :

#include

Tuy nhiên, ở trong suốt khoá học này mình sẽ sử dụng header sau :

#include

Header này sẽ giúp tất cả chúng ta thêm toàn bộ những thư viện về những cấu trúc tài liệu mà tất cả chúng ta sẽ học trong khóa học này .
Ta sẽ khai báo stack như sau :

stack <{kiểu dữ liệu}> {tên
stack};

Ví dụ: stack myStack;

Ngoài ra hoàn toàn có thể khởi tạo stack với mảng giá trị cho trước. Tuy nhiên mình ít khi gặp phải trường hợp này trong trong thực tiễn. Các bạn hoàn toàn có thể tìm hiểu và khám phá thêm về những cách khởi tạo stack khác .

Các phương thức trong stack

Các phương pháp cơ bản trong stack của C + + :

  • push: Thêm phần tử vào cuối

    stack

  • pop: Loại bỏ phần tử cuối

    stack

  • top:

    Trả về giá trị làthành phần cuối trongstack

  • size:

    Trả về giá trị nguyên làsố thành phần đang có trongstack

  • empty:

    Trả về một giá trị bool, true nếu
    stackrỗng, false nếu stackkhông rỗng

Các phương pháp trên sẽ đều mất độ phức tạp O ( 1 ) .
Mình có một đoạn code demo về những phương pháp cơ bản của stack như sau :

#include
using namespace std;
 
stack st;
 
int main(){
    // Thêm các phần tử vào stack
    st.push(1);
    st.push(3);
    st.push(5);
    // Hiện tại stack là [1, 3, 5]
 
    // In ra phần tử cuối cùng trong stack và kích thước stack
    cout << "Phan tu cuoi cung trong stack la:" << st.top() << endl;
    cout << "Kich thuoc hien tai cua stack la:" << st.size() << endl;
 
    // Loại bỏ 1 phần tử ra khỏi stack
    st.pop();
    cout << "Loai bo phan tu cuoi ra khoi stack" << endl;
    // Hiện tại stack là [1, 3]
 
    // Kiểm tra stack có rỗng không
    if(st.empty()) cout << "Stack rong" << endl;
    else cout << "Stack khong rong" << endl;
 
    // Sau khi loại bỏ 1 phần tử ra in ra phần tử cuối cùng trong stack và kích thước stack
    cout << "Phan tu cuoi cung trong stack la:" << st.top() << endl;
    cout << "Kich thuoc hien tai cua stack la:" << st.size() << endl;
 
    // Loại bỏ tất cả các phần tử ra khỏi stack
    while(st.size() > 0) st.pop();
 
    // Kiểm tra stack có rỗng không
    if(st.empty()) cout << "Stack rong" << endl;
    else cout << "Stack khong rong" << endl;
}

Khi chạy đoạn code trên ta thu được tác dụng như sau :

Lưu ý: Các phương thức như pop, top nếu được gọi khi stack rỗng sẽ dẫn đến
Runtime Error. Do đó, cần phải đảm bảo stack không rỗng trước khi gọi các phương thức này. Để kiểm tra stack có rỗng hay không thì các bạn có thể sử dụng phương thức
empty() mà mình đã nêu ở trên.

Ứng dụng stack vào giải quyết bài toán ban đầu

Vậy sau khi biết về stack thì bài toán bắt đầu sẽ được code như sau :

#include
using namespace std;
 
const int MaxN = 1 + 1e6;
 
int n, a[MaxN];
stack st;
 
int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    for(int i = 0 ; i < n ; ++i){
        // Các bạn chú ý phương thức kiểm tra empty() luôn phải được đặt 
        trước khi gọi top() hoặc pop()
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        if(!st.empty()) cout << st.top() + 1 << " ";
        else cout << "-1" << " ";
        st.push(i);
    }
 
    return 0;
}

Hãy quan tâm vào độ phức tạp của thuật toán này : Ta thấy dù có vòng lặp while trong vòng lặp for tuy nhiên hai vòng lặp này trọn vẹn không phụ thuộc vào vào nhau ( Khác với ở giải thuật khởi đầu ). Các thành phần trong mảng a chỉ ra và vào stack tổng số tối đa là 2 lần đo đó trong hàng loạt chương trình, vòng lặp while sẽ chỉ triển khai tối đa 2 n thao tác O ( 1 ). Do đó thuật toán sẽ có độ phức tạp O ( n ). So với thuật toán khởi đầu có độ phức tạp O ( n2 ) thì đây là nâng cấp cải tiến đáng kể .

Về việc sử dụng stack có sẵn và stack tự xây dựng

Như mình có nói, stack trong C + + sẽ tốt hơn trong phần lớn những trường hợp. Vậy có khi nào tất cả chúng ta sẽ cần stack tự thiết kế xây dựng không ? Câu vấn đáp là vẫn có. Vậy thì đó là khi nào ? Các bạn hoàn toàn có thể thấy, thực chất của stack tự kiến thiết xây dựng vẫn là mảng. Do đó, ta hoàn toàn có thể truy vấn ngẫu nhiên vào bất kể thành phần nào, khác với stack trong C + + chỉ hoàn toàn có thể lấy thành phần ở đầu cuối ra. Do đó, nếu những bạn vì nguyên do gì đó cần truy vấn nhiều hơn 1 thành phần ở cuối thì nên dùng stack tự thiết kế xây dựng .
Ngoài ra, trong C + + có một cấu trúc tài liệu là vector. Các bạn trọn vẹn hoàn toàn có thể đọc về vector và sử dụng nó như stack. vector sẽ là sự dung hòa tốt những điểm lợi giữa stack tự thiết kế xây dựng ( truy vấn ngẫu nhiên ) và stack có sẵn ( tiện nghi, bảo đảm an toàn ) .

Kết luận

Qua bài này tất cả chúng ta đã nắm được khái niệm stack cũng như là cách setup và vận dụng trong thực tiễn .

Bài sau chúng ta sẽ bắt đầu tìm hiểu về cấu trúc dữ liệu
Queue và Deque.

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Thảo luận

Nếu bạn có bất kể khó khăn vất vả hay vướng mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI và ĐÁP trên thư viện Howkteam. com để nhận được sự tương hỗ từ hội đồng .

admin