DOUG LLOYD: Tất cả các quyền, vậy bởi thời điểm này bạn có lẽ khá quen thuộc với mảng và danh sách liên kết đó là hai chính cấu trúc dữ liệu, chúng tôi đã nói về việc giữ cho bộ dữ liệu của các kiểu dữ liệu tương tự tổ chức. Bây giờ chúng ta sẽ nói chuyện về một vài biến thể về mảng và danh sách liên kết. Trong video này, chúng ta sẽ để nói về ngăn xếp. Cụ thể chúng ta sẽ nói chuyện về một cấu trúc dữ liệu gọi là stack. Nhớ lại từ các cuộc thảo luận trước đó về con trỏ và bộ nhớ, rằng ngăn xếp cũng là đặt tên cho một đoạn bộ nhớ nơi khai báo tĩnh bộ nhớ memory-- bạn tên, biến mà bạn đặt tên, et cetera và chức năng khung hình mà chúng tôi cũng khung stack gọi tồn tại. Vì vậy, đây là một cấu trúc ngăn xếp dữ liệu không phải là một đoạn ngăn xếp bộ nhớ. ĐƯỢC. 

Nhưng một chồng là gì? Vì vậy, nó là khá nhiều chỉ là một loại đặc biệt của cấu trúc duy trì dữ liệu trong một cách có tổ chức. Và có hai rất cách phổ biến để thực hiện ngăn xếp bằng cách sử dụng hai cấu trúc dữ liệu mà chúng ta đã quen thuộc với, mảng và danh sách liên kết. Điều gì làm cho một chồng đặc biệt là các cách thức mà chúng tôi đưa thông tin thành đống, và cách chúng ta loại bỏ các thông tin từ các stack. Đặc biệt với ngăn xếp các quy tắc chỉ là nhất Gần đây yếu tố bổ sung có thể được gỡ bỏ. 

Vì vậy, suy nghĩ về nó như thể nó là một chồng. Chúng tôi đang chất đống thông tin trên bản thân nó, và chỉ có điều ở đầu của cọc có thể được gỡ bỏ. Chúng ta không thể loại bỏ các điều bên dưới bởi vì tất cả mọi thứ khác sẽ sụp đổ và rơi trên. Vì vậy, chúng tôi thực sự đang xây dựng một chồng mà sau đó chúng ta phải loại bỏ từng mảnh. Bởi vì điều này chúng ta thường gọi để một chồng như một cấu trúc LIFO, kéo vào, ra đầu tiên. LIFO, kéo vào, đầu ra. 

Vì vậy, do sự hạn chế này trên làm thế nào thông tin có thể được thêm vào và lấy ra từ một chồng, có thực sự chỉ có hai điều chúng ta có thể làm với một chồng. Chúng tôi có thể thúc đẩy, đó là hạn, chúng tôi sử dụng cho việc thêm một nguyên tố mới cho phần trên của ngăn xếp, hoặc nếu chồng không tồn tại và chúng tôi đang tạo ra nó từ đầu, tạo ra các ngăn xếp ở vị trí đầu tiên sẽ đẩy. Và sau đó bật, đó là loại của CS hạn chúng tôi sử dụng để loại bỏ gần đây nhất thêm phần tử từ đỉnh của ngăn xếp. 

Vì vậy, chúng ta sẽ xem xét ở cả hai triển khai thực hiện, cả hai mảng dựa và danh sách liên kết dựa. Và chúng ta sẽ bắt đầu với mảng dựa. Vì vậy, đây là ý tưởng cơ bản của những gì mảng dựa trên cấu trúc ngăn xếp dữ liệu sẽ như thế nào. Chúng tôi có một định nghĩa gõ ở đây. Bên trong của chúng ta có hai thành viên hoặc các lĩnh vực của cấu trúc. Chúng tôi có một mảng. Và một lần nữa tôi đang sử dụng giá trị kiểu dữ liệu tùy ý. 

Vì vậy, đây có thể là bất kỳ kiểu dữ liệu, int char hoặc một số dữ liệu khác gõ mà bạn đã tạo trước đó. Vì vậy, chúng tôi có một loạt các khả năng kích thước. Công suất được định nghĩa một bảng liên tục, có lẽ ở một nơi khác trong tập tin của chúng tôi. Vì vậy, nhận thấy đã có đặc biệt này thực hiện chúng tôi đang bounding mình là là thường trường hợp với mảng, mà chúng ta có thể không tự động thay đổi kích thước, nơi có một số lượng nhất định các yếu tố tối đa mà chúng ta có thể đặt trong ngăn xếp của chúng tôi. Trong trường hợp này nó là yếu tố năng lực. 

Chúng tôi cũng theo dõi đỉnh của stack. Yếu tố gì là nhất gần đây đã thêm vào stack? Và vì vậy chúng tôi theo dõi mà trong một biến gọi là hàng đầu. Và tất cả những điều này được bao bọc với nhau thành một kiểu dữ liệu mới gọi là một chồng. Và một khi chúng ta được tạo kiểu dữ liệu mới này chúng ta có thể đối xử với nó như bất kỳ loại dữ liệu khác. Chúng tôi có thể tuyên bố chồng s, giống như chúng ta có thể làm int x, y hoặc char. Và khi chúng ta nói rằng chồng s, cũng những gì xảy ra là chúng ta có được một bộ bộ nhớ dành cho chúng ta. 

Trong trường hợp này công suất Tôi đã quyết định rõ ràng là 10, vì tôi đã có một biến đơn kiểu ngăn xếp trong đó có hai trường nhớ lại. Một mảng, trong trường hợp này là là một mảng các số nguyên như trường hợp ở hầu hết các ví dụ của tôi. Và biến số nguyên khác khả năng lưu trữ hàng đầu, gần đây nhất được bổ sung yếu tố để các stack. Vì vậy, một trong những đơn ngăn xếp của những gì chúng ta chỉ định trông như thế này. Đó là một hộp chứa một mảng của 10 gì sẽ là các số nguyên trong trường hợp này và một biến số nguyên có màu xanh lá cây để chỉ ra các đỉnh của ngăn xếp. 

Để thiết lập đỉnh ngăn xếp, chúng tôi chỉ nói s.top. Đó là cách chúng ta truy cập một lĩnh vực thu hồi cấu trúc. s.top bằng 0 có hiệu quả thực hiện điều này để ngăn xếp của chúng tôi. Vì vậy, một lần nữa chúng tôi có hai hoạt động rằng chúng ta có thể thực hiện ngay bây giờ. Chúng tôi có thể đẩy và chúng tôi có thể bật. Hãy bắt đầu với push. Một lần nữa, đẩy được thêm mới yếu tố để các đỉnh của ngăn xếp. 

Vì vậy, những gì chúng ta cần phải làm gì trong mảng này thực hiện dựa? Vâng trong chung đẩy chức năng sẽ cần phải chấp nhận một con trỏ vào stack. Bây giờ lấy một giây và suy nghĩ về nó. Tại sao chúng tôi muốn chấp nhận một con trỏ tới ngăn xếp? Nhớ lại từ video trước đó trên phạm vi biến và con trỏ, điều gì sẽ xảy ra nếu chúng tôi vừa gửi ngăn xếp, s thay như một tham số? Điều gì thực sự sẽ được thông qua trong đó? Hãy nhớ rằng chúng tôi đang tạo ra một bản sao khi chúng ta vượt qua nó để một chức năng trừ khi chúng ta sử dụng con trỏ. Và chức năng này đẩy nhu cầu để chấp nhận một con trỏ vào stack để chúng tôi đang thực sự thay đổi stack chúng tôi có ý định thay đổi. 

Điều push khác có lẽ cũng muốn đến chấp nhận là một thành phần dữ liệu của loại giá trị. Trong trường hợp này, một lần nữa, một số nguyên chúng ta sẽ thêm vào phía trên cùng của ngăn xếp. Vì vậy, chúng tôi đã có hai thông số của chúng tôi. Chúng ta sẽ đến bây giờ làm bên trong đẩy? Vâng, chỉ đơn giản, chúng ta chỉ cần đi thêm rằng yếu tố để các đỉnh của stack và sau đó thay đổi nơi đầu stack là, đó là chấm giá trị hàng đầu. Vì vậy, đây là những gì một chức năng kê khai push có thể trông giống như trong một mảng dựa trên việc thực hiện. 

Một lần nữa đây không phải là một quy tắc cứng và nhanh chóng mà bạn có thể thay đổi điều này và có nó thay đổi theo những cách khác nhau. Có lẽ s được tuyên bố trên toàn cầu. Và do đó, bạn thậm chí không cần để vượt qua nó như một tham số. Đây lại là chỉ một trường hợp tổng quát cho push. Và có khác nhau cách để thực hiện nó. Nhưng trong trường hợp này chúng tôi push là sẽ mất hai tham số, một con trỏ đến một chồng và một phần tử dữ liệu của loại giá trị, số nguyên trong trường hợp này. 

Vì vậy, chúng tôi tuyên bố của chúng tôi nói s.top bằng 0. Bây giờ chúng ta hãy đẩy số 28 vào ngăn xếp. Cũng có nghĩa là gì? Vâng hiện nay đỉnh của ngăn xếp là 0. Và vì vậy những gì là cơ bản sẽ xảy ra là chúng ta sẽ dính vào các số 28 thành mảng vị trí 0. Khá dễ dàng, đúng, đó là hàng đầu và bây giờ chúng tôi đang tốt để đi. Và sau đó chúng ta cần phải thay đổi những gì đỉnh của ngăn xếp sẽ được. Vì vậy mà trong thời gian tới chúng ta đẩy một phần tử trong, chúng ta sẽ lưu nó trong vị trí mảng, có lẽ không phải là 0. Chúng tôi không muốn ghi đè lên những gì chúng ta chỉ cần đặt ở đó. Và vì vậy chúng tôi sẽ chỉ di chuyển trên xuống 1. Điều đó có thể làm cho tinh thần. 

Bây giờ nếu chúng ta muốn đặt một yếu tố khác vào ngăn xếp, nói chúng tôi muốn đẩy 33, cũng bây giờ chúng tôi chỉ cần đi để lấy 33 và đặt nó ở vị trí số mảng 1, và sau đó thay đổi các đầu của chúng tôi ngăn xếp được mảng vị trí số hai. Vì vậy, nếu thời gian tới, chúng tôi muốn đẩy một phần tử vào stack, nó sẽ được đặt ở vị trí 2 mảng. Và chúng ta hãy làm điều đó một lần nữa. Chúng tôi sẽ đẩy 19 off của ngăn xếp. Chúng tôi sẽ đưa 19 trong mảng vị trí 2 và thay đổi trên của ngăn xếp của chúng tôi là mảng vị trí 3 vì vậy nếu thời gian chúng tôi bên cạnh cần phải thực hiện một sự thúc đẩy chúng tôi đang tốt để đi. 

OK, vì vậy đó là đẩy một cách ngắn gọn. Những gì về popping? Vì vậy, popping là loại đối ứng để đẩy. Đó là cách chúng tôi loại bỏ dữ liệu từ stack. Và trong nhu cầu pop nói chung làm như sau. Nó cần phải chấp nhận một con trỏ đến ngăn xếp, một lần nữa trong trường hợp tổng quát. Trong một số trường hợp khác có lẽ bạn đã tuyên bố stack trên toàn cầu, trong trường hợp này bạn không cần phải vượt qua nó tại vì nó đã có quyền truy cập vào nó như là một biến toàn cầu. Nhưng sau đó những gì mà chúng ta cần phải làm gì? Vâng, chúng tôi đã được incrementing trên cùng của ngăn xếp trong push, vì vậy chúng ta có lẽ sẽ muốn để giảm các đỉnh của stack trong pop, phải không? Và sau đó tất nhiên chúng tôi cũng sẽ muốn để trở về giá trị mà chúng ta loại bỏ. Nếu chúng ta thêm các yếu tố, chúng ta muốn để có được các yếu tố ra sau này, chúng ta có thể thực sự muốn lưu trữ chúng để chúng tôi không chỉ cần xóa chúng khỏi chồng và sau đó không làm gì với họ. Nói chung nếu chúng tôi đẩy và popping ở đây chúng tôi muốn lưu trữ này thông tin trong một cách có ý nghĩa và do đó, nó không làm cho ý nghĩa để chỉ loại bỏ nó. Vì vậy, chức năng này nên có thể trả về một giá trị cho chúng tôi. 

Vì vậy, đây là những gì một tuyên bố cho pop có thể trông giống như có ở trên cùng bên trái. Hàm này trả về dữ liệu của loại giá trị. Một lần nữa, chúng tôi đã sử dụng số nguyên trong suốt. Và nó chấp nhận một con trỏ đến một ngăn xếp như diện duy nhất của mình hoặc tham số duy nhất. Vì vậy, những gì được pop sẽ làm gì? Hãy nói rằng chúng tôi muốn bây giờ bật một yếu tố tắt của s. Vì vậy, hãy nhớ tôi đã nói rằng ngăn xếp là cuối cùng , ra trước, LIFO cấu trúc dữ liệu. Những phần tử được sắp được loại bỏ khỏi stack? Bạn có đoán 19? Bởi vì bạn muốn được quyền. 19 là yếu tố cuối cùng chúng tôi đã thêm vào ngăn xếp khi chúng tôi đã đẩy các yếu tố trên, và do đó, nó sẽ là người đầu tiên yếu tố đó được gỡ bỏ. Đó là nếu chúng ta nói 28, và sau đó chúng tôi đặt 33 trên đầu trang của nó, và chúng tôi đặt 19 trên đó. Yếu tố duy nhất chúng ta có thể cất cánh là 19. 

Bây giờ trong sơ đồ ở đây những gì tôi đã thực hiện là loại xóa 19 từ mảng. Đó không phải là thực sự những gì chúng ta sẽ làm. Chúng tôi chỉ cần đi để loại của giả vờ đó là không có. Nó vẫn còn đó trong mà vị trí bộ nhớ, nhưng chúng tôi chỉ cần đi để bỏ qua nó bằng cách thay đổi các đầu của ngăn xếp của chúng tôi từ là 3-2. Vì vậy, nếu chúng ta bây giờ đẩy một yếu tố vào ngăn xếp, nó sẽ qua viết 19. 

Nhưng chúng ta không đi qua những rắc rối xóa 19 từ stack. Chúng tôi chỉ có thể giả vờ đó là không có. Đối với mục đích của chồng nó đi nếu chúng ta thay đổi trên để được 2 thay vì 3. Tất cả các quyền, vì vậy đó là khá nhiều đó. Đó là tất cả chúng ta cần phải làm để bật một yếu tố hết. Hãy làm điều đó một lần nữa. Vì vậy, tôi đã nêu bật nó trong màu đỏ ở đây để cho thấy chúng ta đang thực hiện một cuộc gọi khác. Chúng ta sẽ làm điều tương tự. 

Vì vậy, những gì sẽ xảy ra? Vâng, chúng ta sẽ lưu 33 trong x và chúng ta sẽ thay đổi trên cùng của ngăn xếp để 1. Vì vậy, nếu chúng tôi ngay bây giờ để đẩy một phần tử vào stack mà chúng tôi sẽ làm ngay bây giờ, những gì sẽ xảy ra là chúng ta sẽ ghi đè lên mảng vị trí số 1. Vì vậy mà 33 đã được loại bỏ đằng sau đó chúng tôi chỉ giả vờ là không còn ở đó nữa, chúng ta chỉ cần đi để clobber nó và đặt 40 có thay thế. Và dĩ nhiên, kể từ khi chúng tôi thực hiện một sự thúc đẩy, chúng tôi đang đi để tăng đỉnh của stack 1-2 nên nếu chúng ta bây giờ thêm yếu tố khác nó sẽ thấy đi vào mảng vị trí số hai. 

Bây giờ là danh sách liên kết khác cách để thực hiện ngăn xếp. Và nếu định nghĩa này trên màn hình ở đây có vẻ quen thuộc với bạn, đó là vì nó trông gần chính xác như nhau, trên thực tế, nó khá nhiều là chính xác giống như một danh sách đơn lẻ liên kết, nếu bạn nhớ lại từ cuộc thảo luận của chúng ta về danh sách liên kết đơn lẻ trong một video khác. Hạn chế duy nhất ở đây là đối với chúng tôi là lập trình viên, chúng tôi không được phép chèn hoặc xóa ngẫu nhiên từ danh sách liên kết đơn lẻ mà chúng ta có thể làm được trước đây. Chỉ bây giờ chúng ta có thể chèn và xóa từ phía trước hoặc phía trên của liên kết danh sách. Đó thực sự là chỉ sự khác biệt. Đây là trường hợp một danh sách đơn lẻ liên kết. Nó chỉ có các hạn chế thay vào bản thân mình như lập trình viên thay đổi nó thành một chồng. 

Các quy tắc ở đây là phải luôn luôn duy trì một con trỏ đến đầu của một danh sách liên kết. Đây là khóa học một thường Nguyên tắc quan trọng đầu tiên. Đối với danh sách liên kết đơn lẻ anyway bạn chỉ cần một con trỏ đến đầu để có được điều đó chuỗi có thể tham khảo để mọi phần tử khác trong danh sách liên kết. Nhưng nó đặc biệt quan trọng với một chồng. Và nói chung bạn đang sẽ thực sự muốn con trỏ này là một biến toàn cầu. Nó có lẽ sẽ được dễ dàng hơn theo cách đó. Vì vậy, các chất tương tự của push và pop là gì? Bên phải. Vì vậy, một lần nữa đẩy được thêm một nguyên tố mới vào stack. Trong một danh sách liên kết đó có nghĩa là chúng ta sẽ có để tạo ra một nút mới chúng tôi sẽ thêm vào danh sách liên kết, và sau đó làm theo các bước sau cẩn thận rằng chúng tôi đã vạch ra trước đó trong danh sách liên kết đơn lẻ để thêm nó vào các chuỗi mà không phá vỡ dây chuyền và mất hoặc orphaning bất kỳ các yếu tố của danh sách liên kết. Và đó là cơ bản những gì mà ít blob của văn bản có tóm tắt. Và chúng ta hãy có một cái nhìn vào nó như là một sơ đồ. 

Vì vậy, đây là danh sách liên kết của chúng tôi. Nó đồng thời có bốn yếu tố. Và hoàn hảo hơn ở đây là của chúng tôi ngăn xếp chứa bốn yếu tố. Và hãy nói rằng bây giờ chúng tôi muốn đẩy một mục mới vào stack này. Và chúng tôi muốn đẩy một mới mục dữ liệu mà giá trị là 12. Vâng những gì chúng ta sẽ làm gì? Cũng lần đầu tiên chúng ta sẽ không gian malloc, năng động phân bổ không gian cho một nút mới. Và tất nhiên ngay lập tức sau khi chúng tôi thực hiện một cuộc gọi đến malloc chúng tôi luôn hãy chắc chắn để kiểm tra null, bởi vì nếu chúng ta có vô lại đã có một số loại vấn đề. Chúng tôi không muốn tới đích không cho rằng con trỏ hoặc bạn sẽ phải chịu một lỗi seg. Đó không phải là tốt. Vì vậy, chúng tôi đã malloced của nút. Chúng tôi sẽ giả sử chúng ta đã thành công ở đây. Chúng ta sẽ đặt 12 vào các trường dữ liệu của nút đó. Bây giờ ông có nhớ mà con trỏ của chúng tôi di chuyển tiếp theo nên chúng tôi không phá vỡ dây chuyền? Chúng tôi có một vài tùy chọn ở đây nhưng chỉ có một mà sẽ là an toàn là để thiết lập tức con trỏ bên cạnh Điểm đến đầu cũ của danh sách hoặc những gì sẽ sớm được đầu cũ của danh sách. Và bây giờ mà tất cả chúng tôi yếu tố được xích lại với nhau, chúng ta chỉ có thể di chuyển danh sách đến điểm đến cùng một nơi mà mới làm. Và bây giờ chúng tôi đã đẩy một cách hiệu quả yếu tố mới vào phía trước của stack. 

Để bật, chúng tôi chỉ muốn xóa mà yếu tố đầu tiên. Và do đó, về cơ bản những gì chúng ta phải làm ở đây, cũng chúng ta phải tìm các yếu tố thứ hai. Cuối cùng sẽ trở thành mới đầu sau khi chúng ta xóa một đầu. Vì vậy, chúng ta chỉ cần bắt đầu từ Ban đầu, di chuyển một về phía trước. Một khi chúng ta đã có một tổ chức trên một phía trước của nơi mà chúng ta hiện là chúng ta có thể xóa một cách an toàn đầu tiên và sau đó chúng ta chỉ có thể di chuyển đầu để trỏ đến những gì là kỳ thứ hai và sau đó bây giờ là lần đầu tiên sau đó nút đã bị xóa. 

Vì vậy, một lần nữa, dùng một cái nhìn vào nó như là một sơ đồ chúng tôi muốn bây giờ bật một yếu tố ra khỏi stack. vậy chúng ta làm gì? Vâng, chúng tôi đang đầu tiên sẽ tạo ra một con trỏ mới đó là đi để trỏ đến cùng một chỗ như người đứng đầu. Chúng ta sẽ di chuyển nó một vị trí về phía trước bằng cách nói trav equals TRAV tiếp theo ví dụ, hơn sẽ thúc đẩy một con trỏ trav vị trí phía trước. Bây giờ chúng ta đã có một giữ trên các yếu tố đầu tiên thông qua con trỏ được gọi là danh sách, và các Yếu tố thứ hai thông qua một con trỏ được gọi là trav, chúng ta có thể an toàn xóa mà Yếu tố đầu tiên từ stack mà không mất phần còn lại của chuỗi bởi vì chúng tôi có một cách để tham khảo đến phần tử thứ hai chuyển tiếp bằng cách của con trỏ được gọi là trav. 

Vì vậy, bây giờ chúng tôi có thể giải phóng nút đó. Chúng tôi có thể miễn phí danh sách. Và sau đó tất cả chúng ta cần làm bây giờ là di chuyển danh sách đến thời điểm đến cùng một nơi trav nào, và chúng tôi sắp xếp lại nơi chúng tôi bắt đầu trước khi chúng tôi đã đẩy 12 trên ở nơi đầu tiên, phải. Đây chính là nơi mà chúng tôi đã. Chúng tôi đã có bốn yếu tố này stack. Chúng tôi thêm một phần năm. Chúng tôi đã đẩy một phần năm yếu tố trên, và sau đó chúng tôi popped mà gần đây nhất thêm vào yếu tố quay trở lại. 

Đó là thực sự khá nhiều tất cả để có ngăn xếp. Bạn có thể thực hiện chúng như mảng. Bạn có thể thực hiện chúng như danh sách liên kết. Có, tất nhiên, khác cách để thực hiện chúng là tốt. Về cơ bản là lý do chúng ta sẽ sử dụng ngăn xếp là để duy trì dữ liệu trong một cách như vậy mà gần đây nhất được bổ sung phần tử là điều đầu tiên chúng tôi sẽ muốn quay trở lại. Tôi Doug Lloyd, đây là CS50.