Ngăn xếp là gì? Ví dụ: máy tính viết bằng ký hiệu Ba Lan ngược
Ngăn xếp là một hiện tượng lập trình và là một giải pháp tự nhiên. Stack ngay lập tức bước chân vào lĩnh vực kinh doanh máy tính và trở nên “bản địa” như thể đó là nơi mọi chuyện bắt đầu.
Không có ngăn xếp, bộ xử lý không hoạt động, không có đệ quy và không thể tổ chức các lệnh gọi hàm hiệu quả. Bất kỳ thuật toán nào cũng có thể thực hiện mà không cần hàng đợi, danh sách, bộ sưu tập, mảng hoặc hệ thống đối tượng có tổ chức, nhưng không có gì hoạt động nếu không có bộ nhớ và ngăn xếp, bao gồm tất cả những điều trên.
Vào buổi bình minh của sự khởi đầu: bộ xử lý, bộ nhớ và ngăn xếp
Bộ nhớ lý tưởng cung cấp địa chỉ trực tiếp đến giá trị - đây là các cấp độ máy và ngôn ngữ ở mức độ cao. Trong trường hợp đầu tiên, bộ xử lý lặp tuần tự qua các địa chỉ bộ nhớ và thực hiện các lệnh. Trong trường hợp thứ hai, người lập trình thao tác với mảng. Cả hai tập đều chứa:
- địa chỉ = giá trị;
- chỉ số = giá trị.
Địa chỉ có thể là tuyệt đối và tương đối, chỉ mục có thể là số và liên kết. Địa chỉ và chỉ mục có thể chứa địa chỉ khác ngoài giá trị, nhưng đây là chi tiết về địa chỉ gián tiếp. Không có bộ nhớ, bộ xử lý không thể hoạt động và không có nhiều lệnh và dữ liệu, nó giống như một chiếc thuyền không có mái chèo.
Chồng đĩa là một câu chuyện truyền thống về bản chất của chồng đĩa: khái niệm chồng đĩa và sự dịch chuyển trong ý thức chung. Bạn không thể lấy đĩa từ bên dưới mà chỉ có thể lấy từ bên trên, khi đó tất cả các đĩa sẽ còn nguyên vẹn.
Bất cứ điều gì đến cuối cùng trong ngăn xếp sẽ được ưu tiên. Giải pháp hoàn hảo. Về bản chất, ngăn xếp, như một bản dịch của hành động này sang hành động khác, biến ý tưởng về thuật toán thành một chuỗi các thao tác.
Bản chất và khái niệm của ngăn xếp
Bộ xử lý và bộ nhớ - chính các nguyên tố cấu trúc máy tính. Bộ xử lý thực thi các hướng dẫn, thao tác với các địa chỉ bộ nhớ, truy xuất và sửa đổi các giá trị tại các địa chỉ này. Trong ngôn ngữ lập trình, tất cả điều này được chuyển thành các biến và giá trị của chúng. Bản chất của ngăn xếp và khái niệm nhập sau xuất trước (LIFO) vẫn không thay đổi.
Từ viết tắt LIFO không còn được sử dụng thường xuyên như trước nữa. Có thể là do danh sách đã được chuyển thành đối tượng và hàng đợi vào trước ra trước (FIFO) được sử dụng khi cần thiết. Tính năng động của các kiểu dữ liệu đã mất đi sự liên quan trong bối cảnh mô tả các biến, nhưng đã đạt được ý nghĩa của nó tại thời điểm thực hiện các biểu thức: loại dữ liệu được xác định tại thời điểm sử dụng và cho đến thời điểm đó bạn có thể mô tả bất cứ điều gì và bất cứ cách nào bạn muốn.
Vậy, chồng - nó là gì? Bây giờ bạn biết rằng đây là một câu hỏi không phù hợp. Rốt cuộc, không có ngăn xếp thì không có lập trình hiện đại. Bất kỳ lệnh gọi hàm nào đều có nghĩa là truyền tham số và địa chỉ trả về. Một hàm có thể gọi một hàm khác - đây lại là việc truyền tham số và địa chỉ trả về. Việc thiết lập cơ chế gọi các giá trị mà không cần ngăn xếp là một công việc bổ sung, mặc dù chắc chắn có thể đạt được một giải pháp khả thi.
Nhiều người hỏi: "Stack - nó là gì?" Trong ngữ cảnh của một lệnh gọi hàm, nó bao gồm ba hành động:
- lưu địa chỉ trả lại;
- lưu tất cả các biến hoặc địa chỉ được chuyển vào chúng;
- lời gọi hàm.
Khi hàm được gọi đã hoàn thành nhiệm vụ của mình, nó sẽ chỉ trả quyền điều khiển về địa chỉ trả về. Một hàm có thể gọi bất kỳ số lượng hàm nào khác vì giới hạn chỉ là kích thước của ngăn xếp.
Thuộc tính ngăn xếp
Ngăn xếp không phải là một kiểu dữ liệu trừu tượng mà là một cơ chế thực sự. Ở cấp độ bộ xử lý, nó là một “động cơ” tinh chỉnh và bổ sung công việc của chu trình xử lý chính. Giống như số học bit, ngăn xếp nắm bắt các quy tắc hoạt động đơn giản và rõ ràng. Nó đáng tin cậy và an toàn.
Các thuộc tính đặc trưng của ngăn xếp là kích thước và độ dài các phần tử của nó. Ở cấp độ bộ xử lý, mọi thứ được xác định bởi dung lượng bit, địa chỉ bộ nhớ và tính chất vật lý của việc truy cập vào nó. Tính năng thú vị và truyền thống: ngăn xếp phát triển đi xuống, nghĩa là theo hướng giảm địa chỉ bộ nhớ và bộ nhớ chương trình và dữ liệu - hướng lên trên. Điều này là phổ biến, nhưng không bắt buộc. Ý nghĩa ở đây rất quan trọng - anh ấy đến sau cùng và rời đi trước. Quy tắc đơn giản đáng ngạc nhiên này cho phép bạn xây dựng các thuật toán thú vị hoạt động chủ yếu bằng ngôn ngữ cấp độ cao. Bây giờ bạn sẽ không hỏi, ngăn xếp là gì?
Công việc hoàn hảo phần cứngđã là chuẩn mực trong một thời gian rất dài, nhưng được đặt lên hàng đầu công nghệ thông tinÝ tưởng về ngăn xếp đang thu được những ứng dụng mới và đầy hứa hẹn.
Về cơ bản, ngăn xếp ở cấp bộ xử lý không quan trọng. Nó là một phần tự nhiên của kiến trúc máy tính. Nhưng trong lập trình, ngăn xếp còn phụ thuộc vào ứng dụng cụ thể và khả năng của người lập trình.
Mảng, bộ sưu tập, danh sách, hàng đợi... Xếp chồng!
Mọi người thường đặt câu hỏi: "Stack - nó là gì?" “Lập trình” và “hệ thống hóa” là những khái niệm thú vị: chúng không phải là từ đồng nghĩa nhưng chúng có liên quan rất chặt chẽ với nhau. Lập trình đã đi một chặng đường dài rất nhanh đến mức đạt đến đỉnh cao dường như là lý tưởng. Rất có thể đây không phải là trường hợp. Nhưng rõ ràng là một cái gì đó khác.
Ý tưởng về ngăn xếp đã trở nên quen thuộc không chỉ ở cấp độ của các ngôn ngữ lập trình khác nhau mà còn ở cấp độ thiết kế và khả năng tạo kiểu dữ liệu của chúng. Bất kỳ mảng nào cũng có push và pop, và khái niệm “phần tử đầu tiên và phần tử cuối cùng của mảng” đã trở thành truyền thống. Trước đây chỉ có các phần tử mảng, nhưng ngày nay có:
- phần tử mảng;
- phần tử đầu tiên của mảng;
- phần tử cuối cùng của mảng.
Thao tác đặt một phần tử vào mảng sẽ di chuyển con trỏ và truy xuất một phần tử từ đầu mảng hoặc từ cuối mảng tạo nên sự khác biệt. Về cơ bản đây là cùng một ngăn xếp nhưng được áp dụng cho các kiểu dữ liệu khác.
Điều đặc biệt đáng chú ý là các ngôn ngữ lập trình phổ biến không có cấu trúc ngăn xếp. Nhưng họ cung cấp đầy đủ ý tưởng của mình cho nhà phát triển.
Xin chào, tôi là sinh viên năm thứ hai Đạ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”).
Một định nghĩa khá đầy đủ nhưng có lẽ hơi khó hiểu đối với người mới bắt đầu.
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à hình thức một chồng sách, trong đó cuốn sách trên cùng là trên cùng.
Trên thực tế, một ngăn xếp có thể được biểu diễn dưới dạng một chồng của bất kỳ đồ vật nào, có thể là chồng khăn trải giường, sổ ghi chép, áo sơ mi, v.v., nhưng tôi nghĩ ví dụ với sách sẽ là tối ưu nhất.
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 nó vào phần tử mới
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; //Viết số được yêu cầu vào Data 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 phần 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 đó Một quyển sách mới tự động trở thành trên cùng, vì ngăn xếp không phải là một 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à đánh đồng (đặt) nó lên trên cùng 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ề 0, 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 số "-2738568384" hoặc các số 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ẽ một 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 trong trường hợp nàyđóng vai trò giống như một con trỏ trong sổ ghi chú, nó chạy quanh toàn bộ ngăn xếp cho đến khi trở thành NULL( while(q != NULL)), nói cách khác, 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à phần tử tiếp theo KHÔNG. 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 bạn không kết nối này, 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 đưa ra Giá trị rỗng//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); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //sau khi thực thi 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 đó, xóa 4, chúng ta nhận được 5321 trên ngăn xếp printf_s("\n");//dịch sang dòng mới s_print(top);//print system("pause");//pause)
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ẽ được tạo và thay đổi chỉ 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
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.
Thẻ: Thêm thẻ
Thẻ: Ngăn xếp, ngăn xếp trong C, triển khai ngăn xếp, xếp chồng trên một mảng, ngăn xếp tăng trưởng linh hoạt, xếp chồng trên một hệ thống được kết nối đơn lẻ
Cây rơm
S tek có lẽ là nhất Cấu trúc đơn giản dữ liệu mà chúng tôi sẽ nghiên cứu và chúng tôi sẽ thường xuyên sử dụng. Ngăn xếp là một cấu trúc dữ liệu trong đó các phần tử hỗ trợ nguyên tắc LIFO (“Vào sau – ra trước”): vào sau, ra trước. Hoặc vào trước, ra sau.
Ngăn xếp cho phép bạn lưu trữ các phần tử và thường hỗ trợ hai thao tác cơ bản:
- XÔ– đặt một phần tử lên trên cùng của ngăn xếp
- NHẠC POP– loại bỏ một phần tử khỏi đỉnh ngăn xếp, di chuyển phần tử trên cùng sang phần tử tiếp theo
Cũng phổ biến là hoạt động PEEK, lấy một phần tử ở đầu ngăn xếp nhưng không loại bỏ nó khỏi đó.
Ngăn xếp là một trong cấu trúc cơ bản dữ liệu và được sử dụng không chỉ trong lập trình mà còn trong thiết kế mạch và đơn giản là trong sản xuất để thực hiện quy trình công nghệ vân vân.; Ngăn xếp được sử dụng làm cấu trúc dữ liệu phụ trợ trong nhiều thuật toán và các cấu trúc phức tạp hơn khác.
Ví dụ, chúng ta có một dãy số. Hãy chạy một vài lệnh. Ban đầu ngăn xếp trống. Phần trên cùng của ngăn xếp là con trỏ tới phần tử đầu tiên, nó không trỏ đến đâu cả. Trong trường hợp C, nó có thể bằng NULL.
Ngăn xếp bây giờ bao gồm một phần tử, số 3. Đỉnh của ngăn xếp trỏ đến số 3.
Ngăn xếp bao gồm hai phần tử, 5 và 3, với đỉnh của ngăn xếp trỏ đến 5.
Ngăn xếp bao gồm ba phần tử, đỉnh của ngăn xếp trỏ đến 7.
Nó sẽ trả về giá trị 7, để lại 5 và 3 trong ngăn xếp, phần trên cùng sẽ trỏ đến phần tử tiếp theo – 5.
Trả về 5, chỉ để lại một phần tử trên ngăn xếp, 3, mà đỉnh ngăn xếp sẽ trỏ tới.
Trả về 3, ngăn xếp sẽ trống.
Một chồng thường được so sánh với một chồng đĩa. Để có được đĩa tiếp theo, bạn cần xóa những cái trước đó. Đỉnh của chồng đĩa là đỉnh của chồng đĩa.
Khi chúng ta làm việc với ngăn xếp, có thể xảy ra hai lỗi chính và phổ biến:
- 1. Stack Underflow: Cố gắng lấy một phần tử từ ngăn xếp trống
- 2. Tràn ngăn xếp: Cố gắng đặt một phần tử mới vào ngăn xếp không thể phát triển được nữa (ví dụ: không đủ RAM)
Triển khai phần mềm
Chúng ta hãy nhìn vào ba triển khai đơn giản cây rơm:
Ngăn xếp kích thước cố định được xây dựng trên một mảng
Điểm đặc biệt là dễ thực hiện và tốc độ tối đa chấp hành. Một ngăn xếp như vậy có thể được sử dụng khi kích thước tối đa của nó được biết trước hoặc được biết là nhỏ.
Đầu tiên, chúng tôi xác định kích thước tối đa của mảng và loại dữ liệu sẽ được lưu trữ trong đó:
#define STACK_MAX_SIZE 20 typedef int T;
Bây giờ chính cấu trúc
Typedef struct Stack_tag ( Dữ liệu T; kích thước size_t; ) Stack_t;
Ở đây, kích thước thay đổi là số phần tử, đồng thời là một con trỏ lên đỉnh ngăn xếp. Phần trên cùng sẽ trỏ đến phần tử tiếp theo của mảng, phần tử này sẽ chứa giá trị.
Chúng tôi đặt một phần tử mới vào ngăn xếp.
Void Push(Stack_t *stack, const T value) ( stack->data = value; stack->size++; )
Vấn đề duy nhất là bạn có thể vượt ra ngoài mảng. Vì vậy, bạn phải luôn kiểm tra xem có lỗi tràn Stack nào không:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) ( if (stack->size >= STACK_MAX_SIZE) ( exit(STACK_OVERFLOW); ) stack->data = value; stack- >kích thước++ ; )
Tương tự, hãy xác định thao tác Pop trả về một phần tử từ trên cùng và chuyển sang phần tiếp theo
T pop(Stack_t *stack) ( if (stack->size == 0) ( exit(STACK_UNDERFLOW); ) stack->size--; return stack->data; )
VÀ chức năng nhìn trộm, trả về phần tử hiện tại từ đầu
Teek(const Stack_t *stack) ( if (stack->size<= 0) { exit(STACK_UNDERFLOW); } return stack->dữ liệu; )
Khác lưu ý quan trọng– chúng tôi không có chức năng tạo ngăn xếp, vì vậy chúng tôi cần đặt lại giá trị kích thước theo cách thủ công
Các hàm trợ giúp để in các phần tử ngăn xếp
Void printStackValue(const T value) ( printf("%d", value); ) void printStack(const Stack_t *stack, void (*printStackValue)(const T)) ( int i; int len = stack- >size - 1 ; printf("stack %d > ", stack->size); for (i = 0; i< len; i++) { printStackValue(stack->dữ liệu [i]); printf(" | "); ) if (stack->size != 0) ( printStackValue(stack->data[i]); ) printf("\n"); )
Lưu ý rằng trong hàm print chúng ta sử dụng int thay vì size_t vì len có thể trở thành số âm. Hàm in kích thước ngăn xếp trước rồi đến nội dung của nó, phân tách các phần tử bằng |
Bài kiểm tra
Ngăn xếp Stack_t; stack.size = 0; đẩy(&stack, 3); printStack(&stack, printStackValue); đẩy(&stack, 5); printStack(&stack, printStackValue); đẩy(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();
Chúng ta cũng hãy xem xét các tình huống có lỗi sử dụng. Dòng chảy ngầm
Void main() ( Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); )
Void main() ( Stack_t stack; size_t i; stack.size = 0; for (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }
Ngăn xếp tăng trưởng động trên một mảng
Ngăn xếp tăng trưởng động được sử dụng khi số lượng phần tử có thể lớn và không xác định được tại thời điểm giải quyết vấn đề. Kích thước tối đa Ngăn xếp có thể bị giới hạn bởi một số lượng nhất định hoặc bởi kích thước của RAM.
Ngăn xếp sẽ bao gồm một con trỏ tới dữ liệu, kích thước của mảng (tối đa) và số phần tử trong mảng. Con số này cũng sẽ chỉ ra phía trên.
Typedef struct Stack_tag ( T *data; size_t size; size_t top; ) Stack_t;
Đầu tiên, bạn sẽ cần một số kích thước mảng ban đầu, hãy để nó là 10
#xác định INIT_SIZE 10
Thuật toán hoạt động như thế này: chúng tôi kiểm tra xem giá trị của top có vượt quá giá trị của kích thước hay không. Nếu giá trị vượt quá thì chúng ta sẽ tăng kích thước của mảng. Có một số tùy chọn ở đây về cách tăng mảng. Bạn có thể thêm một số, bạn có thể nhân với một giá trị nào đó. Tùy chọn nào tốt hơn phụ thuộc vào chi tiết cụ thể của nhiệm vụ. Trong trường hợp của chúng tôi, chúng tôi sẽ nhân kích thước với số MULTIPLIER
#xác định SỐ NHÂN 2
Chúng tôi sẽ không đặt kích thước tối đa. Chương trình sẽ bị lỗi nếu tràn ngăn xếp hoặc tràn ngăn xếp. Chúng ta sẽ thực hiện cùng một giao diện (pop, push, look). Ngoài ra, vì mảng là động nên chúng tôi sẽ tạo một số hàm trợ giúp để tạo ngăn xếp, xóa và dọn dẹp ngăn xếp.
Đầu tiên là chức năng tạo, xóa ngăn xếp và một số lỗi
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() ( Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) ( exit(OUT_OF_MEMORY); ) out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) ( free(out); exit(OUT_OF_MEMORY); ) out- >top = 0; return out; ) void deleteStack(Stack_t **stack) ( free((*stack)->data); free(*stack); *stack = NULL; )
Mọi thứ đều cực kỳ đơn giản và rõ ràng, không có thủ đoạn nào cả. Chúng tôi tạo một ngăn xếp có độ dài ban đầu và đặt lại các giá trị.
Bây giờ hãy viết chức năng phụ trợ thay đổi kích thước.
Đổi kích thước trống(Stack_t *stack) ( stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) ( thoát(STACK_OVERFLOW); ) )
Ở đây, lưu ý rằng nếu không thể phân bổ đủ bộ nhớ, nó sẽ thoát với STACK_OVERFLOW.
Hàm push kiểm tra xem chúng ta có vượt quá giới hạn của mảng hay không. Nếu có thì tăng kích thước của nó lên
Void push(Stack_t *stack, T value) ( if (stack->top >= stack->size) ( thay đổi kích thước(stack); ) stack->data = value; stack->top++; )
Các hàm pop và look tương tự như các hàm được sử dụng cho mảng có kích thước cố định
T pop(Stack_t *stack) ( if (stack->top == 0) ( exit(STACK_UNDERFLOW); ) stack->top--; return stack->data; ) Teek(const Stack_t *stack) ( if ( ngăn xếp-> trên cùng<= 0) { exit(STACK_UNDERFLOW); } return stack->dữ liệu; )
Hãy kiểm tra
Void main() ( int i; Stack_t *s = createStack(); for (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Hãy viết một hàm khác, implode, để giảm kích thước mảng xuống bằng số các phần tử trong mảng. Nó có thể được sử dụng khi đã biết rằng sẽ không có phần tử nào được chèn thêm nữa và bộ nhớ có thể được giải phóng một phần.
Void implode(Stack_t *stack) ( stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); )
Chúng ta có thể sử dụng trong trường hợp của chúng tôi
Với (i = 0; tôi< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Việc triển khai ngăn xếp đơn luồng này sử dụng ít quyền truy cập bộ nhớ, khá đơn giản và có mục đích chung, chạy nhanh và có thể được triển khai, nếu cần, trong vài phút. Nó luôn được sử dụng kể từ đó trừ khi có ghi chú khác.
Nó có một nhược điểm liên quan đến phương pháp tăng mức tiêu thụ bộ nhớ. Khi nhân với hệ số 2 (trong trường hợp của chúng tôi), cần ít quyền truy cập bộ nhớ, nhưng mỗi lần tăng tiếp theo có thể dẫn đến lỗi, đặc biệt nếu dung lượng bộ nhớ trong hệ thống nhỏ. Nếu bạn sử dụng phương pháp phân bổ bộ nhớ nhẹ nhàng hơn (ví dụ: thêm 10 mỗi lần), thì số lượng truy cập sẽ tăng lên và tốc độ sẽ giảm xuống. Ngày nay, thường không có vấn đề gì về kích thước bộ nhớ, đồng thời các trình quản lý bộ nhớ và trình thu gom rác (không có trong C) hoạt động nhanh chóng, do đó, sự thay đổi mạnh mẽ chiếm ưu thế (ví dụ: việc triển khai toàn bộ thư viện tiêu chuẩn của ngôn ngữ Java).
Triển khai ngăn xếp trên danh sách liên kết đơn
Danh sách liên kết đơn là gì? Tóm lại: một danh sách liên kết đơn bao gồm các nút, mỗi nút chứa thông tin hữu ích và một liên kết đến nút tiếp theo. Nút cuối cùng đề cập đến NULL.
Không có mức tối đa và kích thước tối thiểu chúng tôi sẽ không có (mặc dù trong trường hợp chung Có lẽ). Mỗi phần tử mới được tạo ra một lần nữa. Đầu tiên, hãy xác định cấu trúc nút
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag ( Giá trị T; struct Node_tag *next; ) Node_t;
Chức năng chèn phần tử đầu tiên rất đơn giản: tạo một nút mới. Con trỏ tiếp theo được ném tới nút cũ. Tiếp theo, chúng ta chuyển con trỏ lên đầu ngăn xếp tới nút mới tạo. Đỉnh của ngăn xếp bây giờ trỏ đến nút mới.
Void push(Node_t **head, T value) ( Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) ( exit(STACK_OVERFLOW); ) tmp->next = *head; tmp- >giá trị = giá trị; *head = tmp; )
Hàm pop lấy phần tử đầu tiên (phần tử được trỏ đến bởi đỉnh), ném con trỏ tới phần tử tiếp theo và trả về phần tử đầu tiên. Có hai tùy chọn ở đây - bạn có thể trả về một nút hoặc một giá trị. Nếu trả về một giá trị, chúng ta sẽ phải xóa nút bên trong hàm
Node_t* pop1(Node_t **head) ( Node_t *out; if ((*head) == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; return out; )
T pop2(Node_t **head) ( Node_t *out; Giá trị T; if (*head == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; value = out ->giá trị; miễn phí(ra); giá trị trả về; )
Bây giờ, thay vì kiểm tra độ dài của mảng, việc kiểm tra sự bằng nhau của đỉnh ngăn xếp với NULL được sử dụng ở mọi nơi.
Chức năng xem nhanh đơn giản
Teek(const Node_t* head) ( if (head == NULL) ( exit(STACK_UNDERFLOW); ) trả về head->value; )
Việc lặp lại khá thú vị. Chúng ta chỉ cần di chuyển từ nút này sang nút khác cho đến khi kết thúc
Void printStack(const Node_t* head) ( printf("stack >"); while (head) ( printf("%d ", head->value); head = head->next; ) )
Và một vấn đề nữa - bây giờ bạn không thể chỉ nhìn vào kích thước ngăn xếp. Bạn cần phải đi từ đầu đến cuối và đếm tất cả các phần tử. Ví dụ như thế này
Size_t getSize(const Node_t *head) ( size_t size = 0; while (head) ( size++; head = head->next; ) trả về kích thước; )
Tất nhiên, bạn có thể lưu trữ kích thước riêng biệt, bạn có thể bọc ngăn xếp với tất cả dữ liệu trong cấu trúc khác, v.v. Hãy xem xét tất cả những điều này khi nghiên cứu danh sách chi tiết hơn.
Khi thành thạo lập trình, sớm hay muộn câu hỏi cũng đặt ra: " Ngăn xếp là gì?".
Tôi nghĩ cách rõ ràng nhất để giải thích điều này là một chương trình hợp ngữ (đừng lo lắng) chỉ cần thêm dữ liệu vào ngăn xếp.
Cây rơm là một cấu trúc dữ liệu vốn có trong tất cả các công nghệ lập trình. Thông thường, nguyên lý hoạt động của ngăn xếp được so sánh với một chồng đĩa: để lấy cái thứ hai từ trên xuống, bạn cần loại bỏ cái trên cùng. Ngăn xếp thường được gọi là băng đạn - tương tự như băng đạn trong súng (việc bắn sẽ bắt đầu với hộp đạn được nạp cuối cùng).
Tại sao tất cả điều này là cần thiết?
Bạn khó có thể viết một chương trình không sử dụng các hàm (chương trình con). Khi một hàm được gọi, địa chỉ sẽ được sao chép vào ngăn xếp để trả về sau khi quá trình thực hiện chương trình con đã cho kết thúc. Khi kết thúc quá trình thực thi, địa chỉ được trả về từ ngăn xếp đến bộ đếm chương trình và chương trình tiếp tục được thực thi từ điểm sau hàm.
Cũng cần phải đặt các thanh ghi được sử dụng trong chương trình con này vào ngăn xếp (trong các ngôn ngữ cấp cao, trình biên dịch thực hiện việc này).
Tất cả những điều trên là điển hình cho cái gọi là ngăn xếp phần cứng. Tôi hy vọng bạn nhận ra rằng cấu trúc dữ liệu này (LIFO - vào sau, ra trước) không chỉ hữu ích khi làm việc ở mức độ thấp. Thường có nhu cầu lưu trữ dữ liệu theo thứ tự này (ví dụ: một thuật toán nổi tiếng để phân tích các biểu thức số học dựa trên việc làm việc với một ngăn xếp), sau đó các lập trình viên triển khai một ngăn xếp phần mềm.
Làm thế nào nó hoạt động?
Hãy hãy xem cách làm việc với ngăn xếp sử dụng ví dụ về bộ điều khiển dòng MSP430. Tôi chọn chúng chỉ vì tôi tình cờ cài đặt một môi trường để làm việc với chúng.
Trong MSP430, ngăn xếp dựa trên thiết kế giảm dần trước. Những thứ kia. Trước khi bạn ghi dữ liệu vào ngăn xếp, nó sẽ giảm địa chỉ của đỉnh ngăn xếp (đĩa trên cùng). Ngoài ra còn có tăng dần sau/tăng dần (trừ/cộng phần trên cùng của ngăn xếp xảy ra sau khi dữ liệu được ghi) và tăng trước (trước khi ghi, địa chỉ của phần trên cùng được tăng lên).
Nếu ngăn xếp tăng địa chỉ của nó khi ghi dữ liệu thì nó được gọi là ngăn xếp tăng lên; nếu nó giảm đi thì nó được gọi là tăng xuống.
Thanh ghi SP chịu trách nhiệm lưu trữ địa chỉ của đỉnh ngăn xếp.
Như bạn có thể thấy, địa chỉ đỉnh mặc định là 0x0A00.
Hãy xem xét chương trình này:
ĐẨY #0123h ; Đặt 0123h lên trên cùng của ngăn xếp (TOS); sao chép dữ liệu từ bộ nhớ MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; viết thêm hai số PUSH #9250h PUSH #0000h ; bật dữ liệu từ ngăn xếp POP R8 POP R9 POP R10
Chương trình này làm gì?
Với lệnh PUSH, chúng ta đẩy dữ liệu 0123h vào ngăn xếp. Có vẻ như với lệnh này, chúng ta sẽ ghi 0123h vào bộ nhớ tại địa chỉ 0x0A00, nhưng chúng ta nhớ rằng ngăn xếp của chúng ta có tính chất giảm dần trước. Do đó, đầu tiên địa chỉ giảm đi 2 (0x0A00 - 2 = 0x09FE) và dữ liệu được ghi vào ô có địa chỉ kết quả.
Bộ nhớ ban đầu trông như thế này:
Sau khi thực hiện lệnh PUSH (các thay đổi được tô sáng màu đỏ):
Vậy là dữ liệu đã được ghi lại.
Hãy kiểm tra xem điều này có đúng hay không bằng cách thực hiện hai lệnh truyền (mov). Đầu tiên chúng ta sẽ nhận dữ liệu từ ô 0x0A00 và ghi vào thanh ghi R5, sau đó ghi dữ liệu từ ô 0x09FE vào thanh ghi R6.
Sau này, các thanh ghi sẽ chứa dữ liệu sau:
Khi thực thi các lệnh POP, đỉnh của ngăn xếp sẽ tăng thêm 2 với mỗi lệnh và dữ liệu trong các thanh ghi R8-10 sẽ lần lượt là 0x0000, 0x9250 và 0x0123.
Khi nhiều dữ liệu được thêm vào, bộ nhớ (vẫn chứa dữ liệu được lấy ra từ ngăn xếp) sẽ chứa đầy các giá trị mới.
Bạn có thể minh họa cách làm việc với một ngăn xếp như thế này (từ trái sang phải):
Ban đầu, địa chỉ ngăn xếp là 0x0A00, 0000 được lưu trong đó. Khi PUSH được thực thi, ô bên dưới (có địa chỉ 0x09FE) trở thành đầu ngăn xếp và dữ liệu được ghi vào đó. Với mỗi lệnh tiếp theo phần trên cùng thấp hơn trong bộ nhớ.
Khi thực hiện lệnh POP, hình ảnh sẽ bị đảo ngược.
Tôi mong chờ câu hỏi của bạn trong phần bình luận.
Bộ nhớ được sử dụng bởi các chương trình bao gồm một số phần - phân đoạn:
đoạn mã(hoặc "đoạn văn bản") nơi đặt chương trình đã biên dịch. Đoạn mã thường ở dạng chỉ đọc;
phân đoạn bss(hoặc "phân đoạn dữ liệu chưa được khởi tạo"), nơi lưu trữ các giá trị toàn cầu và giá trị khởi tạo bằng 0;
đoạn dữ liệu(hoặc "phân đoạn dữ liệu được khởi tạo"), nơi lưu trữ các biến toàn cục và biến tĩnh được khởi tạo;
ĐẾNgiảng bài(heap), từ đó các biến động được phân bổ;
ngăn xếp cuộc gọi, nơi lưu trữ các biến cục bộ và thông tin khác liên quan đến hàm.
Trong hướng dẫn này, chúng ta sẽ chỉ xem xét heap và stack, vì đó là nơi diễn ra mọi điều thú vị.
Đống
Phân đoạn đống(hoặc đơn giản " một bó") theo dõi bộ nhớ được sử dụng để phân bổ động. Chúng ta đã nói một chút về vùng heap trong .
Trong C++, khi sử dụng toán tử new để chọn bộ nhớ động, bộ nhớ này được phân bổ trong phân đoạn heap của chính ứng dụng.
int *ptr = int mới; // ptr phân bổ 4 byte từ heap int *array = new int; // mảng phân bổ 40 byte từ heap
Địa chỉ của bộ nhớ được cấp phát được toán tử mới truyền lại và sau đó có thể được lưu trữ trong các tệp . Về cơ chế lưu trữ và phân bổ giải phóng bộ nhớ Bây giờ chúng ta không còn gì phải lo lắng nữa. Tuy nhiên, cần biết rằng các yêu cầu bộ nhớ tuần tự không phải lúc nào cũng dẫn đến việc cấp phát địa chỉ bộ nhớ tuần tự!
int *ptr1 = int mới; int *ptr2 = int mới; // ptr1 và ptr2 có thể không có địa chỉ liên tiếp
Khi một biến được cấp phát động bị xóa, bộ nhớ sẽ được trả về vùng heap và sau đó có thể được gán lại (dựa trên các yêu cầu tiếp theo). Hãy nhớ rằng việc xóa một con trỏ không xóa biến, nó chỉ khiến bộ nhớ tại địa chỉ đó được trả về hệ điều hành.
Heap có những ưu điểm và nhược điểm:
Việc phân bổ bộ nhớ trên heap tương đối chậm.
Bộ nhớ được phân bổ vẫn được phân bổ cho đến khi nó được giải phóng (coi chừng rò rỉ bộ nhớ) hoặc cho đến khi ứng dụng kết thúc (lúc đó hệ điều hành phải lấy lại bộ nhớ).
Bộ nhớ được cấp phát động chỉ được truy cập thông qua một con trỏ. Việc hủy tham chiếu một con trỏ chậm hơn so với việc truy cập trực tiếp vào một biến.
Vì heap là một kho chứa lớn bộ nhớ nên nó được sử dụng để phân bổ các hoặc các lớp lớn.
Ngăn xếp cuộc gọi
Ngăn xếp cuộc gọi(hoặc đơn giản " cây rơm") có vai trò thú vị hơn nhiều. Ngăn xếp cuộc gọi theo dõi tất cả các hàm đang hoạt động (những hàm đã được gọi nhưng chưa hoàn thành) từ đầu chương trình đến điểm thực thi hiện tại và xử lý việc phân bổ tất cả các tham số hàm và biến cục bộ.
Ngăn xếp cuộc gọi được triển khai dưới dạng cấu trúc dữ liệu Ngăn xếp. Vì vậy, trước khi nói về cách hoạt động của ngăn xếp cuộc gọi, chúng ta cần hiểu cấu trúc dữ liệu “Ngăn xếp” là gì.
Cấu trúc dữ liệu ngăn xếp
Cấu trúc dữ liệu là một cơ chế lập trình để tổ chức dữ liệu sao cho nó có thể được sử dụng một cách hiệu quả. Bạn đã thấy một số loại cấu trúc dữ liệu, chẳng hạn như mảng và cấu trúc. Chúng cung cấp các cơ chế để lưu trữ và truy cập dữ liệu một cách hiệu quả. Có nhiều cấu trúc dữ liệu bổ sung thường được sử dụng trong lập trình, một số cấu trúc được triển khai trong thư viện chuẩn C++ và Stack là một trong số đó.
Hãy xem xét một chồng đĩa trên bàn. Vì mỗi đĩa đều nặng và được xếp chồng lên nhau nên bạn chỉ có thể thực hiện một trong ba việc sau:
Nhìn vào bề mặt của tấm trên cùng.
Lấy tấm trên cùng ra khỏi ngăn xếp (do đó sẽ lộ ra tấm tiếp theo, nằm bên dưới - nếu có).
Đặt một chiếc đĩa mới lên trên chồng đĩa (giấu chiếc đĩa trên cùng bên dưới, nếu có).
Trong lập trình máy tính, ngăn xếp là một cấu trúc dữ liệu giống như vùng chứa chứa một số biến (tương tự như một mảng). Tuy nhiên, trong khi mảng cho phép bạn truy cập và thay đổi các phần tử theo bất kỳ thứ tự nào (được gọi là " truy cập ngẫu nhiên"), thì ngăn xếp sẽ bị hạn chế hơn. Các thao tác có thể được thực hiện trên ngăn xếp tương ứng với ba thao tác được liệt kê ở trên. Trên ngăn xếp bạn có thể:
Nhìn vào phần tử trên cùng của ngăn xếp (sử dụng hàm đứng đầu() hoặc nhìn trộm() ).
Kéo phần tử trên cùng của ngăn xếp ra (dùng hàm nhạc pop() ).
Thêm một phần tử mới vào đầu ngăn xếp (sử dụng hàm xô() ).
Cây rơm là một cấu trúc như LIFO(Vào sau, ra trước - người đến sau, người về trước). Phần tử cuối cùng được đẩy lên đỉnh ngăn xếp sẽ là phần tử đầu tiên được đưa ra khỏi ngăn xếp. Nếu bạn đặt một chiếc đĩa mới lên trên một chồng đĩa khác thì đó sẽ là chiếc đĩa đầu tiên bạn nhặt. Khi các phần tử được đẩy vào ngăn xếp, ngăn xếp sẽ tăng lên; khi các phần tử được lấy ra khỏi ngăn xếp, ngăn xếp sẽ co lại.
Ví dụ, hãy xem xét trình tự ngắn cho thấy cách thêm và xóa trên ngăn xếp hoạt động:
Ngăn xếp: trống
Đẩy 1
Ngăn xếp: 1
Đẩy 2
Ngăn xếp: 1 2
Đẩy 3
Ngăn xếp: 1 2 3
Đẩy 4
Ngăn xếp: 1 2 3 4
Nhạc pop
Ngăn xếp: 1 2 3
Nhạc pop
Ngăn xếp: 1 2
Nhạc pop
Ngăn xếp: 1
Một chồng đĩa là một sự tương tự khá hay về cách thức hoạt động của một ngăn xếp, nhưng có một sự tương tự tốt hơn. Ví dụ: hãy xem xét một số hộp thư nằm chồng lên nhau. Mỗi hộp thư chỉ có thể chứa một mục và ban đầu tất cả các hộp thư đều trống. Ngoài ra, mỗi hộp thư đều được đóng đinh vào đáy hộp thư nên số lượng hộp thư không thể thay đổi được. Nếu chúng ta không thể thay đổi số lượng hộp thư thì làm sao chúng ta có được hành vi giống như ngăn xếp?
Đầu tiên, chúng tôi sử dụng nhãn dán để cho biết hộp thư trống thấp nhất ở đâu. Lúc đầu, đây sẽ là hộp thư đầu tiên trên sàn. Khi chúng tôi thêm một mục vào ngăn xếp hộp thư của mình, chúng tôi sẽ đặt mục đó vào hộp thư có nhãn dán (tức là hộp thư trống đầu tiên trên sàn), sau đó di chuyển nhãn dán lên một hộp thư cao hơn. Khi chúng ta lấy một phần tử ra khỏi ngăn xếp, chúng ta di chuyển nhãn dán xuống một hộp thư và xóa phần tử đó khỏi ngăn xếp. hộp thư. Mọi thứ bên dưới điểm đánh dấu đều nằm trên ngăn xếp. Mọi thứ trong hộp có nhãn dán trở lên đều không có trong ngăn xếp.
Phân đoạn ngăn xếp cuộc gọi
Phân đoạn ngăn xếp cuộc gọi chứa bộ nhớ được sử dụng cho ngăn xếp cuộc gọi. Khi ứng dụng khởi động, hàm main() sẽ được đẩy lên ngăn xếp cuộc gọi hệ điều hành. Sau đó chương trình bắt đầu thực hiện.
Khi một chương trình gặp một lệnh gọi hàm, hàm đó sẽ được đẩy lên ngăn xếp cuộc gọi. Khi một hàm hoàn thành việc thực thi, nó sẽ bị xóa khỏi ngăn xếp cuộc gọi. Bằng cách này, bằng cách xem xét các hàm được thêm vào ngăn xếp, chúng ta có thể thấy tất cả các hàm đã được gọi đến thời điểm thực thi hiện tại.
Sự tương tự hộp thư của chúng tôi thực sự là cách hoạt động của ngăn xếp cuộc gọi. Ngăn xếp cuộc gọi có số lượng địa chỉ bộ nhớ cố định (kích thước cố định). Hộp thư là địa chỉ bộ nhớ và các "mục" chúng tôi thêm và bật lên ngăn xếp được gọi khung(Hoặc nhiều hơn " nhân viên") cây rơm. Khung ngăn xếp theo dõi tất cả dữ liệu được liên kết với một lệnh gọi hàm. "Nhãn dán" là một thanh ghi ( phần nhỏ bộ nhớ trong CPU), đó là con trỏ ngăn xếp. Con trỏ ngăn xếp theo dõi vị trí trên cùng của ngăn xếp cuộc gọi.
Sự khác biệt duy nhất giữa ngăn xếp cuộc gọi thực tế và ngăn xếp hộp thư giả định của chúng tôi là khi chúng tôi bật một phần tử khỏi ngăn xếp cuộc gọi, chúng tôi không phải xóa bộ nhớ (tức là bật toàn bộ nội dung của hộp thư). Chúng ta có thể chỉ cần để lại bộ nhớ này cho phần tử tiếp theo, phần tử này sẽ ghi đè lên nó. Vì con trỏ ngăn xếp sẽ ở bên dưới địa chỉ bộ nhớ này nên như chúng ta đã biết, vị trí bộ nhớ này sẽ không nằm trên ngăn xếp.
Ngăn xếp cuộc gọi trong thực tế
Chúng ta hãy xem xét kỹ hơn cách hoạt động của ngăn xếp cuộc gọi. Dưới là trình tự các bước thực hiện khi gọi hàm:
Chương trình gặp một cuộc gọi chức năng.
Một khung ngăn xếp được tạo và đặt trên ngăn xếp, nó bao gồm:
Địa chỉ của lệnh nằm phía sau lệnh gọi hàm (được gọi là " địa chỉ trả lại"). Đây là cách bộ xử lý ghi nhớ nơi cần quay lại sau khi thực hiện một chức năng.
Đối số chức năng.
Bộ nhớ cho các biến cục bộ.
Bản sao đã lưu của tất cả các thanh ghi được sửa đổi bởi hàm, sẽ cần được khôi phục sau khi hàm hoàn thành việc thực thi.
Bộ xử lý di chuyển đến điểm bắt đầu của hàm.
Các hướng dẫn bên trong hàm bắt đầu thực thi.
Sau khi các chức năng được hoàn thành, chúng được thực thi bước tiếp theo :
Các thanh ghi được khôi phục từ ngăn xếp cuộc gọi.
Khung ngăn xếp được lấy ra khỏi ngăn xếp. Bộ nhớ của tất cả các biến và đối số cục bộ được giải phóng.
Giá trị trả về được xử lý.
CPU tiếp tục thực thi mã (dựa trên địa chỉ trả về).
Giá trị trả về có thể được xử lý những cách khác, tùy thuộc vào kiến trúc máy tính. Một số kiến trúc coi giá trị trả về là một phần của khung ngăn xếp. Những người khác sử dụng thanh ghi bộ xử lý.
Biết tất cả các chi tiết về cách hoạt động của ngăn xếp cuộc gọi không phải là điều quan trọng. Tuy nhiên, việc hiểu rằng các hàm được thêm vào ngăn xếp khi được gọi và bị xóa khỏi ngăn xếp khi được gọi sẽ mang lại những điều cơ bản cần thiết để hiểu đệ quy, cũng như một số khái niệm khác hữu ích trong .
Ngăn xếp cuộc gọi ví dụ
Hãy xem xét đoạn mã sau:
Ngăn xếp cuộc gọi của chương trình này trông như thế này:
boo() (bao gồm tham số b)
chủ yếu()
Tràn ngăn xếp
Ngăn xếp có kích thước giới hạn và do đó chỉ có thể chứa một lượng thông tin hạn chế. TRONG Kích thước cửa sổ Kích thước ngăn xếp mặc định là 1 MB. Trên một số hệ thống Unix khác, kích thước này có thể đạt tới 8 MB. Nếu một chương trình cố gắng đẩy quá nhiều thông tin vào ngăn xếp, nó sẽ dẫn đến tình trạng tràn ngăn xếp. Tràn ngăn xếp(tràn ngăn xếp) xảy ra khi một yêu cầu bộ nhớ xảy ra khi tất cả bộ nhớ ngăn xếp đã được cấp phát - trong trường hợp này, tất cả các yêu cầu cấp phát sẽ bắt đầu chuyển (tràn) sang các phần bộ nhớ khác.
Tràn ngăn xếp là kết quả của việc thêm quá nhiều biến vào ngăn xếp và/hoặc tạo quá nhiều số lượng lớn các lệnh gọi hàm lồng nhau (ví dụ: trong đó hàm A gọi hàm B, hàm này gọi hàm B, hàm này gọi hàm C, hàm này gọi hàm D, v.v.). Tràn ngăn xếp thường khiến chương trình bị lỗi.
Ví dụ:
int main() ( int stack; return 0; )
int chính() ngăn xếp int [ 100000000 ] ; trả về 0; |
Chương trình này đang cố gắng thêm một mảng lớn vào ngăn xếp cuộc gọi. Vì kích thước ngăn xếp không đủ để xử lý một mảng như vậy nên phần bổ sung của nó sẽ chuyển sang các phần khác của bộ nhớ mà chương trình không thể sử dụng. Vì vậy, chúng tôi nhận được một thất bại.
Đây là một chương trình khác có thể gây tràn ngăn xếp nhưng vì một lý do khác:
void boo() ( boo(); ) int main() ( boo(); return 0; )
