Cách Sử Dụng Stack Trong C#

Trong bài bác này, Kteam sẽ giới thiệu đến bạnmột kết cấu dữ liệu được sử dụng không ít trong những bài toán –đó chính là ngăn xếp - Stack.Cùng tò mò xemStacklà gì và cách sử dụng như thế nào nhé!

Nội dung

Để rất có thể hiểu được bài học này một cách xuất sắc nhất, chúng ta nên có kỹ năng cơ bản về các phần:

Nhập, xuất tài liệu qua file trong C++

Trong bài học kinh nghiệm này họ sẽ tò mò về:

Khái niệm stack Cách thiết lập stack thủ công bằng tay Cách áp dụng stack tất cả trong C++

Bài toán để ra

Ta bao gồm một câu hỏi như sau:

Cho một dãy số tất cả n số nguyên dương ai (n≤106,ai109). Cùng với mỗi địa điểm i, hãy in ra vị trí j sớm nhất về phía phía bên trái thoả mãn ai j. Nếu không có phần tử nào đồng tình in ra -1.

Bạn đang xem: Cách sử dụng stack trong c#

Ví dụ:

InputOutput

72 1 3 2 8 5 7

-1 1 -1 3 -1 5 5

Phương phía suy nghĩ

Thông thường, khi giải quyết một bài toán, ta đang tiếp cận theo các bước sau:

Đề bài xích bảo gì ta sẽ đi làm việc cái đó, vậy gắng lưu ý đến ra một thuật toán đơn giản và dễ dàng nhất đáp ứng nhu cầu được yêu mong đề bài xích mà không cần cân nhắc thời gian hay bộ nhớ (Cách này được điện thoại tư vấn là “chạy trâu”).Từ thuật toán ban đầu, tra cứu kiếm các kết cấu dữ liệu để buổi tối ưu thời gian hoặc chuyển ra những tính chất, dìm xét để rút ra được một số điểm sáng của bài toán.Từ các nhận xét trên, tìm ra lời giải tối ưu của bài bác toán

Lời giải ban đầu

Theo như để bài yêu mong thì ta sẽ phải tìm thành phần gần nhất phía bên trái mà béo hơn bộ phận hiện tại. Vì đó, theo cách để ý đến thông thường, với mỗi vị trí, ta sẽ coi xét từ đề xuất qua trái từ vị trí hiện tại, bộ phận đầu tiên mà phệ hơn bộ phận hiện tại chính là vị trí yêu cầu tìm.

Ta sẽ tiến hành thuật toán như sau: cùng với mỗi địa chỉ i, ta sẽ chăm chú ngược toàn bộ các vị trí j theo máy tự trường đoản cú i – 1 đến 0 (Mảng trong C++ ban đầu từ 0). Nếu chạm chán được một địa điểm j cơ mà aj> ai thì ta vẫn in ra hiệu quả và huỷ quăng quật vòng lặp. Giả dụ như duyệt cho 0 nhưng vẫn quan trọng tìm ra j đống ý thì in ra -1.

Một chút chăm chú cho chúng ta trước khi phát âm code của mình. Nhìn trong suốt khoá học tập này, bản thân sẽ thực hiện đọc và ghi dữ liệu lần lượt ra hai tệp tin text “CTDL.inp” và “CTDL.out”. Bởi vì đó, nếu chúng ta copy code mình và ước ao chạy trên máy bạn dạng thân thì cần tạo nên hai file này làm việc dạng text ở thuộc thư mực chứa code của các bạn.

Cách này sẽ tiến hành code như sau:

#includeusing namespace std; const int MaxN = 1e6 + 1; int n, a; int main(){ freopen("CTDL.inp","r",stdin); freopen("CTDL.out","w",stdout); cin >> n; for(int i = 0 ; i > a; for(int i = 0 ; i = 0 ; --j) if(a > a) // giả dụ tìm thấy địa điểm j đồng tình thì khắc ghi và dừng vòng lặp pos = j; break; // kiểm soát xem tất cả tồn tại vị trí j không, nếu tất cả thì quý giá pos sẽ phía bên trong đoạn <0, n – 1> // In ra đề xuất cộng 1 vày chỉ số mảng vào C++ bước đầu từ 0 if(pos >= 0) cout sau khoản thời gian chạy, ta thấy bí quyết này là 1 trong cách trọn vẹn đúng. Tuy vậy tathấy chương trình sử dụng hai vòng lặp lồng nhau. Trong trường thích hợp xấu nhất, vòng lặp j vẫn phải lặp lại n-1 lần. Vày đó,độ tinh vi của cách này lên đến O(n2). Nếu trong các kì thi giới hạn thời gian là 1s cho mỗi chương trình với n = 106 thì bí quyết này là không được tốt.

Nhận xét

Hãy xét một hàng như sau: <5, 1, 2, 3, 4>

Giả xử ta đang ở đoạn i = 4 (ai=4), theo như code ban đầu của họ thì ta sẽ phải xét cả các vị trí j = 1, 2. Ta thấy những giá trị trên j = 1, 2 còn nhỏ hơn trên j = 3 đề xuất nếu j = 3 không mãn nguyện thì xét qua những vị trí j = 1, 2 là hoàn toàn vô nghĩa. Vì chưng đó, ta nghĩ tới việc làm sao nhằm chỉ xét các vị trí có khả năng thỏamãn chứ không cần xét toàn bộ.

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

Từ dấn xét trên, ta sẽ sở hữu một tập b gọi là “ứng cử viên” diễn tả cho vị trí trong dãy a. Tập này sẽ sở hữu được tính chất sau:

bibj vàabi>abj (∀i.

Ví dụ: dãy b là <2, 4, 6> thì a2 > a4> a6.

Khi đó, ta tất cả một thuật toán như sau:

Với mỗi địa điểm i, ta sẽ loại trừ tất cả các ứng cử viên j nghỉ ngơi cuối tập cơ mà aji . Xét tập ứng viên, ứng viên ở đầu cuối trong tập đó là vị trí nên tìm. Trường hợp như tập rỗng tức là không tồn tại vị trí thoả mãn.Đẩy vị trí i vào thời điểm cuối tập.

Hãy tưởng tượng luồng chạy của công tác trong lấy ví dụ trên:

Đầu tiên, xét i = 0. Bây giờ tập ứng viên sẽ rỗng. Do đó sẽ không có số nào to hơn a0mà đứng trước nó. In ra -1 cùng đẩy i = 0 vào tập ứng cử viênXét i = 1. Hiện nay tại, tập người tìm việc đang có một đề cử là vị trí j = 0. Ta thấy đề cử thỏamãn vị a0> a1. Cho nên vì vậy in ra đề cử và đẩy i = 1 vào tập ứng viên. Hôm nay tập vẫn đáp ứng nhu cầu tính hóa học nêu trên.Xét i = 2. Hiện nay tại, tập người tìm việc 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 cuối cùng. Lí do là do dãy b tăng dần nên địa điểm ở cuối vẫn là địa điểm gần i tuyệt nhất về phía bên trái. Tuy nhiên, địa điểm j này không đáp ứng nhu cầu yêu cầu. Đây là lúc mà lại ta yêu cầu chú ý. Do tất cả các vị trí i sau đây đều tìm tới vị trí gần nhất bên trái buộc phải một lúc tồn trên i thế nào cho ai> ajthì địa điểm j vẫn không khi nào được lựa chọn. Thiệt vậy, nếu như như tất cả một địa điểm k thừa nhận vị trí j làm kết quả mà không phải là vị trí i thì có nghĩa là (aj> akvà ak> ai) giỏi aj> ai (Trái với đưa thiết). Bởi đó sa thải 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 = 2vào tập. Cách triển khai với những giá trị i = 3, 4, 5, 6 là tương tự

Như vậy, lịch trình của bọn họ sẽ yên cầu một kết cấu dữ liệu có công dụng đáp ứng các yêu ước sau:

Cho 1 phần tử vào thời gian cuối dãy Đẩy phần tử cuối dãy ra ngoài

Đó đó là lúc mà cấu tạo dữ liệu stackphát huy sức khỏe của mình. Hiện thời hãy cùng cả nhà tìm hiểu cụ thể vềstack nhé.

Khái niệm stack

Stack là một kết cấu dữ liệu chuyển động theo hiệ tượng Last In First Out. Hiểu dễ dàng và đơn giản là phần tử sẽ được sản xuất cuốistack với khi kéo ra ta cũng trở nên lấy bộ phận cuốistack (phần tử được thêm vào gần nhất).

Một lấy ví dụ trong thực tiễn của stack mà các chúng ta có thể dễ tưởng tượng được đó chính là hộp ước lông. Khi ao ước cho cầu vào trong hộp ta vẫn cho ước vào lòng hộp cầu và khi ý muốn lấy mong ra thì ta đang lấy trái cầu sớm nhất được đến vào.

*

*

Một stack sẽ cung ứng các làm việc cơ bạn dạng sau:

Thêm phần tử vào cuối stackLoại bỏ phần tử cuối thoát khỏi stackLấy giá trị cuối trong stackLấy kích cỡ stack

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

Cơ chế buổi giao lưu của stack

Ta sẽ sở hữu mảng a giả làm stackvà quý hiếm sz thể hiện kích thước của stacknhư sau:

*

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

Chèn bộ phận cuối stack

Để chèn thành phần cuối stackthì ta chỉ việc gán bộ phận ở vị trí sz (vị trí trống làm việc cuối) giá chỉ trị phải thêm vào rồi đội giá trị sz thể hiện việcstack tăng kích thước.

Ví dụ như lúc ta thêm 3 vào stack thì ta được

*

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

*

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

Nếu muốn bỏ thành phần cuối stack thì dễ dàng và đơn giản là ta sẽ áp dụng chính sách ưu đãi giảm giá trị sz đi 1.Khi này, ví như như chèn bộ phận mới vào thì thành phần 5 tự nhiên và thoải mái sẽ bị loại bỏ bỏ.

*

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

Xem thêm: Trái Cherry Bán Ở Đâu Tphcm Ở Đâu Giá Tốt Và Đảm Bảo Hàng Nhập Khẩu

Lấy giá trị cuối vào stack

Ta thấy cực hiếm cuối vào stack nằm tại phần sz – 1 nên đơn giản dễ dàng là trả về bộ phận ở địa chỉ sz – 1

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

Lấy kích thước stack

Ta thấy kích thước chính là biến sz bởi vì đó chỉ cần trả về thay đổi sz là được.

Code

struct CustomStack int sz = 0; // size stack int a; // Mảng được giả có tác dụng stack với size tối đa 1e6 // Thêm bộ phận vào stack void push(int element) a = element; sz++; // Xoá bộ phận khỏi stack void pop() if(sz) sz--; // lấy giá trị ở đầu cuối trong stack int top() if(sz) return a; // Lấy kích cỡ stack int getSize() return sz; ;

Cách thực hiện stack gồm trong C++

Stack được setup ở trên là kha khá ổn. Tuy nhiên, vào C++ sẽ được kiến thiết sẵnstack với tác dụng tốt cho nên việc xây dựng bên trên là không thực sự sự quan trọng trong phần lớn các trường hợp.

Khai báo stack

Thông thường nhằm thêm stackvào chương trình, chúng ta sẽ thêm thư viện như sau:

#include

Tuy nhiên, sinh hoạt trong suốt khoá học tập này mình sẽ thực hiện header sau:

#include

Header này sẽ giúp chúng ta thêm toàn bộ các thư viện về các kết cấu dữ liệu mà họ sẽ học tập trong khóahọc này.

Ta sẽ khai báo stacknhư sau:

stack tênstack;

Ví dụ: stack myStack;

Ngoài ra rất có thể khởi chế tác stackvới mảng giá chỉ trị cho trước. Tuy nhiên mình ít khi chạm chán phải trường hòa hợp này trong thực tế. Các bạn có thể tham khảo thêm về những cách khởi tạostack khác.

Các cách tiến hành trong stack

Các cách thức cơ bản trong stackcủa C++:

push: Thêm thành phần vào cuối stack pop: các loại bỏ phần tử cuối stacktop: Trả về quý hiếm là thành phần cuối trongstack size: Trả về quý giá nguyên là số phần tử đang bao gồm trongstack empty: Trả về một cực hiếm bool, true nếustack rỗng, false nếu như stack ko rỗng

Các cách tiến hành trên sẽ các mất độ phức hợp O(1).

Mình bao gồm một đoạn code demo về những phương thức cơ phiên bản của stack như sau:

#includeusing namespace std; stack st; int main(){ // Thêm các bộ phận vào stack st.push(1); st.push(3); st.push(5); // bây giờ stack là <1, 3, 5> // In ra phần tử cuối thuộc trong stack và kích thước stack cout 0) st.pop(); // bình chọn stack gồm rỗng ko if(st.empty()) cout khi chạy đoạn code bên trên ta thu được công dụng như sau:

*

Lưu ý: các phương thức như pop, đứng đầu nếu được call khi stack rỗng sẽ dẫn đếnRuntime Error. Vì chưng đó, yêu cầu phải đảm bảo an toàn stack không rỗng trước lúc gọi các phương thức này. Để khám nghiệm stack gồm rỗng hay không thì các chúng ta cũng có thể sử dụng phương thứcempty()mà mình đã nêu làm việc 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ề stackthì bài bác toán thuở đầu sẽ được code như sau:

#includeusing namespace std; const int MaxN = 1 + 1e6; int n, a;stack st; int main(){ freopen("CTDL.inp","r",stdin); freopen("CTDL.out","w",stdout); cin >> n; for(int i = 0 ; i > a; for(int i = 0 ; i Hãy chăm chú vào độ phức hợp của thuật toán này: Ta thấy dù là vòng lặpwhile trong tầm lặp for tuy nhiên hai vòng lặp này hoàn toàn không nhờ vào vào nhau (Khác với ở lời giải ban đầu). Các phần tử trong mảng a chỉ ra và vào stack tổng số tối đa là 2 lần đo đó trong toàn bộ chương trình, vòng lặp whilesẽ chỉ tiến hành tối nhiều 2n thao tác làm việc O(1). Cho nên vì vậy thuật toán sẽ sở hữu độ phức tạp O(n). đối với thuật toán ban đầu có độ phức hợp O(n2) thì trên đây là cách tân đáng kể.

Về việc thực hiện stack tất cả sẵn với stack trường đoản cú xây dựng

Như mình có nói, stacktrong C++ sẽ giỏi hơn trong nhiều phần các trường hợp. Vậy có khi nào chúng ta đang cầnstack tự xuất bản không? Câu vấn đáp là vẫn có. Vậy thì đó là khi nào? Các bạn cũng có thể thấy, thực chất củastack từ bỏ xây dựng vẫn luôn là mảng. Bởi đó, ta rất có thể truy cập bỗng dưng vào bất cứ phần tử nào, không giống vớistack trong C++ chỉ rất có thể lấy bộ phận cuối thuộc ra. Bởi vì đó, nếu chúng ta vì lýdo gì đó cần truy vấn nhiều hơn một trong những phần tử ngơi nghỉ cuối thì nên cần dùngstack tự xây dựng.

Ngoài ra, vào C++ bao gồm một kết cấu dữ liệu là vector. Các bạn hoàn toàn hoàn toàn có thể đọc về vector và sử dụng nó nhưstack. Vector sẽ là sự việc dunghòa giỏi các điểm lợi giữa stack tự thi công (truy cập ngẫu nhiên) vàstack bao gồm sẵn (tiện lợi, an toàn).

Kết luận

Qua bài bác này họ đã vậy được định nghĩa stackcũng như là cách thiết lập và vận dụng trong thực tế.

Bài sau chúng ta sẽ ban đầu tìm hiểu về cấu tạo dữ liệuQueue và Deque.

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

Thảo luận

Nếu chúng ta có ngẫu nhiên khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc vào mục HỎI & ĐÁP trên tủ sách exposedjunction.com.com để nhận được sự cung cấp từ cộng đồng.