DOUG LLOYD: Vì vậy, nếu bạn đã xem video trên stack, này có lẽ sẽ cảm thấy như một chút của deja vu. Đó sẽ là một khái niệm rất tương tự, chỉ với một thay đổi nhỏ trên đó. Chúng ta sẽ nói bây giờ về hàng đợi. Vì vậy, một hàng đợi, tương tự như một chồng, là một loại cấu trúc dữ liệu rằng chúng ta có thể sử dụng để duy trì dữ liệu một cách có tổ chức. Tương tự như một chồng, nó có thể được thực hiện như là một mảng hoặc một danh sách liên kết. Không giống như một chồng, các quy tắc mà chúng tôi sử dụng để xác định khi mọi thứ được thêm vào và lấy ra từ một hàng đợi là một chút khác nhau. Không giống như một chồng, mà là một cấu trúc LIFO, kéo vào, ra đầu tiên, một hàng đợi là một FIFO cấu trúc, FIFO, đầu vào, đầu ra. Bây giờ hàng đợi, bạn có thể có một tương tự để xếp hàng. Nếu bạn đã từng đứng xếp hàng tại công viên giải trí hoặc tại một ngân hàng, có sắp xếp của một sự công bằng thực hiện cơ cấu. Người đầu tiên trong đường dây Ngân hàng là người đầu tiên những người được để nói chuyện với các nhân viên giao dịch. 

Nó sẽ là sắp xếp của một chủng tộc đến phía dưới nếu cách duy nhất Bạn có để nói chuyện với các nhân viên giao dịch tại ngân hàng đã phải là người cuối cùng trong hàng. Mọi người sẽ luôn luôn muốn phải là người cuối cùng trong đường dây, và người đó đã có những người đầu tiên người đã chờ đợi một thời gian, có thể ở đó trong nhiều giờ, và giờ, và giờ trước khi chúng có cơ hội để thực sự rút tiền tại ngân hàng. Và như vậy hàng đợi được sắp xếp của các công bằng việc thực hiện cơ cấu. Nhưng điều đó không nhất thiết có nghĩa rằng ngăn xếp là một điều xấu, chỉ rằng hàng đợi là một cách khác để làm điều đó. Vì vậy, một lần nữa một hàng đợi đầu vào, đầu tiên ra, so với một chồng mà cuối cùng trong, đầu ra. Tương tự như một chồng, chúng tôi có hai hoạt động rằng chúng ta có thể thực hiện trên hàng đợi. Các tên là enqueue, đó là thêm một yếu tố mới vào cuối hàng đợi, và dequeue, đó là để loại bỏ các cổ nhất yếu tố từ phía trước của hàng đợi. Vì vậy, chúng ta sẽ thêm các yếu tố vào cuối hàng đợi, và chúng tôi sẽ loại bỏ các yếu tố từ phía trước của hàng đợi. Một lần nữa, với chồng, chúng tôi đã bổ sung thêm phần từ đỉnh của ngăn xếp và loại bỏ yếu tố từ đỉnh của ngăn xếp. Vì vậy, với enqueue, nó thêm vào cuối, loại bỏ từ phía trước. Vì vậy, điều lâu đời nhất ở trong đó luôn luôn là điều tiếp theo để đi ra nếu chúng tôi cố gắng và dequeue một cái gì đó. 

Vì vậy, một lần nữa, với hàng đợi, chúng ta có thể triển khai mảng dựa trên và danh sách liên kết triển khai dựa. Chúng tôi sẽ bắt đầu lại với triển khai mảng dựa trên. Định nghĩa cấu trúc trông khá tương tự. Chúng tôi có một mảng khác có giá trị kiểu dữ liệu, do đó, nó có thể chứa các loại dữ liệu tùy ý. Chúng tôi một lần nữa đi vào sử dụng số nguyên trong ví dụ này. 

Và cũng như với chúng tôi mảng dựa trên ngăn xếp thực hiện, bởi vì chúng ta đang sử dụng một mảng, chúng ta nhất thiết có giới hạn đó mà loại C của thực thi trên chúng ta, đó là chúng ta không có bất kỳ năng động trong chúng tôi khả năng phát triển và co mảng. Chúng tôi phải quyết định ngay từ đầu số lượng tối đa của vật là gì rằng chúng ta có thể đưa vào đây hàng đợi, và trong trường hợp này, khả năng sẽ có một số bảng định nghĩa hằng số trong mã của chúng tôi. Và cho các mục đích này video, công suất sẽ là 10. 

Chúng ta cần theo dõi phía trước của hàng đợi vì vậy chúng tôi biết rằng những yếu tố chúng tôi muốn dequeue, và chúng ta cũng cần phải theo dõi một cái gì đó else-- số phần tử mà chúng tôi có trong hàng đợi của chúng tôi. Chú ý chúng tôi không theo dõi Tính đến cuối của hàng đợi, chỉ kích thước của hàng đợi. Và lý do cho rằng sẽ hy vọng trở thành một chút rõ ràng hơn trong một thời điểm. Một khi chúng ta đã hoàn thành định nghĩa kiểu này, chúng ta có một kiểu dữ liệu mới gọi là hàng đợi, mà chúng tôi có thể bây giờ khai báo các biến của kiểu dữ liệu. Và phần nào gây nhầm lẫn, tôi đã quyết định để gọi hàng đợi q này, các thư q thay vì các kiểu dữ liệu q. 

Vì vậy, đây là hàng đợi của chúng tôi. Nó là một cấu trúc. Nó chứa ba thành viên hoặc ba lĩnh vực, một mảng có kích thước NĂNG LỰC. Trong trường hợp này, NĂNG LỰC là 10. Và mảng này là sẽ giữ nguyên. Màu xanh là mặt trước của hàng đợi của chúng tôi, Yếu tố tiếp theo sẽ được gỡ bỏ, và màu đỏ sẽ được kích thước của hàng đợi, bao nhiêu yếu tố hiện đang là hiện có trong hàng đợi. Vì vậy, nếu chúng ta nói equals q.front 0, và kích thước q.size bằng 0-- chúng ta đặt số 0 vào các lĩnh vực này. Và tại thời điểm này, chúng tôi khá nhiều sẵn sàng để bắt đầu làm việc với hàng đợi của chúng tôi. 

Vì vậy, các hoạt động đầu tiên chúng ta có thể thực hiện là enqueue một cái gì đó, để thêm một yếu tố mới để cuối của hàng đợi. Vâng những gì chúng ta cần phải làm gì trong trường hợp tổng quát? Vâng chức năng này enqueue nhu cầu để chấp nhận một con trỏ vào hàng đợi của chúng tôi. Một lần nữa, nếu chúng ta đã tuyên bố hàng đợi của chúng tôi trên toàn cầu, chúng ta sẽ không cần phải làm điều này nhất thiết, nhưng nói chung, chúng tôi cần phải chấp nhận con trỏ để cấu trúc dữ liệu như thế này, bởi vì nếu không, chúng ta đang đi ngang qua value-- chúng tôi đi qua trong các bản sao của hàng đợi, và vì vậy chúng ta không thực sự thay đổi hàng đợi rằng chúng tôi có ý định thay đổi. 

Một điều khác cần làm là chấp nhận một phần tử dữ liệu của các loại thích hợp. Một lần nữa, trong trường hợp này, đó là sẽ là các số nguyên, nhưng bạn có thể tùy tiện khai báo kiểu dữ liệu như giá trị và sử dụng nói chung. Đó là những yếu tố chúng ta muốn enqueue, chúng ta muốn thêm vào cuối hàng đợi. Sau đó, chúng tôi thực sự muốn đặt dữ liệu trong hàng đợi. Trong trường hợp này, đặt nó trong đúng vị trí của mảng của chúng tôi, và sau đó chúng tôi muốn thay đổi kích thước của hàng đợi, bao nhiêu yếu tố chúng tôi hiện có. 

Vì vậy, chúng ta hãy bắt đầu. Ở đây, một lần nữa, mà nói chung khai báo hàm dạng cho những gì enqueue thể trông như thế. Và ở đây chúng tôi đi. Hãy enqueue số 28 vào hàng đợi. Vì vậy, những gì chúng ta sẽ làm gì? Vâng, mặt trước của hàng đợi của chúng tôi là 0, và kích thước của hàng đợi của chúng tôi là 0, và vì vậy chúng tôi có thể muốn đặt số 28 trong số phần tử mảng 0, phải không? Vì vậy, bây giờ chúng tôi đã đặt trong đó. Vì vậy, bây giờ những gì chúng ta cần phải thay đổi? Chúng tôi không muốn thay đổi phía trước của hàng đợi, bởi vì chúng tôi muốn biết những gì yếu tố chúng ta có thể cần phải dequeue sau. Vì vậy, lý do chúng tôi có mặt ở đó là loại một chỉ báo về những gì điều lâu đời nhất trong mảng. Vâng điều lâu đời nhất trong array-- trong Thực tế, điều duy nhất trong mảng quyền now-- là 28, đó là ở mảng vị trí 0. Vì vậy, chúng tôi không muốn thay đổi con số màu xanh lá cây, bởi vì đó là những yếu tố lâu đời nhất. Thay vào đó, chúng tôi muốn thay đổi kích thước. Vì vậy, trong trường hợp này, chúng tôi sẽ tăng kích thước đến 1. 

Bây giờ một loại chung của ý tưởng về nơi Yếu tố tiếp theo là sẽ đi trong một hàng đợi là thêm hai con số với nhau, mặt trước và kích thước, và đó sẽ cho bạn biết nơi tiếp theo phần tử trong hàng đợi là sẽ đi. Vì vậy, bây giờ hãy enqueue một số khác. Hãy enqueue 33. Vì vậy, 33 là sẽ đi vào mảng địa điểm 0 cộng với 1. Vì vậy, trong trường hợp này, nó sẽ để đi vào mảng vị trí 1, và bây giờ là kích thước của hàng đợi của chúng tôi là 2. 

Một lần nữa, chúng tôi sẽ không thay đổi mặt trước của hàng đợi của chúng tôi, vì 28 vẫn là yếu tố lâu đời nhất, và chúng tôi muốn với: khi ta sẽ nhận được để dequeuing, loại bỏ yếu tố từ hàng đợi này, chúng tôi muốn biết ở đó yếu tố lâu đời nhất là. Và vì vậy chúng tôi luôn luôn cần phải duy trì một số chỉ số về nơi đó là. Vì vậy, đó là những gì 0 là có cho. Đó là những gì phía trước là có cho. 

Hãy ở enqueue một trong nhiều yếu tố, 19. Tôi chắc rằng bạn có thể đoán nơi 19 là sẽ đi. Nó sẽ đi vào mảng vị trí số 2. Đó là 0 cộng 2. Và bây giờ là kích thước của hàng đợi của chúng tôi là 3. Chúng tôi có 3 yếu tố trong đó. Vì vậy, nếu chúng ta, và chúng ta sẽ không đến ngay bây giờ, enqueue một yếu tố khác, nó sẽ đi vào mảng vị trí số 3, và kích thước của hàng đợi của chúng tôi sẽ là 4. Vì vậy, chúng tôi đã enqueued một số yếu tố bây giờ. Bây giờ chúng ta hãy bắt đầu loại bỏ chúng. Hãy dequeue họ từ hàng đợi. 

Vì vậy, tương tự như pop, đó là loại của analog này cho ngăn xếp, dequeue cần phải chấp nhận một con trỏ đến queue-- một lần nữa, trừ khi nó được công bố trên toàn cầu. Bây giờ chúng tôi muốn thay đổi vị trí của mặt trước của hàng đợi. Đây là nơi mà nó loại đi kèm vào chơi, mà biến phía trước, bởi vì một khi chúng ta loại bỏ một phần tử, chúng ta muốn để di chuyển nó đến các yếu tố cũ nhất tiếp theo. 

Sau đó, chúng tôi muốn giảm kích thước của hàng đợi, và sau đó chúng ta muốn trả về giá trị đã được gỡ bỏ khỏi hàng đợi. Một lần nữa, chúng tôi không muốn chỉ cần loại bỏ nó. Chúng tôi có lẽ được chiết xuất nó từ queue-- chúng tôi dequeuing nó bởi vì chúng tôi quan tâm đến nó. Vì vậy, chúng tôi muốn chức năng này để trở về một phần tử dữ liệu của loại giá trị. Một lần nữa, trong trường hợp này, giá trị là số nguyên. 

Vì vậy, bây giờ hãy dequeue một cái gì đó. Hãy loại bỏ một phần tử từ hàng đợi. Nếu chúng ta nói int x = & q, ký hiệu q-- một lần nữa đó là một con trỏ đến dữ liệu q này structure-- cho yếu tố sẽ được dequeued? Trong trường hợp này, bởi vì nó là một đầu tiên trong, đầu ra cấu trúc dữ liệu, FIFO, điều đầu tiên chúng ta đưa vào đây hàng đợi là 28, và vì vậy trong trường hợp này, chúng ta sẽ mất 28 trong số hàng đợi, không phải 19, mà là những gì chúng tôi đã có thể làm nếu điều này là một chồng. Chúng ta sẽ mất 28 ra khỏi hàng đợi. 

Tương tự như những gì chúng ta đã làm với một chồng, chúng tôi không thực sự đi để xóa 28 từ hàng đợi riêng của mình, chúng tôi chỉ cần đi để loại của giả vờ đó là không có. Vì vậy, nó sẽ ở lại đó trong bộ nhớ, nhưng chúng tôi chỉ sẽ loại bỏ nó bằng cách di chuyển hai lĩnh vực khác của dữ liệu của chúng tôi q cấu trúc. Chúng ta sẽ thay đổi phía trước. Q.front bây giờ sẽ là 1, vì rằng bây giờ là các yếu tố lâu đời nhất chúng tôi có trong chúng tôi hàng đợi, bởi vì chúng tôi đã loại bỏ 28, đó là yếu tố lâu đời cũ. 

Và bây giờ, chúng tôi muốn thay đổi kích thước của hàng đợi hai yếu tố thay vì ba. Bây giờ nhớ trước đó tôi đã nói khi chúng tôi muốn thêm phần tử vào hàng đợi, chúng tôi đặt nó ở một vị trí mảng đó là tổng của mặt trước và kích thước. Vì vậy, trong trường hợp này, chúng tôi vẫn đặt nó, phần tử tiếp theo trong hàng đợi, vào mảng vị trí 3, và chúng ta sẽ thấy rằng trong một giây. 

Vì vậy, bây giờ chúng tôi đã dequeued của chúng tôi Yếu tố đầu tiên từ hàng đợi. Hãy làm điều đó một lần nữa. Hãy loại bỏ khác phần tử từ hàng đợi. Trong trường hợp, lâu đời nhất hiện nay phần tử là mảng 1 vị trí. Đó là những gì q.front nói với chúng ta. Đó là hộp màu xanh lá cây cho chúng ta biết đó là yếu tố lâu đời nhất. Và như vậy, x sẽ trở thành 33. Chúng tôi sẽ chỉ cần loại quên 33 tồn tại trong mảng, và chúng tôi sẽ nói rằng bây giờ, các yếu tố cổ nhất mới trong hàng đợi là ở mảng vị trí 2, và kích thước của hàng đợi, số lượng các yếu tố chúng tôi có trong hàng đợi, là 1. Bây giờ chúng ta hãy enqueue một cái gì đó, và tôi loại này đã cho đi một giây trước đó, nhưng nếu chúng ta muốn đặt 40 vào hàng đợi, nơi của 40 sẽ đi đâu? Vâng, chúng tôi đã đưa nó trong q.front cộng với hàng đợi kích thước, và do đó, nó làm cho cảm giác thực sự để đưa 40 ở đây. Bây giờ nhận thấy rằng tại một số điểm, chúng ta sẽ để có được đến cuối của mảng của chúng tôi bên trong của q, nhưng mà nhạt nhòa dần 28 và 33-- chúng thật sự, về mặt kỹ thuật không gian mở, phải không? Và như vậy, chúng ta có thể eventually-- rằng quy tắc của việc thêm hai together-- chúng tôi có thể cuối cùng cần mod bởi kích thước của công suất vì vậy chúng tôi có thể quấn quanh. 

Vì vậy, nếu chúng ta có được yếu tố số 10, nếu chúng tôi thay thế nó trong phần tử số 10, chúng tôi muốn thực sự đặt nó trong mảng vị trí 0. Và nếu chúng tôi đã đi mảng location-- tha cho tôi, nếu chúng tôi được họ lên cùng nhau, và chúng tôi đã số 11 sẽ là nơi mà chúng tôi sẽ phải đặt nó, mà không tồn tại trong array-- này nó sẽ đi ra ngoài giới hạn. Chúng ta có thể mod bởi 10 và đặt nó trong mảng 1 vị trí. Vì vậy, đó là cách làm việc hàng đợi. Họ luôn luôn đi từ trái sang phải và có thể quấn quanh. Và bạn biết rằng họ đang đầy đủ nếu kích thước, mà hộp màu đỏ, trở nên bằng năng lực. Và như vậy sau khi chúng tôi đã thêm 40 đến hàng đợi, cũng làm những gì chúng ta cần phải làm gì? Vâng, yếu tố cổ xưa nhất trong hàng đợi vẫn là 19, vì vậy chúng tôi không muốn thay đổi phía trước của hàng đợi, nhưng bây giờ chúng tôi có hai các phần tử trong hàng đợi, và vì vậy chúng tôi muốn tăng Kích thước của chúng tôi 1-2. 

Đó là khá nhiều nó với làm việc với hàng đợi dựa trên mảng, và tương tự để ngăn xếp, đó cũng là một cách để thực hiện một hàng đợi như là một danh sách liên kết. Bây giờ nếu có kiểu cấu trúc dữ liệu này trông quen thuộc với bạn, nó được. Nó không phải là một danh sách đơn lẻ liên kết, đó là một danh sách gấp đôi được liên kết. Và bây giờ, khi một sang một bên, nó là thực sự có thể thực hiện một hàng đợi như một danh sách liên kết đơn lẻ, nhưng Tôi nghĩ về mặt trực quan, nó thực sự có thể giúp để xem này như là một danh sách gấp đôi được liên kết. Nhưng nó chắc chắn có thể làm điều này như là một danh sách đơn lẻ liên kết. 

Vì vậy, chúng ta hãy có một cái nhìn tại điều này có thể trông như thế nào. Nếu chúng ta muốn enquue-- vì vậy bây giờ, một lần nữa chúng tôi chuyển sang một danh sách liên kết dựa trên mô hình ở đây. Nếu chúng ta muốn enqueue, chúng tôi muốn để thêm một yếu tố mới, cũng những gì chúng ta cần phải làm gì? Vâng, trước hết, bởi vì chúng ta đang thêm đến cùng và loại bỏ từ bắt đầu, chúng ta có thể muốn duy trì con trỏ đến cả đầu và đuôi của danh sách liên kết? Tail là một hạn cho sự kết thúc của danh sách liên kết, phần tử cuối cùng trong danh sách liên kết. Và những thể sẽ, một lần nữa, có lợi cho chúng tôi nếu họ là các biến toàn cầu. Nhưng bây giờ nếu chúng ta muốn thêm một mới yếu tố gì làm chúng ta phải làm gì? Những gì chúng ta chỉ [? Malak?] hoặc tự động phân bổ nút mới của chúng tôi cho chính mình. Và sau đó, giống như khi chúng ta thêm bất kỳ yếu tố để một danh sách chúng ta gấp đôi liên kết, chỉ có để sắp xếp of-- ba bước cuối cùng ở đây chỉ là tất cả về việc di chuyển con trỏ một cách chính xác do đó các phần tử được thêm vào các chuỗi mà không phá vỡ dây chuyền hoặc làm cho một số loại sai lầm hoặc có một số loại tai nạn xảy ra nhờ đó mà chúng ta vô tình Orphan một số yếu tố của hàng đợi của chúng tôi. Đây là những gì này có thể trông như thế nào. Chúng tôi muốn thêm vào các yếu tố 10 đến cuối hàng đợi này. Vì vậy, các yếu tố lâu đời nhất ở đây được đại diện bởi đầu. Đó là điều đầu tiên chúng tôi đặt vào hàng đợi giả thuyết này ở đây. Và đuôi, 13 tuổi, là nhất gần đây đã thêm yếu tố. Và như vậy, nếu chúng ta muốn enqueue 10 vào hàng đợi này, chúng tôi muốn đặt nó sau 13. Và như vậy chúng ta sẽ phải tự động phân bổ không gian cho một nút mới và kiểm tra null để đảm bảo chúng ta không có một thất bại bộ nhớ. Sau đó chúng ta sẽ đặt 10 vào nút đó, và bây giờ chúng ta cần phải cẩn thận về cách chúng tôi tổ chức các con trỏ vì vậy chúng tôi không phá vỡ dây chuyền. 

Chúng tôi có thể thiết lập trường trước đây của 10 đến điểm trở lại đuôi cũ, và kể từ '10 sẽ là đuôi mới tại một số điểm do thời gian tất cả các chuỗi được kết nối, không có gì đang xảy đến sau 10 ngay bây giờ. Và như vậy con trỏ tới 10 của sẽ trỏ đến null, và sau đó sau khi chúng tôi làm điều này, sau khi chúng tôi đã kết nối 10 ngược trở lại để các chuỗi, chúng ta có thể lấy đầu cũ, hay, cái cớ tôi, đuôi cũ của hàng đợi. Sự kết thúc cũ của hàng đợi, 13, và làm cho nó trỏ đến 10. Và bây giờ, vào thời điểm này, chúng tôi có enqueued số 10 vào hàng đợi này. Tất cả chúng ta cần làm bây giờ chỉ được di chuyển đuôi để trỏ đến 10 thay vì 13. 

Dequeuing là thực sự rất giống với popping từ một chồng mà là thực hiện như một danh sách liên kết nếu bạn đã nhìn thấy những đống video. Tất cả chúng ta cần phải làm là bắt đầu ở bắt đầu, tìm các phần tử thứ hai, giải phóng các yếu tố đầu tiên, và sau đó di chuyển đầu để trỏ đến phần tử thứ hai. Có lẽ tốt hơn để hình dung nó chỉ được thêm rõ ràng về nó. Vì vậy, đây là hàng đợi của chúng tôi một lần nữa. 12 là yếu tố lâu đời nhất trong hàng đợi của chúng tôi, những người đứng đầu. 10 là nguyên tố mới nhất trong hàng đợi của chúng tôi, đuôi của chúng tôi. 

Và như vậy khi chúng ta muốn để dequeue một phần tử, chúng ta muốn loại bỏ các yếu tố lâu đời nhất. vậy chúng ta làm gì? Vâng, chúng tôi thiết lập một con trỏ traversal mà bắt đầu từ đầu, và chúng tôi di chuyển nó để nó trỏ tới phần tử thứ hai điều này queue-- một cái gì đó bằng cách nói trav bằng trav mũi tên bên cạnh, ví dụ, sẽ di chuyển trav đó để trỏ đến 15, trong đó, sau khi chúng tôi dequeue 12, hoặc sau khi chúng tôi loại bỏ 12, sẽ trở thành các yếu tố sau đó lâu đời. 

Bây giờ chúng ta đã có một tổ chức vào ngày đầu tiên yếu tố thông qua đầu con trỏ và yếu tố thứ hai qua trav con trỏ. Chúng tôi có thể đứng đầu bây giờ miễn phí, và sau đó chúng ta có thể nói gì đến trước 15 nữa. Vì vậy, chúng ta có thể thay đổi 15 của trước con trỏ trỏ tới null, và chúng ta chỉ cần di chuyển đầu hơn. Và ở đó chúng tôi đi. Bây giờ chúng tôi đã thành công dequeued 12, và bây giờ chúng tôi có một hàng đợi của 4 yếu tố. Đó là khá nhiều tất cả có đến hàng đợi, cả hai mảng dựa trên và danh sách liên kết dựa. Tôi Doug Lloyd. Đây là CS 50.