Ngăn xếp trong lập trình là gì  Ngăn xếp là gì? Ngăn xếp kích thước cố định được xây dựng trên một mảng

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 tới giá trị - đây là các cấp độ máy và ngôn ngữ bằng cấp 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 đổi ý 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ớ là những khối xây dựng chính của 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 tính 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ề. Thiết lập cơ chế gọi giá trị không cần ngăn xếp là công việc làm thêm, 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 kiểu trừu tượng dữ liệu, 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 xuống dưới, 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 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. Điều này rất có thể 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”).

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 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ề 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 con trỏ mới q kiểu cấu trúc comp. Trên thực tế, đây là phần tử mới q = new comp(); // cấp phát bộ nhớ cho phần tử mới q->Data = D; //Viết số cần tìm vào phần tử Data if (top == NULL) ( //Nếu không có đỉnh, tức 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 phần trên cùng bây giờ là 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 việc xem xét 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à đặ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 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 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 ở phía 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 cho 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 đó chúng ta xóa 4, ngăn xếp kết thúc bằng 5321 printf_s("\n");//chuyển sang dòng mới s_print(top);//hệ thống đầu ra("tạm dừng");//tạm dừ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ỏ lên trên cùng vào hàm, thì “Ngăn xếp” sẽ chỉ được tạo và thay đổi bên trong hàm, theo chức năng chínhđầu vẫn 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 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.

Thẻ: Thêm thẻ

Ngăn xếp là một tập hợp mà các phần tử của nó được lấy theo nguyên tắc nhập sau, xuất trước. (Vào sau xuất trước hoặc LIFO). Điều này có nghĩa là chúng ta sẽ chỉ có quyền truy cập vào phần tử được thêm vào cuối cùng.

Không giống như danh sách, chúng ta không thể truy cập một phần tử tùy ý của ngăn xếp. Chúng ta chỉ có thể thêm hoặc xóa các phần tử bằng cách sử dụng phương pháp đặc biệt. Ngăn xếp cũng không có phương thức Chứa như danh sách. Ngoài ra, ngăn xếp không có vòng lặp. Để hiểu tại sao những hạn chế như vậy lại được đặt trên ngăn xếp, hãy xem cách nó hoạt động và cách sử dụng nó.

Sự tương tự phổ biến nhất để giải thích một chồng là một chồng đĩa. Bất kể có bao nhiêu tấm trong ngăn xếp, chúng ta luôn có thể loại bỏ tấm trên cùng. Các đĩa sạch được đặt lên trên cùng của chồng theo cách tương tự và chúng tôi sẽ luôn lấy đĩa được đặt cuối cùng lên đầu tiên.

Ví dụ: nếu chúng ta đặt một tấm màu đỏ, sau đó là tấm màu xanh lam, rồi đến tấm màu xanh lá cây, thì trước tiên chúng ta sẽ cần loại bỏ tấm màu xanh lá cây, sau đó là tấm màu xanh lam và cuối cùng là tấm màu đỏ. Điều chính cần nhớ là các đĩa luôn được đặt ở trên cùng của ngăn xếp. Khi ai đó lấy một cái đĩa, họ cũng lấy nó ra khỏi đầu. Hóa ra các tấm được tháo rời theo thứ tự ngược lại với thứ tự chúng được đặt.

Bây giờ chúng ta đã hiểu cách hoạt động của ngăn xếp, hãy giới thiệu một số thuật ngữ. Hoạt động thêm một phần tử vào ngăn xếp được gọi là “đẩy” và xóa phần tử đó được gọi là “pop”. Phần tử cuối cùng được thêm vào được gọi là phần trên cùng của ngăn xếp hoặc "trên cùng" và có thể được xem bằng thao tác "nhìn trộm". Bây giờ chúng ta hãy xem mẫu của một lớp triển khai ngăn xếp.

Lớp ngăn xếp

Lớp Stack xác định các phương thức Push, Pop, Peek để truy cập các phần tử và trường Count. Trong quá trình triển khai chúng tôi sẽ sử dụng LinkedList để lưu trữ các phần tử.

Ngăn xếp lớp công khai ( LinkedList _items = new LinkedList(); public void Push(T value) ( ​​​​throw new NotImplementedException(); ) public T Pop() ( ném new NotImplementedException(); ) public T Peek() ( ném mới NotImplementedException( ); int công khai ( get ; ) )

Phương pháp đẩy

• Hành vi: Thêm một phần tử vào đầu ngăn xếp.
• Độ phức tạp: O(1).

Vì chúng ta đang sử dụng danh sách liên kết để lưu trữ các phần tử nên chúng ta chỉ cần thêm một phần tử mới vào cuối danh sách.

Công khai void Push(T value) ( ​​_items.AddLast(value); )

Phương pháp bật lên

• Hành vi: Loại bỏ một phần tử ở đầu ngăn xếp và trả về phần tử đó. Nếu ngăn xếp trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Push thêm các phần tử vào cuối danh sách, do đó nó cũng sẽ lấy chúng từ cuối. Nếu danh sách trống, một ngoại lệ sẽ được đưa ra.

Public T Pop() ( if (_items.Count == 0) ( ném new InvalidOperationException("Ngăn xếp trống"); ) T result = _items.Tail.Value; _items.RemoveLast(); kết quả trả về; )

Phương pháp nhìn trộm

• Hành vi: Trả về phần tử trên cùng của ngăn xếp nhưng không xóa nó. Nếu ngăn xếp trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp đếm

• Hành vi: Trả về số phần tử trong ngăn xếp.
• Độ phức tạp: O(1).

Tại sao chúng ta cần biết có bao nhiêu phần tử trong ngăn xếp nếu chúng ta không có quyền truy cập vào chúng? Với trường này, chúng ta có thể kiểm tra xem có phần tử nào trên ngăn xếp hay nó trống. Điều này rất hữu ích vì phương thức Pop đưa ra một ngoại lệ.

Ví dụ: máy tính viết bằng ký hiệu Ba Lan ngược.

Một ví dụ cổ điển về việc sử dụng ngăn xếp là một máy tính bằng ký hiệu tiếng Ba Lan ngược hoặc hậu tố. Trong đó toán tử được viết sau đó toán hạng của chúng. Đó là, chúng tôi viết:

<операнд> <операнд> <оператор>

thay vì cách truyền thống:

<операнд> <оператор> <операнд>

Nói cách khác, thay vì “4 + 2” chúng ta sẽ viết “4 2 +”. Nếu bạn quan tâm đến nguồn gốc của ký hiệu tiếng Ba Lan ngược và tên của nó, bạn có thể tìm hiểu về nó trên Wikipedia hoặc trên một công cụ tìm kiếm.

Cách tính nghịch đảo nhập cảnh Ba Lan và tại sao ngăn xếp lại hữu ích khi sử dụng nó có thể được thấy rõ từ thuật toán sau:

Đối với mỗi giá trị đầu vào nếu giá trị là số nguyên, đẩy giá trị đó vào ngăn toán hạng, nếu giá trị là toán tử bật cái giá trị trái và phải từ ngăn xếp đánh giá toán tử đẩy kết quả vào ngăn xếp bật câu trả lời từ ngăn xếp.

Nghĩa là, đối với biểu thức “4 2 +”, các hành động sẽ như sau:

Đẩy(4) đẩy(2) đẩy(pop() + pop())

Cuối cùng sẽ có một giá trị trên ngăn xếp - 6.

Sau đây là mã đầy đủ máy tính đơn giản, đọc một biểu thức (ví dụ: 4 2 +) từ bảng điều khiển, phân tách đầu vào theo dấu cách (["4", "2", "+"]) và thực hiện thuật toán tính toán. Việc đánh giá tiếp tục cho đến khi gặp từ thoát.

Void RpnLoop() ( while (true) ( ​​​Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) // Ngăn xếp các giá trị chưa được xử lý. Giá trị ngăn xếp = new Stack(); foreach (string token in input. Split(new char (" " )) ( // Nếu giá trị là số nguyên... int value; if (int. TryParse(token, out value)) ( // ... đặt nó vào ngăn xếp. value.Push(value); ) else ( // nếu không thì thực hiện thao tác... int rhs = value .Pop(); int lhs = value.Pop(); // ... và đặt kết quả trở lại switch (token) ( case "+": value.Push(lhs + rhs); break; case "-" : value.Push(lhs - rhs ); break; case "*": value.Push(lhs * rhs); case "/": value.Push(lhs / rhs); Nếu thao tác không +, -, * hoặc / ném new ArgumentException(string.Format("Unrecognized token: (0)", token) ) ) // Phần tử cuối cùng trên ngăn xếp là kết quả. .Nhạc pop()); ) )

Xếp hàng

Hàng đợi rất giống với ngăn xếp. Chúng cũng không cấp quyền truy cập vào một phần tử tùy ý, nhưng không giống như ngăn xếp, các phần tử được xếp chồng lên nhau (xếp hàng) và leo lên (dequeue) từ các đầu khác nhau. Phương pháp này được gọi là “nhập trước, xuất trước” (Nhập trước xuất trước hoặc FIFO). Tức là chúng ta sẽ lấy các phần tử từ hàng đợi theo thứ tự như chúng ta đặt chúng. Giống như một hàng đợi hoặc băng tải thực sự.

Hàng đợi thường được sử dụng trong các chương trình để cung cấp một vùng đệm trong đó một phần tử có thể được đặt vào để xử lý sau này, giữ nguyên thứ tự mà nó đến. Ví dụ: nếu cơ sở dữ liệu chỉ hỗ trợ một kết nối, bạn có thể sử dụng một hàng các luồng, kỳ lạ thay, sẽ đợi đến lượt chúng để truy cập cơ sở dữ liệu.

Lớp xếp hàng

Lớp Hàng đợi, giống như ngăn xếp, sẽ được triển khai bằng danh sách liên kết. Nó sẽ cung cấp Enqueue để thêm một phần tử, Dequeue để xóa, các phương thức Peek và Count. Giống như lớp Stack, nó sẽ không triển khai giao diện ICollection , vì đây là những bộ sưu tập có mục đích đặc biệt.

Hàng đợi lớp công khai ( LinkedList _items = new LinkedList(); public void Enqueue(T value) ( ​​​throw new NotImplementedException(); ) public T Dequeue() ( ném new NotImplementedException(); ) public T Peek() ( ném mới NotImplementedException( ); int công khai ( get ; ) )

Phương pháp xếp hàng

• Hành vi: Thêm một phần tử vào hàng đợi.
• Độ phức tạp: O(1).

Các phần tử hàng đợi mới có thể được thêm vào đầu hoặc cuối danh sách. Điều quan trọng là các phần tử được tiếp cận từ cạnh đối diện. Trong quá trình triển khai này, chúng tôi sẽ thêm các phần tử mới vào đầu danh sách nội bộ.

Public void Enqueue(T value) ( ​​_items.AddFirst(value); )

Phương thức xếp hàng

• Hành vi: Loại bỏ phần tử được đặt đầu tiên khỏi hàng đợi và trả về nó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Vì chúng tôi đang chèn các phần tử vào đầu danh sách nên chúng tôi sẽ xóa chúng khỏi cuối danh sách. Nếu danh sách trống, một ngoại lệ sẽ được đưa ra.

Public T Dequeue() ( if (_items.Count == 0) ( Throw new InvalidOperationException("Hàng đợi trống"); ) T Last = _items.Tail.Value; _items.RemoveLast(); return Last; )

Phương pháp nhìn trộm

• Hành vi: Trả về phần tử sẽ được trả về trong lệnh gọi tiếp theo tới phương thức Dequeue. Hàng đợi vẫn không thay đổi. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp đếm

• Hành vi:
• Độ phức tạp: O(1).

Hàng đợi hai chiều

Hàng đợi hai chiều (Hàng đợi hai đầu), hoặc tháng 12 (Deque), mở rộng hành vi của hàng đợi. Trong deque, bạn có thể thêm hoặc xóa các phần tử ở cả đầu và cuối hàng đợi. Hành vi này hữu ích trong nhiều tác vụ, chẳng hạn như lập lịch các luồng hoặc triển khai các cấu trúc dữ liệu khác. Sau này chúng ta sẽ xem xét việc triển khai ngăn xếp bằng cách sử dụng deque.

lớp deque

Lớp Deque dễ triển khai nhất bằng cách sử dụng danh sách liên kết đôi. Nó cho phép bạn xem, xóa và thêm các phần tử vào đầu và cuối danh sách. Sự khác biệt chính giữa hàng đợi hai chiều và hàng đợi thông thường là các phương thức Enqueue, Dequeue và Peek được chia thành từng cặp để hoạt động ở cả hai đầu của danh sách.

Lớp công khai Deque ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) ( ​​​throw new NotImplementedException(); ) public void EnqueueLast(T value) ( ​​​​ném NotImplementedException(); ) public T DequeueFirst( ) ( ném NotImplementedException mới(); ) công khai T DequeueLast() ( ném NotImplementedException mới(); ) công khai T PeekFirst() ( ném NotImplementedException mới(); ) công khai T PeekLast() ( ném NotImplementedException mới(); ) công khai int Đếm ( được; ) )

Phương pháp EnqueueFirst

• Hành vi:
• Độ phức tạp: O(1).

EnqueuePhương pháp cuối cùng

• Hành vi:
• Độ phức tạp: O(1).

Phương thức DequeueFirst

• Hành vi: Loại bỏ một phần tử khỏi đầu hàng đợi và trả về phần tử đó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương thức DequeueLast

• Hành vi:
• Độ phức tạp: O(1).

Phương pháp PeekFirst

• Hành vi: Trả về một phần tử từ đầu hàng đợi mà không sửa đổi nó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp PeekLast

• Hành vi:
• Độ phức tạp: O(1).

Phương pháp đếm

• Hành vi: Trả về số phần tử trong hàng đợi hoặc 0 nếu hàng đợi trống.
• Độ phức tạp: O(1).

Ví dụ: Triển khai ngăn xếp

Deque thường được sử dụng để triển khai các cấu trúc dữ liệu khác. Hãy xem một ví dụ về cách triển khai ngăn xếp bằng cách sử dụng nó.

Bạn có thể thắc mắc tại sao triển khai ngăn xếp dựa trên hàng đợi thay vì danh sách liên kết. Có hai lý do: hiệu suất và tái sử dụng mã số. Danh sách liên kết có chi phí tạo nút và không có sự đảm bảo về vị trí dữ liệu: các phần tử có thể được đặt ở bất kỳ đâu trong bộ nhớ, điều này gây ra một số lượng lớn lỗi và suy giảm hiệu suất ở cấp độ bộ xử lý. Việc triển khai hàng đợi song công hiệu quả hơn đòi hỏi một mảng để lưu trữ các phần tử.

Tuy nhiên, việc triển khai một ngăn xếp hoặc hàng đợi bằng cách sử dụng một mảng là một nhiệm vụ không hề dễ dàng, nhưng việc triển khai deque theo cách này và sử dụng nó làm cơ sở cho các cấu trúc dữ liệu khác sẽ mang lại cho chúng ta những lợi ích đáng kể về hiệu suất và cho phép chúng ta sử dụng lại mã. Điều này làm giảm chi phí hỗ trợ.

Chúng ta sẽ xem xét một biến thể của hàng đợi sử dụng mảng sau, nhưng trước tiên hãy xem xét lớp ngăn xếp bằng cách sử dụng dequeue:

Ngăn xếp lớp công khai ( Deque _items = new Deque(); public void Push(T value) ( ​​_items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items .PeekFirst(); public int Count ( get ( return _items.Count; ) ) )

Lưu ý rằng tất cả việc xử lý lỗi hiện được xử lý bởi lớp Deque và ngoài ra, mọi tối ưu hóa hàng đợi cũng sẽ được phản ánh trên ngăn xếp. Việc triển khai hàng đợi khứ hồi thông thường đơn giản đến mức chúng tôi coi nó như một bài tập dành cho người đọc.

Lưu trữ các phần tử trong một mảng

Như đã đề cập, việc triển khai hàng đợi bằng mảng có những ưu điểm của nó. Trông có vẻ đơn giản nhưng trên thực tế có một số sắc thái cần được tính đến.

Hãy xem xét các vấn đề có thể phát sinh và cách giải quyết chúng. Ngoài ra, chúng ta sẽ cần thông tin về việc tăng mảng bên trong từ bài viết trước về mảng động.

Khi một hàng đợi được tạo, một mảng có độ dài bằng 0 sẽ được tạo bên trong nó. Các chữ cái màu đỏ "h" và "t" tương ứng là các con trỏ _head và _tail.

Deque deq = Deque mới(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Xin lưu ý: chỉ mục của “đầu” hàng đợi đã nhảy lên đầu danh sách. Bây giờ phần tử đầu tiên sẽ được trả về khi gọi phương thức DequeueFirst là 0 (chỉ mục 3).

Deq.EnqueueLast(3);

Mảng đã đầy nên khi thêm một phần tử sẽ xảy ra hiện tượng sau:

• Thuật toán tăng trưởng sẽ xác định kích thước của mảng mới.
• Các phần tử sẽ được sao chép vào mảng mới từ đầu đến đuôi.
• Một yếu tố mới sẽ được thêm vào.

Bây giờ hãy xem điều gì xảy ra khi một phần tử bị xóa:

Deq.DequeueFirst();

Deq.DequeueLast();

Thời điểm quan trọng: bất kể dung lượng hay độ đầy của mảng bên trong, về mặt logic, nội dung của hàng đợi là các phần tử từ “đầu” đến “đuôi”, có tính đến “tính tuần hoàn”. Hành vi này còn được gọi là "bộ đệm vòng".

Bây giờ chúng ta hãy nhìn vào việc thực hiện.

lớp deque (dùng mảng)

Giao diện của hàng đợi dựa trên mảng giống như trong trường hợp triển khai danh sách liên kết. Chúng tôi sẽ không lặp lại nó. Tuy nhiên, vì danh sách đã được thay thế bằng một mảng nên chúng tôi đã thêm các trường mới - chính mảng đó, kích thước của nó và các con trỏ tới “đuôi” và “đầu” của hàng đợi.

Lớp công khai Deque ( T _items = new T; // Số phần tử trong hàng đợi. int _size = 0; // Chỉ mục của phần tử đầu tiên (cũ nhất). int _head = 0; // Chỉ mục của phần tử cuối cùng (mới nhất) . int _tail = -1; )

Thuật toán tăng trưởng

Khi nơi miễn phíở phần cuối của mảng bên trong, nó cần được tăng lên, các phần tử được sao chép và các con trỏ tới “đuôi” và “đầu” được cập nhật. Thao tác này được thực hiện nếu cần thiết trong khi thêm một phần tử. Tham số startedIndex được sử dụng để cho biết có bao nhiêu trường nên để trống ở đầu (trong trường hợp thêm vào đầu).

Lưu ý cách lấy dữ liệu khi bạn phải nhảy về đầu mảng khi đi từ đầu đến đuôi.

Private void phân bổNewArray(int startedIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) ( int targetIndex = startedIndex; // Sao chép nội dung... // Nếu mảng không lặp, chỉ cần sao chép các phần tử // Ngược lại, sao chép từ đầu đến cuối, sau đó từ đầu mảng đến đuôi // Nếu đuôi nhỏ hơn đầu thì chuyển về đầu. (_đuôi.< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }

Phương pháp EnqueueFirst

• Hành vi: Thêm một phần tử vào đầu hàng đợi. Phần tử này sẽ được lấy từ hàng đợi tiếp theo khi phương thức DequeueFirst được gọi.
• Độ phức tạp:

EnqueuePhương pháp cuối cùng

• Hành vi: Thêm một phần tử vào cuối hàng đợi. Phần tử này sẽ được lấy từ hàng đợi tiếp theo khi phương thức DequeueLast được gọi.
• Độ phức tạp: O(1) trong hầu hết các trường hợp; O(n) khi cần mở rộng mảng.

Phương thức DequeueFirst

• Hành vi: Loại bỏ một phần tử khỏi đầu hàng đợi và trả về phần tử đó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương thức DequeueLast

• Hành vi: Loại bỏ một phần tử ở cuối hàng đợi và trả về phần tử đó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp PeekFirst

• Hành vi: Trả về phần tử từ đầu hàng đợi mà không thay đổi phần tử đó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp PeekLast

• Hành vi: Trả về một phần tử ở cuối hàng đợi mà không sửa đổi nó. Nếu hàng đợi trống, sẽ ném ra ngoại lệ InvalidOperationException.
• Độ phức tạp: O(1).

Phương pháp đếm

• Hành vi: Trả về số phần tử trong hàng đợi hoặc 0 nếu hàng đợi trống.
• Độ phức tạp: O(1).

Còn tiếp

Bây giờ chúng ta đã hoàn thành phần thứ tư của loạt bài viết của mình. Trong đó chúng tôi đã xem xét các ngăn xếp và hàng đợi. Lần tới chúng ta sẽ chuyển sang cây tìm kiếm nhị phâ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 bạn sử dụng toán tử mới để phân bổ bộ nhớ động, bộ nhớ đó sẽ được phân bổ trong phân đoạn heap riêng của ứ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 . Bây giờ chúng ta không cần phải lo lắng về cơ chế lưu trữ và phân bổ bộ nhớ trống. 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 lớp 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 một chuỗi ngắn hiển thị cách hoạt động của việc thêm và xóa trên ngăn xếp:

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 tôi lấy một mục ra khỏi ngăn xếp, chúng tôi di chuyển nhãn dán xuống một hộp thư và xóa mục đó khỏi 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 một ứng dụng khởi động, hàm main() sẽ được hệ điều hành đẩy lên ngăn xếp cuộc gọi. 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 là 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 (một phần nhỏ bộ nhớ trong CPU) được 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 được thực thi.

Sau khi chức năng hoàn thành, các bước sau được thực hiện:

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ề).

Các giá trị trả về có thể được xử lý theo nhiều cách khác nhau, 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ế. Trên Windows, 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ẽ gây ra 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 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 C, hàm này gọi hàm D, v.v., và vân vân.). 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; )

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; )

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.

Trong một số ngôn ngữ (ví dụ: Lisp, Python), bất kỳ danh sách nào cũng có thể được gọi là ngăn xếp vì chúng có sẵn các thao tác bật và đẩy. Trong C++, thư viện chuẩn có một lớp với cấu trúc và phương thức được triển khai. Vân vân.

YouTube bách khoa toàn thư

1 / 3

Khoa học máy tính. Cấu trúc dữ liệu: Ngăn xếp. Trung tâm học tập trực tuyến Foxford

#9. Ngăn xếp / 1. Trình biên dịch và thủ tục / Lập trình từ đầu

Cơ bản về mạng dữ liệu. Mô hình OSI và ngăn xếp giao thức TCP IP. Cơ bản về Ethernet.

phụ đề

ngăn xếp phần mềm

Tổ chức trong bộ nhớ

Thông thường, ngăn xếp được triển khai dưới dạng danh sách một chiều (mỗi phần tử trong danh sách, ngoài thông tin được lưu trữ trong ngăn xếp, còn chứa một con trỏ tới phần tử tiếp theo của ngăn xếp).

Nhưng ngăn xếp cũng thường được đặt trong mảng một chiều với các địa chỉ được sắp xếp. Việc tổ chức ngăn xếp này thuận tiện nếu một phần tử thông tin chiếm một số từ cố định trong bộ nhớ, chẳng hạn như 1 từ. Điều này giúp loại bỏ nhu cầu lưu trữ một con trỏ rõ ràng tới phần tử ngăn xếp tiếp theo trong phần tử ngăn xếp, giúp tiết kiệm bộ nhớ. Trong trường hợp này, con trỏ ngăn xếp ( Con trỏ ngăn xếp, - SP) thường là một thanh ghi bộ xử lý và trỏ đến địa chỉ phần đầu của ngăn xếp.

Ví dụ: giả sử phần đầu của ngăn xếp được đặt ở địa chỉ thấp hơn, các phần tử sau được đặt ở địa chỉ tăng dần. Mỗi lần một từ được đẩy vào ngăn xếp, SP đầu tiên sẽ giảm đi 1 và sau đó địa chỉ từ SP được ghi vào bộ nhớ. Mỗi khi một từ được lấy ra khỏi ngăn xếp, đầu tiên nó sẽ đọc địa chỉ hiện tại từ SP và sau đó tăng nội dung của SP lên 1.

Khi tổ chức ngăn xếp dưới dạng danh sách một chiều, giá trị của biến ngăn xếp là một con trỏ tới đỉnh của nó - địa chỉ của đỉnh. Nếu ngăn xếp trống thì giá trị con trỏ là NULL.

Một ví dụ về triển khai ngăn xếp trong C:

ngăn xếp cấu trúc (char * data; struct stack * next; );

Hoạt động ngăn xếp

Có ba thao tác có thể thực hiện được trên ngăn xếp: thêm phần tử (còn gọi là đẩy), xóa phần tử (pop) và đọc phần tử đầu (peek).

Khi đẩy (push) một phần tử mới được thêm vào, trỏ tới phần tử trước đó là phần đầu. Phần tử mới bây giờ trở thành phần tử đầu.

Khi xóa một phần tử (pop), phần tử đầu tiên sẽ bị xóa và phần tử đầu trở thành phần tử mà đối tượng này có con trỏ (phần tử tiếp theo). Trong trường hợp này, giá trị của phần tử bị loại bỏ sẽ được trả về.

đẩy khoảng trống (STACK * ps, int x) // Thêm một phần tử mới vào ngăn xếp( if ( ps -> size == STACKSIZE ) // Ngăn xếp có bị tràn không?( fputs ("Lỗi: tràn ngăn xếp \n " , stderr ); hủy bỏ (; ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Xóa khỏi ngăn xếp( nếu ( ps -> kích thước == 0 ) // Ngăn xếp có trống không?( fputs ("Lỗi: ngăn xếp tràn \n " , stderr ); hủy bỏ (; ) else ( return ps -> items [ -- ps -> size ]; ) )

Khu vực ứng dụng

Chế độ xem lập trình của ngăn xếp được sử dụng để duyệt qua các cấu trúc dữ liệu, chẳng hạn như cây hoặc biểu đồ. Khi sử dụng các hàm đệ quy, một ngăn xếp cũng sẽ được sử dụng nhưng ở dạng phần cứng. Ngoài những mục đích này, ngăn xếp còn được sử dụng để tổ chức

Các quá trình tương tự xảy ra khi ngắt phần cứng (bộ xử lý X86 tự động lưu thanh ghi cờ trên ngăn xếp trong khi ngắt phần cứng). Ngoài ra, trình biên dịch đặt các biến cục bộ của thủ tục vào ngăn xếp (nếu bộ xử lý có quyền truy cập vào một vị trí ngăn xếp ngẫu nhiên).

Trước khi có thể sử dụng ngăn xếp, nó phải được khởi tạo để các thanh ghi SS:ESP trỏ đến địa chỉ của đầu ngăn xếp trong vùng vật lý. bộ nhớ truy cập tạm thời và để lưu trữ dữ liệu trong ngăn xếp cần phải dự trữ số lượng ô nhớ cần thiết (rõ ràng là ngăn xếp trong ROM đương nhiên không thể tổ chức được). Chương trình ứng dụng, theo quy định, một ngăn xếp sẵn sàng sử dụng được lấy từ hệ điều hành. Trong chế độ bộ xử lý được bảo vệ, phân đoạn trạng thái tác vụ chứa bốn bộ chọn phân đoạn ngăn xếp (dành cho các cấp đặc quyền khác nhau), nhưng mỗi lần chỉ sử dụng một ngăn xếp.