Mẫu lớp Stack được triển khai trong một tệp *.h riêng biệt, vâng, nó được triển khai, tôi không nhầm. Vấn đề là cả giao diện mẫu lớp và phần triển khai đều phải nằm trong cùng một tệp, nếu không bạn sẽ thấy danh sách các lỗi có nội dung tương tự:

lỗi không xác định tham chiếu đến "phương thức mẫu lớp"

Giao diện mẫu lớp được khai báo từ dòng 9 đến dòng 28. Tất cả các phương thức lớp đều chứa các nhận xét và theo tôi, sẽ không có ý nghĩa gì nếu mô tả công việc của chúng một cách riêng biệt. Xin lưu ý rằng tất cả các phương thức của mẫu lớp Stack đều được khai báo là . Điều này được thực hiện để tăng tốc lớp học. Bởi vì các hàm lớp dựng sẵn hoạt động nhanh hơn các hàm bên ngoài.

Ngay sau giao diện mẫu là phần triển khai các phương thức của lớp Stack, các dòng 32 - 117. Không có gì phức tạp trong việc triển khai các phương thức lớp nếu bạn biết cách ngăn xếp, các mẫu và . Lưu ý rằng có hai hàm tạo trong lớp, hàm đầu tiên được khai báo ở dòng 32-33 là hàm tạo mặc định. Nhưng hàm tạo ở dòng 41-5 là hàm tạo sao chép. Cần phải sao chép đối tượng này sang đối tượng khác. Phương thức Peek, dòng 80 - 88, cung cấp khả năng xem các phần tử của ngăn xếp. Bạn chỉ cần nhập số phần tử, tính từ đầu ngăn xếp. Các hàm còn lại là các hàm dịch vụ, nghĩa là chúng được thiết kế để sử dụng bên trong lớp, tất nhiên, ngoại trừ hàm printStack(), hiển thị các phần tử ngăn xếp trên màn hình.

Bây giờ chúng ta hãy xem trình điều khiển cho ngăn xếp của chúng ta; theo trình điều khiển, ý tôi là chương trình trong đó hoạt động của lớp được kiểm tra. Như thường lệ, đây là chức năng chính, trong đó chúng ta sẽ kiểm tra mẫu lớp Stack của mình. Nhìn vào đoạn mã dưới đây:

#bao gồm sử dụng không gian tên std; #include "stack.h" int main() ( Stack stackSymbol(5); int ct = 0; char ch; trong khi(ct++< 5) { cin >>ch; stackSymbol.push(ch); // đẩy các phần tử vào ngăn xếp ) cout<< endl; stackSymbol.printStack(); // печать стека cout << "\n\nУдалим элемент из стека\n"; stackSymbol.pop(); stackSymbol.printStack(); // печать стека StacknewStack(stackSymbol); cout<< "\n\nСработал конструктор копирования!\n"; newStack.printStack(); cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl; return 0; }

Chúng tôi đã tạo một đối tượng ngăn xếp, dòng 9, kích thước ngăn xếp là 5, nghĩa là ngăn xếp có thể chứa không quá 5 phần tử. Chúng ta điền vào ngăn xếp, các dòng 13 - 17. Ở dòng 21, chúng ta hiển thị ngăn xếp trên màn hình, sau đó chúng ta xóa một phần tử khỏi ngăn xếp, dòng 24 và hiển thị lại nội dung của ngăn xếp, tin tôi đi, nó đã thay đổi chính xác một phần tử. Chúng ta hãy xem kết quả của chương trình:

RẤT NHIỀU! | ! | R | T | Ồ | L Xóa một phần tử khỏi ngăn xếp | R | T | Ồ | L Trình tạo bản sao đã hoạt động! | R | T | Ồ | L Mục thứ hai trong dòng: T

Ở dòng 28, chúng ta đã sử dụng hàm tạo sao chép, giống như hàm tôi đã viết ở trên. Chúng ta đừng quên hàm seek(), hãy xem phần tử thứ hai của ngăn xếp, dòng 33.

Đó là tất cả! Chúng tôi có một ngăn xếp và nó hoạt động bình thường, hãy thử kiểm tra nó, ví dụ: trên kiểu dữ liệu int. Tôi chắc chắn mọi thứ sẽ tiếp tục hoạt động bình thường.

Xếp hàng

Hàng đợi như một cấu trúc dữ liệu có thể hiểu được ngay cả với những người không quen với lập trình. Hàng đợi chứa các phần tử, như thể được xếp nối tiếp nhau thành một chuỗi. Hàng đợi có điểm bắt đầu và điểm kết thúc. Bạn chỉ có thể thêm các phần tử mới vào cuối hàng đợi; bạn chỉ có thể lấy các phần tử từ đầu. Không giống như hàng đợi thông thường, luôn có thể được để lại nếu muốn, các phần tử không thể bị xóa khỏi giữa hàng đợi của lập trình viên.

Hàng đợi có thể được coi như một cái ống. Bạn có thể thêm các quả bóng - các phần tử của hàng đợi - vào một đầu của ống và chúng sẽ bị xóa khỏi đầu kia. Các phần tử ở giữa hàng đợi, tức là các quả bóng bên trong ống không thể tiếp cận được. Phần cuối của ống mà các quả bóng được thêm vào tương ứng với phần cuối của hàng đợi, phần cuối mà chúng được lấy ra tương ứng với phần đầu của hàng đợi. Do đó, các đầu của ống không đối xứng; các quả bóng bên trong ống chỉ chuyển động theo một hướng.

Về nguyên tắc, chúng ta có thể cho phép các phần tử được thêm vào cả hai đầu của hàng đợi và được lấy từ cả hai đầu. Cấu trúc dữ liệu như vậy cũng tồn tại trong lập trình, tên của nó là “dec”, bắt nguồn từ tiếng Anh. Hàng đợi kết thúc đôi, tức là một hàng đợi có hai đầu. Tháng 12 được sử dụng ít thường xuyên hơn hàng đợi.

Việc sử dụng hàng đợi trong lập trình gần như giống với vai trò của nó trong cuộc sống hàng ngày. Hàng đợi hầu như luôn được liên kết với các yêu cầu cung cấp dịch vụ trong trường hợp chúng không thể được hoàn thành ngay lập tức. Hàng đợi cũng duy trì thứ tự các yêu cầu được phục vụ. Ví dụ, hãy xem xét điều gì xảy ra khi một người nhấn một phím trên bàn phím máy tính. Vì vậy, một người yêu cầu máy tính thực hiện một số hành động. Ví dụ: nếu anh ta chỉ đơn giản là gõ văn bản, thì hành động đó sẽ bao gồm việc thêm một ký tự vào văn bản và có thể đi kèm với việc vẽ lại vùng màn hình, cuộn cửa sổ, định dạng lại đoạn văn, v.v.

Bất kỳ hệ điều hành nào, ngay cả đơn giản nhất, luôn đa nhiệm ở mức độ này hay mức độ khác. Điều này có nghĩa là tại thời điểm nhấn phím, hệ điều hành có thể đang bận một số công việc khác. Tuy nhiên, hệ điều hành không có quyền bỏ qua việc nhấn phím trong mọi tình huống. Vì vậy, hoạt động của máy tính bị gián đoạn, nó ghi nhớ trạng thái và chuyển sang xử lý các phím bấm. Quá trình xử lý này phải rất ngắn để không làm gián đoạn các nhiệm vụ khác. Lệnh được đưa ra bằng cách nhấn một phím chỉ được thêm vào cuối hàng yêu cầu đang chờ được thực thi. Sau đó, thời gian gián đoạn kết thúc, máy tính khôi phục trạng thái và tiếp tục công việc bị gián đoạn khi nhấn phím. Một yêu cầu được xếp hàng đợi sẽ không được thực hiện ngay lập tức mà chỉ được thực hiện khi đến lượt nó.

Trong Windows, hoạt động của các ứng dụng cửa sổ dựa trên các thông báo được gửi đến các ứng dụng đó. Ví dụ: có các thông báo về việc nhấn nút chuột, về việc đóng cửa sổ, về nhu cầu vẽ lại vùng cửa sổ, về việc chọn một mục menu, v.v. Mỗi chương trình có hàng đợi yêu cầu. Khi chương trình nhận được lát thời gian thực hiện, nó sẽ chọn yêu cầu tiếp theo từ phía trước hàng đợi và thực hiện yêu cầu đó. Vì vậy, nói một cách đơn giản, công việc của một ứng dụng cửa sổ bao gồm việc thực hiện tuần tự các yêu cầu từ hàng đợi của nó. Hàng đợi được duy trì bởi hệ điều hành.

Một cách tiếp cận lập trình không bao gồm các cuộc gọi trực tiếp đến các thủ tục mà gửi các thông điệp được đặt trong hàng đợi yêu cầu, có nhiều ưu điểm và là một trong những đặc điểm của lập trình hướng đối tượng. Vì vậy, ví dụ, nếu một chương trình windows cần tắt vì lý do nào đó, tốt hơn hết bạn không nên gọi ngay lệnh tắt máy, điều này rất nguy hiểm vì nó phá vỡ tính logic của công việc và có thể dẫn đến mất dữ liệu. Thay vào đó, chương trình sẽ tự gửi thông báo tắt, thông báo này sẽ được gửi đến hàng đợi yêu cầu và thực hiện sau khi nhận được yêu cầu trước đó.

Triển khai hàng đợi dựa trên mảng

Như đã nói, người lập trình được cung cấp một mảng từ phía trên; tất cả các cấu trúc dữ liệu khác cần được triển khai trên cơ sở của nó. Tất nhiên, việc triển khai như vậy có thể gồm nhiều giai đoạn và mảng không phải lúc nào cũng đóng vai trò là cơ sở triển khai ngay lập tức. Trong trường hợp hàng đợi, hai cách triển khai phổ biến nhất là dựa trên mảng liên tục, còn được gọi là triển khai dựa trên bộ đệm vòng và Thực hiện tham khảo hoặc triển khai dựa trên danh sách. Triển khai tham khảo sẽ được thảo luận dưới đây.

Khi triển khai hàng đợi liên tục, cơ sở là một mảng có độ dài N cố định nên hàng đợi bị giới hạn và không thể chứa nhiều hơn N phần tử. Các chỉ số phần tử mảng nằm trong khoảng từ 0 đến N - 1 . Ngoài mảng, việc triển khai hàng đợi còn lưu trữ ba biến đơn giản: chỉ mục ở đầu hàng đợi, chỉ mục ở cuối hàng đợi và số phần tử của hàng đợi. Các phần tử của hàng đợi được chứa trong phân đoạn mảng từ chỉ mục đầu đến chỉ mục cuối.

Khi thêm một phần tử mới vào cuối hàng đợi, chỉ số cuối trước tiên sẽ tăng thêm một, sau đó phần tử mới được ghi vào ô mảng có chỉ mục này. Tương tự, khi truy xuất một phần tử từ phần đầu của hàng đợi, nội dung của ô mảng có chỉ mục phần đầu của hàng đợi được lưu trữ dưới dạng kết quả của thao tác, khi đó chỉ số phần đầu của hàng đợi sẽ tăng lên một. Cả chỉ số bắt đầu và kết thúc của hàng đợi đều di chuyển từ trái sang phải trong quá trình hoạt động. Điều gì xảy ra khi chỉ mục cuối hàng đợi đến cuối mảng, tức là N-1?

Ý tưởng chính của việc triển khai hàng đợi là mảng được lặp thành một vòng. Phần tử cuối cùng của mảng được coi là được theo sau bởi phần tử đầu tiên của nó (hãy nhớ rằng phần tử cuối cùng có chỉ số N - 1 và phần tử đầu tiên có chỉ mục 0). Khi dịch chỉ mục cuối hàng sang phải, trường hợp nó trỏ đến phần tử cuối cùng của mảng thì nó sẽ di chuyển đến phần tử đầu tiên. Do đó, một đoạn liên tục của mảng bị chiếm giữ bởi các phần tử của hàng đợi có thể đi từ cuối mảng đến đầu mảng.

Cây rơm

Ngăn xếp là cấu trúc dữ liệu phổ biến nhất và có lẽ là quan trọng nhất trong lập trình. Ngăn xếp là một thiết bị lưu trữ trong đó các phần tử được loại bỏ theo thứ tự ngược lại khi thêm vào. Nó giống như một hàng đợi không đều đặn, trong đó người được phục vụ đầu tiên là người vào cuối cùng. Trong tài liệu lập trình, các chữ viết tắt thường được chấp nhận để biểu thị nguyên tắc của hàng đợi và ngăn xếp. Kỷ luật xếp hàng được chỉ định là FIFO, có nghĩa là Vào trước ra trước. Kỷ luật ngăn xếp được chỉ định là LIFO, nhập sau ra trước (Last In First Out).

Có thể coi ngăn xếp như một ống có đáy chịu lực bằng lò xo, nằm thẳng đứng. Đầu trên của ống mở, các phần tử có thể được thêm vào hoặc, như người ta nói, được đẩy vào đó. Các thuật ngữ tiếng Anh phổ biến về vấn đề này rất nhiều màu sắc; hoạt động thêm một phần tử vào ngăn xếp được biểu thị là đẩy, được dịch là “đẩy, xô”. Một phần tử mới được thêm vào sẽ đẩy các phần tử được đặt trước đó trên ngăn xếp xuống một vị trí. Khi các phần tử được lấy ra khỏi ngăn xếp, chúng sẽ được đẩy lên, bằng tiếng Anh pop (“bắn”).

Một ví dụ về một chồng có thể là một đống cỏ khô, một chồng giấy tờ trên bàn, một chồng đĩa, v.v. Đây là nguồn gốc của tên ngăn xếp, có nghĩa là ngăn xếp trong tiếng Anh. Các tấm được lấy ra khỏi ngăn xếp theo thứ tự ngược lại với việc bổ sung chúng. Chỉ có tấm trên cùng mới có thể truy cập được, tức là. đĩa trên đỉnh ngăn xếp. Một ví dụ điển hình là một ngõ cụt đường sắt nơi ô tô có thể xếp chồng lên nhau.

Sử dụng ngăn xếp trong lập trình

Ngăn xếp được sử dụng khá thường xuyên và trong nhiều tình huống khác nhau. Chúng thống nhất với nhau vì mục tiêu sau: bạn cần lưu một số công việc chưa hoàn thành nếu bạn cần chuyển sang nhiệm vụ khác. Ngăn xếp được sử dụng để lưu trữ tạm thời trạng thái của một tác vụ chưa hoàn thành. Sau khi lưu trạng thái, máy tính chuyển sang tác vụ khác. Sau khi hoàn thành việc thực thi, trạng thái của tác vụ bị trì hoãn sẽ được khôi phục từ ngăn xếp và máy tính tiếp tục hoạt động bị gián đoạn.

Tại sao ngăn xếp được sử dụng để lưu trạng thái công việc bị gián đoạn? Giả sử máy tính đang thực hiện nhiệm vụ A. Trong quá trình thực hiện, cần phải hoàn thành nhiệm vụ B. Trạng thái của tác vụ A được ghi nhớ và máy tính chuyển sang thực thi tác vụ B. Nhưng ngay cả khi thực hiện tác vụ B, máy tính vẫn có thể chuyển sang tác vụ C khác và nó sẽ cần lưu trạng thái của tác vụ B trước khi chuyển sang tác vụ C. Sau đó, khi hoàn thành nhiệm vụ C, trạng thái của nhiệm vụ B sẽ được khôi phục trước tiên, sau đó, khi hoàn thành nhiệm vụ B, trạng thái của nhiệm vụ A sẽ được khôi phục. Do đó, quá trình khôi phục xảy ra theo thứ tự ngược lại với quá trình lưu, tương ứng với quy tắc của ngăn xếp.

Ngăn xếp cho phép bạn tổ chức đệ quy, tức là. một chương trình con gọi chính nó, trực tiếp hoặc thông qua một chuỗi các lệnh gọi khác. Ví dụ: để thường trình A thực thi một thuật toán phụ thuộc vào tham số đầu vào X và có thể phụ thuộc vào trạng thái của dữ liệu toàn cục. Đối với các giá trị đơn giản nhất của X, thuật toán được thực hiện trực tiếp. Đối với các giá trị X phức tạp hơn, thuật toán được triển khai dưới dạng rút gọn việc áp dụng thuật toán tương tự cho các giá trị X đơn giản hơn. Trong trường hợp này, chương trình con A tham chiếu đến chính nó, truyền một giá trị X đơn giản hơn làm tham số. Với quyền truy cập này, giá trị trước đó của tham số X, cũng như tất cả các biến cục bộ của chương trình con A, được lưu trữ trên ngăn xếp. Tiếp theo, một tập hợp các biến cục bộ mới và một biến chứa giá trị mới (đơn giản hơn) của tham số X được tạo. Chương trình con A được gọi hoạt động trên một tập biến mới mà không hủy tập hợp trước đó. Khi kết thúc cuộc gọi, tập hợp các biến cục bộ cũ và trạng thái cũ của tham số đầu vào X được khôi phục từ ngăn xếp và quy trình sẽ tiếp tục từ nơi nó dừng lại.

Trên thực tế, bạn thậm chí không cần phải lưu các giá trị của các biến cục bộ của chương trình con vào ngăn xếp theo một cách đặc biệt. Thực tế là các biến cục bộ của một chương trình con (tức là các biến nội bộ, biến điều hành, được tạo khi bắt đầu thực thi và bị hủy khi kết thúc) được đặt trên một ngăn xếp, được triển khai trong phần cứng dựa trên RAM thông thường. Khi bắt đầu công việc, chương trình con lấy không gian trên ngăn xếp cho các biến cục bộ của nó; vùng bộ nhớ này trong ngăn xếp phần cứng thường được gọi là khối biến cục bộ hoặc bằng tiếng Anh khung("khung"). Tại thời điểm hoàn thành công việc, chương trình con sẽ giải phóng bộ nhớ bằng cách loại bỏ khối biến cục bộ của nó khỏi ngăn xếp.

Ngoài các biến cục bộ, địa chỉ trả về cho các cuộc gọi chương trình con được lưu trữ trên ngăn xếp phần cứng. Cho một chương trình con được gọi tại một thời điểm nào đó trong chương trình A B. Trước khi chương trình con B được gọi, địa chỉ của lệnh theo sau lệnh gọi B được lưu trong ngăn xếp. Đây là cái gọi là địa chỉ trả lại tới chương trình A. Khi chạy xong, chương trình con B lấy địa chỉ trả về của chương trình A từ ngăn xếp và trả quyền điều khiển về địa chỉ đó. Do đó, máy tính tiếp tục thực hiện chương trình A, bắt đầu bằng lệnh sau lệnh gọi. Hầu hết các bộ xử lý đều có các hướng dẫn đặc biệt hỗ trợ gọi chương trình con bằng cách trước tiên đẩy địa chỉ trả về vào ngăn xếp và quay lại từ chương trình con tại địa chỉ được lấy ra từ ngăn xếp. Thông thường lệnh gọi gọi là call, lệnh return gọi là return.

Các tham số của chương trình con hoặc hàm cũng được đẩy vào ngăn xếp trước khi nó được gọi. Thứ tự chúng được đặt trên ngăn xếp phụ thuộc vào quy ước của các ngôn ngữ cấp cao. Vì vậy, trong ngôn ngữ C hoặc C++, đối số hàm đầu tiên nằm ở trên cùng của ngăn xếp, đối số thứ hai ở dưới nó, v.v. Trong Pascal thì ngược lại: đối số cuối cùng của hàm nằm ở đầu ngăn xếp. (Nhân tiện, đây là lý do tại sao các hàm có số lượng đối số thay đổi, chẳng hạn như printf, có thể có trong C, nhưng không có trong Pascal.)

Trong Fortran-4, một trong những ngôn ngữ lập trình lâu đời nhất và thành công nhất, các đối số được truyền qua một vùng bộ nhớ đặc biệt, có thể không nằm trên ngăn xếp, vì cho đến cuối những năm 70 của thế kỷ 20 vẫn còn những máy tính như Máy tính IBM 360 hoặc ES không có ngăn triển khai phần cứng. Địa chỉ trả về cũng không được lưu trữ trên ngăn xếp mà trong các ô bộ nhớ được cố định cho mỗi chương trình con. Các lập trình viên gọi bộ nhớ đó là tĩnh theo nghĩa là các biến tĩnh luôn chiếm cùng một vị trí trong bộ nhớ bất kỳ lúc nào trong quá trình thực hiện chương trình. Khi chỉ sử dụng bộ nhớ tĩnh, việc đệ quy là không thể vì các giá trị trước đó của biến cục bộ sẽ bị hủy khi thực hiện lệnh gọi mới. Tham chiếu Fortran 4 chỉ sử dụng các biến tĩnh và đệ quy bị cấm. Cho đến nay, ngôn ngữ Fortran được sử dụng rộng rãi trong tính toán khoa học và kỹ thuật, tuy nhiên, tiêu chuẩn Fortran-90 hiện đại đã đưa vào bộ nhớ ngăn xếp, loại bỏ những thiếu sót của các phiên bản ngôn ngữ trước đó.

Triển khai ngăn xếp dựa trên mảng

Việc triển khai ngăn xếp dựa trên mảng là một phương pháp lập trình cổ điển. Đôi khi, ngay cả khái niệm về ngăn xếp cũng không được xác định hoàn toàn chính xác với cách triển khai này.

Cơ sở triển khai là một mảng có kích thước N, do đó triển khai một ngăn xếp có kích thước giới hạn, độ sâu tối đa của nó không thể vượt quá N. Các chỉ số ô mảng nằm trong khoảng từ 0 đến N - 1 . Các phần tử ngăn xếp được lưu trữ trong một mảng như sau: phần tử ở cuối ngăn xếp nằm ở đầu mảng, tức là. trong chỉ mục ô 0. Phần tử phía trên phần tử dưới cùng của ngăn xếp được lưu trữ trong chỉ mục ô 1, v.v. Đỉnh của ngăn xếp được lưu trữ ở đâu đó ở giữa mảng. Chỉ mục của phần tử ở đầu ngăn xếp được lưu trữ trong một biến đặc biệt thường được gọi là con trỏ N-1 . Các phần tử ngăn xếp chiếm một phần liền kề của mảng, bắt đầu từ ô có chỉ mục được lưu trong con trỏ ngăn xếp và kết thúc bằng ô cuối cùng của mảng. Trong tùy chọn này, ngăn xếp phát triển theo hướng giảm chỉ mục. Nếu ngăn xếp trống thì con trỏ ngăn xếp chứa giá trị N (lớn hơn chỉ số của ô cuối cùng trong mảng một đơn vị).

Xin chào, tôi là sinh viên năm thứ hai của một trường đại học kỹ thuật. Sau khi nghỉ học một vài lớp lập trình vì lý do sức khỏe, tôi phải đối mặt với tình trạng thiếu hiểu biết về các chủ đề như Stack và Queue. Qua thử và sai, sau vài ngày, cuối cùng tôi cũng hiểu ra nó là gì và nó được ăn với cái gì. Để sự hiểu biết của bạn không mất quá nhiều thời gian, trong bài viết này tôi sẽ nói về “Stack” là gì, làm thế nào và với những ví dụ nào tôi hiểu nó là gì. Nếu bạn thích, tôi sẽ viết phần thứ hai, sẽ đề cập đến một khái niệm như “Hàng đợi”

Lý thuyết

Trên Wikipedia định nghĩa của ngăn xếp là:

Stack (tiếng Anh stack - stack; read stack) là kiểu dữ liệu trừu tượng, là danh sách các phần tử được sắp xếp theo nguyên tắc LIFO (tiếng Anh Last in - First out, “last in - first out”).

Vì vậy, điều đầu tiên tôi muốn tập trung vào là việc thể hiện ngăn xếp dưới dạng những đồ vật trong cuộc sống. Cách giải thích đầu tiên xuất hiện trong đầu tôi là dưới dạng một chồng sách, trong đó cuốn sách trên cùng là trên cùng.

Vì vậy, một ngăn xếp bao gồm những gì?

Ngăn xếp bao gồm các ô (trong ví dụ, đây là những cuốn sách), được biểu diễn dưới dạng cấu trúc chứa một số dữ liệu và một con trỏ tới loại cấu trúc này tới phần tử tiếp theo.
Khó? Không vấn đề gì, hãy cùng tìm hiểu nhé.

Hình ảnh này thể hiện sơ đồ ngăn xếp. Khối có dạng “Data/*next” là ô của chúng ta. *next, như chúng ta thấy, trỏ đến phần tử tiếp theo, nói cách khác, con trỏ *next lưu trữ địa chỉ của ô tiếp theo. Con trỏ *TOP trỏ đến đỉnh ngăn xếp, nghĩa là nó lưu trữ địa chỉ của nó.

Chúng ta đã học xong lý thuyết, hãy chuyển sang thực hành.

Luyện tập

Đầu tiên chúng ta cần tạo một cấu trúc sẽ là “ô” của chúng ta

Mã C++

struct comp ( //Cấu trúc được gọi là comp (từ thành phần word) int Data; //Một số dữ liệu (có thể là bất kỳ, ví dụ bạn có thể viết int key; char Data; bạn cũng có thể thêm một số dữ liệu khác) comp *next;/ / Con trỏ kiểu Comp tới phần tử tiếp theo);

Người mới bắt đầu có thể không hiểu tại sao con trỏ của chúng ta lại thuộc loại comp, hay chính xác hơn là con trỏ thuộc loại cấu trúc comp. Hãy để tôi giải thích, để con trỏ *next lưu trữ cấu trúc comp, nó cần chỉ ra loại cấu trúc này. Nói cách khác, chỉ ra những gì con trỏ sẽ lưu trữ.

Sau khi chúng ta đã thiết lập xong “Ô”, hãy chuyển sang tạo các hàm.

Chức năng

Chức năng tạo “Stack”/thêm phần tử vào “Stack”

Khi thêm một phần tử, chúng ta sẽ có hai tình huống:

• Ngăn xếp trống và cần được tạo
• Ngăn xếp đã tồn tại và bạn chỉ cần thêm phần tử mới vào đó

Mã C++

void s_push(comp **top, int D) ( //hàm kiểu void (không trả về bất cứ thứ gì) lấy một con trỏ lên đầu ngăn xếp và một biến sẽ được ghi vào ô comp *q; //Tạo một con trỏ mới q của kiểu cấu trúc comp. Về bản chất, đây là phần tử mới của chúng ta q = new comp(); // cấp phát bộ nhớ cho phần tử mới q->Data = D // Ghi số được yêu cầu vào Dữ liệu; phần tử if (top == NULL) ( //Nếu không có đỉnh, nghĩa là ngăn xếp trống *top = q; //đỉnh của ngăn xếp sẽ là phần tử mới) else //nếu ngăn xếp không trống ( q->next = *top; //Chúng ta vẽ một kết nối từ phần tử mới lên trên cùng. Tức là chúng ta đặt cuốn sách lên trên cùng của ngăn xếp . *top = q; //Biểu thị rằng đỉnh là bây giờ là một yếu tố mới) )

Chúng ta hãy xem xét nó chi tiết hơn một chút.
Đầu tiên, tại sao hàm chấp nhận **top, tức là một con trỏ tới một con trỏ, để các bạn hiểu rõ hơn, tôi sẽ để lại vấn đề này sau. Thứ hai, hãy nói chi tiết hơn về q->tiếp theo = *trên cùng và về ý nghĩa của nó -> .

-> có nghĩa là, nói một cách đại khái, chúng ta đi vào cấu trúc của mình và lấy ra một phần tử của cấu trúc này từ đó. Trong dòng q->tiếp theo = *trên cùng Chúng ta lấy một con trỏ tới phần tử tiếp theo *next từ ô của chúng ta và thay thế nó bằng một con trỏ trỏ đến đỉnh của ngăn xếp *top. Nói cách khác, chúng ta tạo kết nối từ phần tử mới đến đỉnh ngăn xếp. Không có gì phức tạp ở đây, mọi thứ đều giống như sách. Chúng ta đặt cuốn sách mới chính xác lên trên cùng của chồng sách, tức là chúng ta vẽ một kết nối từ cuốn sách mới đến đầu chồng sách. Sau đó, cuốn sách mới tự động trở thành trên cùng, vì ngăn xếp không phải là chồng sách, chúng ta cần chỉ ra rằng phần tử mới là trên cùng, vì điều này chúng ta viết: *trên cùng = q;.

Chức năng xóa một phần tử khỏi “Stack” dựa trên dữ liệu

Hàm này sẽ loại bỏ một phần tử khỏi ngăn xếp nếu số Dữ liệu của ô (q->Dữ liệu) bằng số mà chính chúng ta sẽ chỉ định.

Có thể có các tùy chọn sau:

• Ô chúng ta cần loại bỏ là ô trên cùng của ngăn xếp
• Ô chúng ta cần xóa nằm ở cuối hoặc giữa 2 ô

Mã C++

void s_delete_key(comp **top, int N) (//một hàm lấy đỉnh trên cùng và số cần xóa comp *q = *top; //tạo một con trỏ kiểu comp và đặt (đặt) nó ngang hàng với đỉnh của ngăn xếp comp *prev = NULL;//chúng ta tạo một con trỏ tới phần tử trước đó, ngay từ đầu nó sẽ trống while (q != NULL) (//trong khi con trỏ q không trống, chúng ta sẽ thực thi đoạn mã trong một vòng lặp, nếu vẫn là vòng lặp trống thì vòng lặp sẽ kết thúc if (q-> Data == N) (//nếu Data của phần tử bằng số mà chúng ta cần loại bỏ if (q == *top) ( //nếu con trỏ như vậy bằng top, thì có một phần tử mà chúng ta cần loại bỏ - top *top = q- >next;//di chuyển đỉnh sang phần tử tiếp theo free(q);//clear ô q->Data = NULL; //Tiếp theo, để tránh lỗi, chúng ta đặt lại các biến trong ô từ xa, vì trong một số trình biên dịch, ô từ xa có các giá trị biến không phải NULL, nhưng theo nghĩa đen là "Không thể đọc bộ nhớ" hoặc các số “-2738568384” hoặc các phần tử khác, tùy thuộc vào trình biên dịch q->next = NULL ) else//nếu phần tử là phần tử cuối cùng hoặc nằm giữa hai phần tử khác ( prev->next = q ->next;//Vẽ kết nối từ phần tử trước tới phần tử free(q);//xóa ô q->Data = NULL;//không có biến q->next = NULL; ) ) // nếu Data của phần tử KHÔNG bằng số ta cần loại bỏ prev = q; //ghi nhớ ô hiện tại là ô trước q = q->next;//di chuyển con trỏ q tới phần tử tiếp theo ) )

Con trỏ q trong trường hợp này đóng vai trò giống như con trỏ trong notepad; nó chạy xuyên suốt toàn bộ ngăn xếp cho đến khi bằng NULL( while(q != NULL)), nói cách khác là cho đến khi hết ngăn xếp.

Để hiểu rõ hơn về việc loại bỏ một phần tử, hãy vẽ một phép tương tự với chồng sách vốn đã quen thuộc. Nếu chúng tôi cần xóa một cuốn sách ở trên, chúng tôi sẽ xóa cuốn sách đó và cuốn sách bên dưới sẽ trở thành cuốn sách trên cùng. Ở đây cũng vậy, chỉ là lúc đầu chúng ta phải xác định phần tử tiếp theo sẽ trở thành phần tử hàng đầu *top = q->next; và chỉ sau đó xóa phần tử miễn phí(q);

Nếu cuốn sách cần bỏ nằm giữa hai cuốn sách hoặc giữa một cuốn sách và một cái bàn thì cuốn sách trước đó sẽ nằm trên cuốn sách tiếp theo hoặc trên bàn. Như chúng ta đã hiểu, cuốn sách của chúng ta là một ô và bảng hóa ra là NULL, nghĩa là không có phần tử tiếp theo. Hóa ra cũng giống như với sách, chúng ta chỉ định rằng ô trước đó sẽ được kết nối với ô tiếp theo trước->tiếp theo = q->tiếp theo;, điều đáng chú ý là trước-> tiếp theo có thể bằng một ô hoặc bằng 0, nếu q->tiếp theo = NULL, tức là không có ô (cuốn sách sẽ nằm trên bàn), sau đó chúng ta xóa ô miễn phí(q).

Cũng cần lưu ý rằng nếu kết nối này không được thực hiện, phần ô nằm sau ô đã xóa sẽ không thể truy cập được, vì chính kết nối kết nối ô này với ô khác sẽ bị mất và phần này sẽ bị mất trong bộ nhớ.

Chức năng hiển thị ngăn xếp

Chức năng đơn giản nhất:

Mã C++

void s_print(comp *top) ( //chấp nhận một con trỏ ở đầu ngăn xếp comp *q = top; //đặt q lên đầu while (q) ( // miễn là q không trống (while(q ) tương đương với while(q != NULL )) printf_s("%i", q->Data);//hiển thị dữ liệu của ô ngăn xếp q = q->next;//sau khi hiển thị xong, di chuyển q đến phần tử tiếp theo (ô) ) )

Ở đây tôi nghĩ mọi thứ đều rõ ràng, tôi chỉ muốn nói rằng q nên được coi như một thanh trượt, nó chạy trên tất cả các ô từ trên cùng nơi chúng ta đặt nó ở đầu: *q = trên cùng;, đến phần tử cuối cùng.

Chức năng chính

Được rồi, chúng ta đã viết ra các hàm chính để làm việc với ngăn xếp và gọi chúng.
Hãy nhìn vào mã:

Mã C++

void main() ( comp *top = NULL; // đầu chương trình không có hàng đợi nên không có đỉnh, ta gán giá trị NULL //Tiếp theo chúng ta bắt đầu cộng các số từ 1 đến 5 đến ngăn xếp của chúng tôi s_push(&top, 1); s_push (&top, 2); s_push(&top, 4); s_push(&top, 5); // sau khi thực hiện các hàm trên ngăn xếp, chúng ta sẽ có 54321 s_print(top);// print s_delete_key(&top, 4); //Sau đó chúng ta xóa 4, ngăn xếp nhận được 5321 printf_s("\n");//dịch sang dòng mới s_print(top);//print system("pause");/ /tạm ngừng)

Hãy quay lại lý do tại sao chúng ta truyền một con trỏ tới con trỏ đỉnh của hàm. Thực tế là nếu chúng ta chỉ đưa một con trỏ tới đỉnh vào hàm, thì “Ngăn xếp” sẽ chỉ được tạo và thay đổi bên trong hàm; trong hàm chính, đỉnh sẽ là NULL. Bằng cách chuyển một con trỏ tới một con trỏ, chúng ta thay đổi đỉnh *top trong hàm main. Hóa ra là nếu một hàm thay đổi ngăn xếp, bạn cần chuyển một đỉnh tới nó bằng một con trỏ tới một con trỏ, như chúng ta đã làm trong hàm s_push, s_delete_key. Trong hàm s_print, “Stack” không được thay đổi, vì vậy chúng ta chỉ cần chuyển một con trỏ lên trên cùng.
Thay vì các số 1,2,3,4,5, bạn cũng có thể sử dụng các biến kiểu int.

Phần kết luận

Mã chương trình đầy đủ:

Mã C++

#bao gồm ; #bao gồm ; struct comp ( //Cấu trúc có tên comp int Data; //Một số dữ liệu (có thể là sở thích của bạn, ví dụ bạn có thể viết int key; char Data; hoặc thêm một số dữ liệu khác) comp *next; // Con trỏ kiểu comp tới phần tử tiếp theo); void s_push(comp **top, int D) ( //hàm kiểu void (không trả về gì) lấy một con trỏ lên đỉnh ngăn xếp và một biến sẽ được ghi vào ô comp *q; //Tạo một con trỏ mới q, mà chúng ta đánh đồng với ngăn xếp trên cùng. Trên thực tế, đây là phần tử mới của chúng ta q = new comp(); // cấp phát bộ nhớ cho phần tử mới q->Data = D; // Ghi D vào phần tử Dữ liệu. if (top == NULL) ( //Nếu không có đỉnh nào, nghĩa là ngăn xếp trống *top = q; //đỉnh của ngăn xếp sẽ là phần tử mới) else //nếu ngăn xếp không trống ( q->next = *top; //Chúng ta vẽ một kết nối từ phần tử mới lên trên cùng. Nghĩa là, chúng ta đặt cuốn sách lên các ngăn xếp trên cùng *top = q //Chúng ta viết rằng phần trên cùng là một phần tử mới. element) ) void s_delete_key(comp **top, int N) (//một hàm lấy phần trên cùng và số cần xóa comp *q = *top; //tạo một con trỏ kiểu comp và đánh đồng (đặt) nó lên đầu ngăn xếp comp *prev = NULL;//tạo một con trỏ tới phần tử trước đó, ngay từ đầu nó sẽ trống while (q != NULL) (//cho đến khi con trỏ q trống, chúng ta sẽ kiểm tra nó nếu nó vẫn để vòng lặp kết thúc if (q->Data == N) (//nếu Dữ liệu của phần tử bằng số mà chúng ta cần xóa if (q == *top) (//nếu như vậy con trỏ bằng top, nghĩa là phần tử chúng ta cần xóa - top *top = q->next;//di chuyển phần trên cùng sang phần tử tiếp theo free(q);//xóa ô q->Data = NULL; //Tiếp theo, để tránh lỗi, chúng tôi đặt lại các biến trong ô từ xa về 0, vì trong một số trình biên dịch, ô từ xa có các biến không phải giá trị NULL, mà theo nghĩa đen là “Không thể đọc bộ nhớ” hoặc các số “-2738568384” hoặc các biến khác, tùy thuộc vào trên trình biên dịch. q->tiếp theo = NULL; ) else//nếu phần tử là phần tử cuối cùng hoặc nằm giữa hai phần tử khác ( prev->next = q->next;//Chúng ta tạo một kết nối từ phần tử trước đó đến phần tử tiếp theo free(q);//xóa ô q->Data = NULL;/ /reset biến q->next = NULL; ) )// nếu Data của phần tử KHÔNG bằng số ta cần xóa prev = q; // nhớ ô hiện tại như ô trước đó q = q->next; // di chuyển con trỏ q tới phần tử tiếp theo ) ) void s_print(comp *top) ( //chấp nhận một con trỏ lên đầu ngăn xếp comp * q = top; //đặt q thành đỉnh while (q) ( //while q không trống (while(q) tương đương với while(q ! = NULL)) printf_s("%i", q->Data);//hiển thị dữ liệu của ô ngăn xếp q = q->next;//sau khi hiển thị, di chuyển q sang phần tử tiếp theo (ô) ) ) void main () ( comp *top = NULL; // khi bắt đầu chương trình chúng ta không có hàng đợi nên không có đỉnh, chúng ta gán cho nó giá trị NULL //Tiếp theo chúng ta bắt đầu thêm các số từ 1 đến 5 vào ngăn xếp s_push(&top, 1); s_push(&top , 2); //Sau đó chúng ta xóa 4, ngăn xếp nhận được 5321 printf_s("\n");//dịch sang dòng mới s_print(top);//print hệ thống("tạm dừng");//tạm dừng)

Kết quả thực hiện

Vì các phần tử liên tục được thêm vào đầu ngăn xếp nên các phần tử sẽ được hiển thị theo thứ tự ngược lại.

Cuối cùng, tôi muốn cảm ơn bạn đã dành thời gian cho bài viết của tôi, tôi thực sự hy vọng rằng tài liệu này đã giúp một số lập trình viên mới làm quen hiểu “Stack” là gì, cách sử dụng nó và trong tương lai họ sẽ không còn nữa các vấn đề. Viết ý kiến ​​​​của bạn trong phần bình luận, cũng như cách tôi có thể cải thiện bài viết của mình trong tương lai. Cám ơn vì sự quan tâm của bạn.

Cây rơm

Ngăn xếp là cấu trúc dữ liệu phổ biến nhất và có lẽ là quan trọng nhất trong lập trình. Ngăn xếp là một thiết bị lưu trữ trong đó các phần tử được loại bỏ theo thứ tự ngược lại khi thêm vào. Nó giống như một hàng đợi không đều đặn, trong đó người được phục vụ đầu tiên là người vào cuối cùng. Trong tài liệu lập trình, các chữ viết tắt thường được chấp nhận để biểu thị nguyên tắc của hàng đợi và ngăn xếp. Kỷ luật xếp hàng được chỉ định là FIFO, có nghĩa là Vào trước ra trước. Kỷ luật ngăn xếp được chỉ định là LIFO, nhập sau ra trước (Last In First Out).

Có thể coi ngăn xếp như một ống có đáy chịu lực bằng lò xo, nằm thẳng đứng. Đầu trên của ống mở, các phần tử có thể được thêm vào hoặc, như người ta nói, được đẩy vào đó. Các thuật ngữ tiếng Anh phổ biến về vấn đề này rất nhiều màu sắc; hoạt động thêm một phần tử vào ngăn xếp được biểu thị là đẩy, được dịch là “đẩy, xô”. Một phần tử mới được thêm vào sẽ đẩy các phần tử được đặt trước đó trên ngăn xếp xuống một vị trí. Khi các phần tử được lấy ra khỏi ngăn xếp, chúng sẽ được đẩy lên, bằng tiếng Anh pop (“bắn”).

Một ví dụ về một chồng có thể là một đống cỏ khô, một chồng giấy tờ trên bàn, một chồng đĩa, v.v. Đây là nguồn gốc của tên ngăn xếp, có nghĩa là ngăn xếp trong tiếng Anh. Các tấm được lấy ra khỏi ngăn xếp theo thứ tự ngược lại với việc bổ sung chúng. Chỉ có tấm trên cùng mới có thể truy cập được, tức là. đĩa trên đỉnh ngăn xếp. Một ví dụ điển hình là một ngõ cụt đường sắt nơi ô tô có thể xếp chồng lên nhau.

Ngăn xếp được sử dụng khá thường xuyên và trong nhiều tình huống khác nhau. Chúng thống nhất với nhau vì mục tiêu sau: bạn cần lưu một số công việc chưa hoàn thành nếu bạn cần chuyển sang nhiệm vụ khác. Ngăn xếp được sử dụng để lưu trữ tạm thời trạng thái của một tác vụ chưa hoàn thành. Sau khi lưu trạng thái, máy tính chuyển sang tác vụ khác. Sau khi hoàn thành việc thực thi, trạng thái của tác vụ bị trì hoãn sẽ được khôi phục từ ngăn xếp và máy tính tiếp tục hoạt động bị gián đoạn.

Tại sao ngăn xếp được sử dụng để lưu trạng thái công việc bị gián đoạn? Giả sử rằng máy tính đang thực hiện nhiệm vụ A. Trong quá trình thực thi, nhu cầu thực hiện nhiệm vụ B. Trạng thái của nhiệm vụ A được ghi nhớ và máy tính tiếp tục thực hiện nhiệm vụ B. Nhưng ngay cả khi thực hiện nhiệm vụ B, máy tính vẫn có thể chuyển đổi sang nhiệm vụ C khác và nó sẽ cần được lưu trạng thái của nhiệm vụ B trước khi chuyển sang nhiệm vụ C. Sau đó, khi hoàn thành nhiệm vụ C, trạng thái của nhiệm vụ B sẽ được khôi phục trước, sau đó, khi hoàn thành nhiệm vụ B, trạng thái của nhiệm vụ A. Do đó, quá trình khôi phục diễn ra theo thứ tự ngược lại với quá trình lưu, tương ứng với kỷ luật ngăn xếp.

Ngăn xếp cho phép bạn tổ chức đệ quy, tức là. một chương trình con gọi chính nó, trực tiếp hoặc thông qua một chuỗi các lệnh gọi khác. Ví dụ: để thường trình A thực thi một thuật toán phụ thuộc vào tham số đầu vào X và có thể phụ thuộc vào trạng thái của dữ liệu toàn cục. Đối với các giá trị đơn giản nhất của X, thuật toán được thực hiện trực tiếp. Trong trường hợp các giá trị X phức tạp hơn, thuật toán được triển khai dưới dạng rút gọn việc áp dụng thuật toán tương tự cho các giá trị X đơn giản hơn. Trong trường hợp này, chương trình con A tự truy cập, truyền giá trị đơn giản hơn của X dưới dạng một tham số. Với quyền truy cập này, giá trị trước đó của tham số X, cũng như tất cả các biến cục bộ của thường trình A sẽ được lưu trữ trên ngăn xếp. Tiếp theo, một tập hợp các biến cục bộ mới và một biến chứa giá trị mới (đơn giản hơn) của tham số X được tạo. Chương trình con A được gọi hoạt động trên tập hợp biến mới mà không hủy tập hợp trước đó. Khi kết thúc cuộc gọi, tập hợp các biến cục bộ cũ và trạng thái cũ của tham số đầu vào X được khôi phục từ ngăn xếp và quy trình sẽ tiếp tục từ nơi nó dừng lại.

Trên thực tế, bạn thậm chí không cần phải lưu các giá trị của các biến cục bộ của chương trình con vào ngăn xếp theo một cách đặc biệt. Thực tế là các biến cục bộ của chương trình con (tức là các biến hoạt động, bên trong của nó, được tạo khi bắt đầu thực thi và bị hủy khi kết thúc) được đặt trên một ngăn xếp được triển khai trong phần cứng dựa trên RAM thông thường. Khi bắt đầu công việc, chương trình con lấy không gian trên ngăn xếp cho các biến cục bộ của nó; vùng bộ nhớ này trong ngăn xếp phần cứng thường được gọi là khối biến cục bộ hoặc bằng tiếng Anh khung("khung"). Tại thời điểm hoàn thành công việc, chương trình con sẽ giải phóng bộ nhớ bằng cách loại bỏ khối biến cục bộ của nó khỏi ngăn xếp.

Ngoài các biến cục bộ, địa chỉ trả về cho các cuộc gọi chương trình con được lưu trữ trên ngăn xếp phần cứng. Cho một chương trình con được gọi tại một thời điểm nào đó trong chương trình A B. Trước khi chương trình con B được gọi, địa chỉ của lệnh theo sau lệnh gọi B được lưu trong ngăn xếp. Đây là cái gọi là địa chỉ trả lại tới chương trình A. Khi nó kết thúc, chương trình con B lấy địa chỉ trả về của chương trình A từ ngăn xếp và trả lại quyền điều khiển cho địa chỉ đó. Do đó, máy tính tiếp tục thực hiện chương trình A, bắt đầu bằng lệnh sau lệnh gọi. Hầu hết các bộ xử lý đều có các hướng dẫn đặc biệt hỗ trợ gọi chương trình con bằng cách trước tiên đẩy địa chỉ trả về vào ngăn xếp và quay lại từ chương trình con tại địa chỉ được lấy ra từ ngăn xếp. Thông thường lệnh gọi gọi là call, lệnh return gọi là return.

Các tham số của chương trình con hoặc hàm cũng được đẩy vào ngăn xếp trước khi nó được gọi. Thứ tự chúng được đặt trên ngăn xếp phụ thuộc vào quy ước của các ngôn ngữ cấp cao. Vì vậy, trong ngôn ngữ C hoặc C++, đối số hàm đầu tiên nằm ở trên cùng của ngăn xếp, đối số thứ hai ở dưới nó, v.v. Trong Pascal thì ngược lại: đối số cuối cùng của hàm nằm ở đầu ngăn xếp. (Nhân tiện, đây là lý do tại sao các hàm có số lượng đối số thay đổi, chẳng hạn như printf, có thể có trong C, nhưng không có trong Pascal.)

Trong Fortran-4, một trong những ngôn ngữ lập trình lâu đời nhất và thành công nhất, các đối số được truyền qua một vùng bộ nhớ đặc biệt, có thể không nằm trên ngăn xếp, vì cho đến cuối những năm 70 của thế kỷ 20 vẫn còn những máy tính như Máy tính IBM 360 hoặc ES không có ngăn triển khai phần cứng. Địa chỉ trả về cũng không được lưu trữ trên ngăn xếp mà trong các ô bộ nhớ được cố định cho mỗi chương trình con. Các lập trình viên gọi bộ nhớ đó là tĩnh theo nghĩa là các biến tĩnh luôn chiếm cùng một vị trí trong bộ nhớ bất kỳ lúc nào trong quá trình thực hiện chương trình. Khi chỉ sử dụng bộ nhớ tĩnh, việc đệ quy là không thể vì các giá trị trước đó của biến cục bộ sẽ bị hủy khi thực hiện lệnh gọi mới. Tham chiếu Fortran 4 chỉ sử dụng các biến tĩnh và đệ quy bị cấm. Cho đến nay, ngôn ngữ Fortran được sử dụng rộng rãi trong tính toán khoa học và kỹ thuật, tuy nhiên, tiêu chuẩn Fortran-90 hiện đại đã đưa vào bộ nhớ ngăn xếp, loại bỏ những thiếu sót của các phiên bản ngôn ngữ trước đó.