DOUG 로이드 : 당신이했습니다 있다면 스택에 비디오를 시청 이것은 아마도 느낄 것입니다 데자뷰의 조금있다. 그것은 매우 유사한 개념 것 단지에 약간의 트위스트와 함께. 우리는 큐에 대해 지금 이야기하는 것입니다. 그래서 스택과 유사한 큐, 데이터 구조의 다른 종류 인 우리는 유지하기 위해 사용할 수있는 조직적인 방법으로 데이터. 스택과 유사하게, 이를 실현할 수있다 배열이나 연결리스트로. 스택 달리 규정 우리가 결정하는 데 사용하는 가지 추가 제거 얻을 때 큐는 조금 다르다. 스택 달리하는 LIFO 구조이며, , 첫 번째 아웃 마지막으로, 큐는 FIFO입니다 처음에 구조, FIFO, 먼저 밖으로. 지금 당신은 아마, 큐 큐에 비유가 있습니다. 혹시에 라인에 한 경우 놀이 공원이나 은행, 공정성의 종류가있다 구조를 구현. 라인의 첫 번째 사람에 은행은 최초의 사람이다 누가 출납원에게 말을 가져옵니다. 

그것은 경주의 종류 것 유일한 방법 경우 아래로 당신은의 창구와 통화 할 수있어 은행은 라인의 마지막 사람이 될 것이 었습니다. 모두가 항상 원하는 것 라인의 마지막 사람이되고, 먼저 사람이 누구 누가, 잠시 기다리고있다 시간이있을 수 있습니다, 및 시간, 시간 그들은 실제로 기회가 전에 은행에서 돈을 인출. 그리고 큐의 일종 공정성 구조를 구현. 그러나 그것은 반드시 의미하지 않는다 스택은, 나쁜 일이 있음 큐는 그것을 할 수있는 또 다른 방법 있음. 그래서 다시 큐는 처음에 처음이다 출력, 마지막 스택 대, 첫 번째 아웃. 스택과 유사하게, 우리는 두 가지 작업을 우리가 큐에서 수행 할 수있다. 이름이 추가되는, 대기열입니다 큐의 끝에 새로운 요소, 이며, 디큐, 가장 오래된를 제거 큐의 전방으로부터 소자. 그래서 우리는 요소를 추가 할거야 큐의 끝에, 우리는 요소를 제거하는거야 큐의 앞에서. 또, 스택, 우리는 추가 된 스택의 상단에 요소 및 요소를 제거 스택의 상단에서. 대기열에 그래서, 그것은에 추가 있어요 전방으로부터 제거 끝. 거기에서 가장 오래된 것은 그래서 항상 다음 일 우리가 시도하는 경우에 나올하기 뭔가를 대기열에서 제외. 

그래서 다시, 큐, 우리는 할 수 있습니다 어레이 기반 구현 와 연결된 목록 구현을 기반으로. 우리는 다시 시작합니다 어레이 기반 구현. 구조 정의 꽤 비슷합니다. 우리는 다른 배열을 가지고 이 데이터 타입 값, 그래서 임의의 데이터 형식을 보유 할 수 있습니다. 우리는 다시 사용하는거야 이 예에서 정수. 

그리고 단지와 같은 우리의 어레이 기반 스택 구현, 우리를 사용하기 때문에 배열, 우리는 반드시 그 제한이 그 C 종류 의 우리를 인 우리에게 적용 어떤 역 동성이없는 우리의 성장하고 배열을 축소 할 수있는 능력. 우리는 처음에 결정해야 사물의 최대 수 무엇인가 우리는이에 투입 할 수있는 큐,이 경우, 용량은 몇 파운드 것 우리의 코드에서 상수 정의. 이 중 상업적 비디오, 용량은 10이 될 것입니다. 

우리는 추적 할 필요가 큐의 앞 그래서 우리는 어떤 요소 알고 우리는 대기열에서 제외하려면, 우리는 또한 추적 할 필요가 어떤 요소의 수를 else-- 우리는 우리의 큐에 있는지. 우리가 트랙을 유지하지 않을 주목 큐의 끝, 단지 큐의 크기입니다. 그리고 그 이유는 잘하면 것 순간에 조금 더 명확해진다. 우리가 완료되면 이러한 유형의 정의, 우리는 새로운 데이터 유형 큐라고하는 우리가 지금 할 수있는 데이터 타입의 변수를 선언. 그리고 다소 혼동, 나는 결정했습니다 , 편지 쓰기이 큐 Q를 호출 대신 데이터 유형 Q의 Q. 

그래서 여기에 우리의 큐입니다. 그것은 구조입니다. 그것은 3 명 또는 세를 포함 필드 크기 용량 어레이. 이 경우, 용량은 10이다. 그리고이 배열이다 정수를 개최 할 예정. 녹색에서 우리의 큐의 앞이며, 다음 요소는 제거하고, 빨간색한다 큐의 크기가됩니다, 얼마나 많은 요소 현재 큐에 존재하는. 우리는 q.front 동등한 말 그래서 경우 0을 q.size 크기는 동일 0-- 우리는 그 필드에 0을 넣어 것입니다. 그리고이 시점에서, 우리는 꽤 많이있어 우리의 큐 작업을 시작할 준비가. 

그래서 첫 번째 작업을 우리는 할 수 수행 뭔가를 대기열에하는 것입니다, 에 새로운 요소를 추가합니다 큐의 끝. 그럼 우리는 무엇을해야합니까 일반적인 경우에합니까? 그럼이 기능은 요구를 대기열에 우리의 큐에 대한 포인터를 적용합니다. 다시 말하지만, 우리는 선언했다면 전 세계적으로 우리의 큐, 우리는이 작업을 수행 할 필요가 없습니다 것입니다 반드시, 그러나 일반적으로, 우리 포인터를 수락해야 데이터 구조 이런 식으로, 그렇지 않으면 때문에, 우리는 우리가있어 value-- 지나가는거야 큐의 사본을 전달, 그래서 우리는 실제로 변경하지 않을 우리는 변경하고자하는 큐입니다. 

그것은 할 필요가 다른 것은 받아 들일입니다 적절한 유형의 데이터 요소. 또,이 경우의 정수가 될 것, 하지만 당신은 임의의 수 값 데이터 유형을 선언 더 일반적으로 사용합니다. 즉, 우리가 대기열에 할 요소이다 우리는 큐의 끝 부분에 추가 할. 그럼 우리가 실제로 원하는 큐에 데이터를 배치합니다. 이 경우,에 배치 우리의 배열의 정확한 위치, 그리고, 우리는 크기를 변경하려면 큐의, 얼마나 많은 요소가 우리를 현재이 있습니다. 

그래서 시작하자. 여기서, 다시이며, 일반적으로 그 폼 함수 선언 대기열이 어떻게 보이는지에 대한. 그리고 여기 우리는 간다. 의이 수를 대기열에 보자 큐에 (28). 그래서 우리가 할 건가요? 글쎄, 우리의 큐의 앞입니다 0, 그리고 우리의 큐의 크기에 0이고, 그래서 우리는 아마 넣을 배열 요소 수의 수 (28) 0, 오른쪽? 그래서 우리는 지금 거기에 있음을 배치했습니다. 그래서 지금 우리는 무엇을 변경해야합니까? 우리는 변경하지 않으 큐의 앞에 우리는 어떤 요소를 알고 싶어하기 때문에 우리는 나중에 큐에서 제거해야 할 수도 있습니다. 그래서 이유를 우리는 앞이 있습니다 무엇의 지표의 일종이다 배열에서 가장 오래된 것. 그럼 array--에서 가장 오래된 일에 사실, 배열의 유일한 것은 바로 들을 당장 인 28 배열 위치 0. 그래서 우리는하고 싶지 않아 그 녹색 번호를 변경 왜냐하면 가장 오래된 요소입니다. 대신, 우리는 크기를 변경할. 이 경우, 우리는 정액 1 크기를 증가. 

여기서의 아이디어 이제 일반적인 종류 다음 요소는 큐에 갈 것입니다 그 두 숫자를 추가하는 것입니다 함께, 전면 및 크기, 그 어디 다음을 말씀 드리죠 큐에 요소 갈 것입니다. 그래서 지금의 다른 번호를 대기열에 할 수 있습니다. 의 33 대기열에 보자. 그래서 33로 갈 것입니다 배열 위치 0에 1을 더한. 이 경우에 그래서, 그것은거야 배열 위치 1로 이동합니다, 지금 우리의 큐의 크기는 2입니다. 

다시 말하지만, 우리는 변화하지 않을 우리의 큐의 앞, 28 여전히 때문에 오래된 요소, 그리고 우리 우리는 결국 얻을 때 원하는 이러시면 요소를 제거하기 위해 대기열에서 제외 이 큐에서, 우리는 알고 싶다 여기서 가장 오래된 원소이다. 그래서 우리는 항상 유지해야 즉 여기서의 일부 표시. 그래서 0가있다거야. 즉, 전면가있다거야. 

대기열에서의 또 하나의 요소 (19)을 보자. 나는 당신이 추측 할 수있다 확신 여기서 19는 갈 것입니다. 그것은에 갈거야 배열 위치 번호 2. 즉, 0 플러스 2입니다. 그리고 지금 우리의 큐의 크기는 3입니다. 우리는 3 요소를 가지고있다. 그래서 우리는에 있었다, 우리는하지 않을거야 경우 지금까지, 다른 요소를 대기열에 그것은 배열 위치로 갈 것 번호 3, 우리의 큐의 크기 4 일 것입니다. 그래서 우리는 지금 여러 가지 요소를 대기열했습니다. 이제 그들을 제거하기 시작하자. 의는 대기열에서 작업을 대기열에서 제외 할 수 있습니다. 

종류 인 팝 그래서 비슷한 이 스택의 아날로그, 디큐는 동의 필요 다시 queue--에 대한 포인터 하지 않는 한이 전 세계적으로 선언합니다. 이제 우리는 위치를 변경하려면 대기열의 앞. 그것은 일종의 오는 곳이다 놀이로, 그 앞에 변수 우리가 제거되면 때문에 요소, 우리가 원하는 다음으로 오래된 요소로 이동합니다. 

그럼 우리가 감소 할 큐의 크기, 그리고, 우리는 값을 반환하려면 그는 큐에서 제거되었습니다. 다시 말하지만, 우리는 단지 그것을 버리고 싶지 않아요. 우리는 아마도 압축을 해제 우리가있어 queue--의 IT 우리가 걱정 때문에 그것을 대기열에서 제외. 그래서 우리는이 함수가 반환 할 입력 값의 데이터 요소. 또,이 경우는 정수 값이다. 

그래서 지금의이 일을 대기열에서 제외 할 수 있습니다. 의 대기열에서 요소를 제거 할 수 있습니다. 우리가 말한다면 INT X는 동일 & Q, 앰퍼샌드 q-- 다시이 Q 데이터에 대한 포인터이다 structure-- 어떤 요소 대기열에서 제거 될 것입니다? 이 경우, 제 때문에 , 첫 번째 데이터 구조, FIFO 밖으로 우리는이에 넣어 먼저 대기열 (28)이고,이 경우, 우리는 밖으로 (28)을거야 무엇을하는 대기열이 아닌 19, 이 스택이 있다면 우리가 할 것입니다. 우리는 큐에서 28를 취할 것입니다. 

우리가 무슨 짓을했는지와 유사 스택, 우리가 실제로 아니에요 (28)을 삭제하는 것 큐 자체에서, 우리는 단지 종류에가는거야 의 그것이없는 척. 그래서 거기있을거야 메모리에,하지만 우리는 그냥있어 종류의 이동을 무시하는 것 우리 Q 데이터의 다른 두 필드 구조. 우리는 앞을 변경하는 것입니다. Q.front 지금에 가고 즉 지금이기 때문에, 1 일 우리가 가지고있는 가장 오래된 요소 우리 큐, 우리는 이미 28을 제거했기 때문에, 이는 이전의 오래된 요소였다. 

그리고 지금, 우리는 변경하려면 큐의 크기 두 가지 요소 대신 3. 지금 기억 이전의 나는 말할 때 우리 큐에 요소를 추가 할, 우리는 배열 위치에 넣어 이는 앞의 크기의 합이다. 이 경우에 그래서, 우리는 여전히 퍼팅 그 큐 내의 다음 요소 어레이의 위치 (3) 내로 우리는 두 번째에있는 것을 볼 수 있습니다. 

그래서 우리는 지금 대기열 한 우리의 큐에서 첫 번째 요소. 이제 다시 해 보자. 의 다른를 제거하자 대기열에서 요소입니다. 오래된 경우, 전류 요소는 배열 위치 1입니다. 즉 q.front이 우리에게 무엇을. 즉, 녹색 상자는 것을 우리에게 알려줍니다 그 가장 오래된 요소입니다. 그리고, X는 33이 될 것입니다. 우리는 종류의 잊지합니다 (33) 어레이에 있는지, 우리는 지금 그런 말을 할 것이다 큐에 새로운 오래된 요소 어레이 (2)의 위치 및 크기이며 요소의 큐의 개수 우리는 큐에, 1 있습니다. 이제 뭔가를 대기열에하자, 나는 종류는 제 2 전이 멀리 준 그러나 우리는로 (40)를 넣어하려는 경우 큐는 어디 (40) 갈거야? 그런데 우리는 그것을 넣어 봤는데 q.front 플러스 큐의 크기, 그리고 그것은에 의미가 있습니다 실제로 여기에 40을 넣어. 지금에 통지 어떤 시점, 우리는거야 의 끝에 도착 Q의 내부에 우리의 배열, 하지만 28을 머 금고 33-- 그들은 기술적으로, 실제로있어 열린 공간, 오른쪽? 그래서, 우리는 eventually-- 수 있습니다 추가의 규칙 두 together-- 우리는 결국 수도 용량의 크기에 의해 개조 할 필요 그래서 우리는 랩 어라운드 수 있습니다. 

우리가 요소에 도착한다면 우리가 있다면 10 번 원소 번호 10를 대체, 우리는 거라고 실제로 배열 위치 0에 넣어. 그리고 우리는 가고 있었다 경우 배열 실례 location--, 우리가 함께 그들을 추가 한 경우, 우리는 수있어 우리가 넣어야 할 것 인 (11)는 것 또한, 이는 본 array--에없는 이 범위를 벗어 갈 것입니다. 우리는 10 모드 (mod)과 넣을 수 그 배열 위치 1. 그래서 큐가 작동하는 방법입니다. 그들은 항상 왼쪽에서 갈거야 오른쪽 가능성이 랩 어라운드. 그리고 당신은 그들이 거 알아 전체 경우 크기, 빨간색 상자가, 용량과 동일하게된다. 그리고 우리는 40를 추가 한 그래서 후 큐, 물론 우리는 무엇을 어떻게해야합니까? 음, 가장 오래된 요소 큐에, 여전히 19 그래서 우리는 변경하지 않으 큐의 앞에 하지만 지금 우리는 두 가지를 가지고 큐의 요소, 그래서 우리는 증가 할 1-2 우리의 크기입니다. 

즉 거의 그것을와의 어레이 기반 큐와 협력, 및 스택과 마찬가지로, 방법도 있습니다 연결리스트로 큐를 구현합니다. 이제 데이터 구조 타입하다면 당신에게 익숙한 보인다는 것입니다. 그것은, 단독으로 연결된 목록이 아니다 그것은 이중 연결리스트입니다. 그리고 지금, 옆으로, 그것은이다 구현이 실제로 가능 단일 연결리스트로 큐,하지만 나는, 시각화의 관점에서 생각 실제로 볼 수 도움이 될 수 있습니다 이중 연결리스트로이. 그러나에 확실히 가능하다 단일 연결리스트로이 작업을 수행. 

그럼에서 살펴보기로하자 어떤이는 것처럼 보일 수 있습니다. 우리는 enquue--하려면 그래서 지금, 다시 우리는있어 연결리스트로 전환 여기에 모델을 기반으로. 우리가 대기열에 싶은 경우에, 우리는 원하는 물론, 새로운 요소를 추가합니다 우리는 무엇을 어떻게해야합니까? 우선, 음, 때문에 우리는 단부에 추가하고 과에서 제거 시작, 우리는 아마 모두에 대한 포인터를 유지하려면 헤드와 연결리스트의 꼬리? 꼬리는 또 다른 용어 인 링크 된리스트의 끝에, 연결리스트의 마지막 요소입니다. 그리고이 아마 것 다시, 우리에게 도움이 될 그들은 글로벌 변수 경우. 하지만 지금 우리는 새로운를 추가하려면 요소 우리는 무엇을해야합니까? 우리는 [? 말락?] 또는 동적으로 자신을 위해 우리의 새로운 노드를 할당합니다. 우리가 어떤을 추가 할 때 다음처럼 이중 연결리스트의 우리에 요소, 다만 동행입니다 정렬 할 수 있습니다 여기 마지막 세 단계 다만 모든 이동에 대한 있습니다 올바른 방법으로 포인터 되도록 요소에 추가됩니다 체인을 깨지 않고 체인 또는 실수의 일종을 만드는 사고의 일종을 가지고 이에 우리 실수로 발생 우리의 큐의 일부 요소를 고아. 여기에이 어떻게 보이는지입니다. 우리는 요소를 추가 할 이 큐의 마지막에 10. 여기에서 가장 오래된 요소는 그래서 머리로 표현된다. 그것은 우리가 넣어 첫 번째 일이 여기이 가상 큐에. 꼬리 (13)는, 대부분이며 최근에 요소를 추가했다. 그래서 우리는로 (10)를 대기열에하려면 이 큐는, 우리는 13 후 넣어합니다. 그래서 우리는 동적거야 새로운 노드에 대한 공간을 할당 하고 있는지 확인하는 경우는 null를 확인 우리는 메모리 고장이 없다. 그럼 우리가 갈거야 해당 노드로 (10)를 배치, 그리고 지금 우리는 조심해야 우리가 포인터를 구성하는 방법에 대한 그래서 우리는 체인을 중단하지 않습니다. 

우리는 10의 이전 필드를 설정할 수 있습니다 기존의 꼬리로 다시 가리 키도록, 및 '10 년 이후가 될 것 어떤 점에서 새로운 꼬리 이 모든 시간에 의해 체인이 연결되어, 아무것도 올 않을 것 이후 10 지금. 그리고 10의 다음 포인터 null로 가리 킵니다, 우리가 한 후에 다음 우리는이 작업을 수행 한 후 상기 체인 (10)을 뒤로 연결 우리는 기존의 머리, 또는 변명을 할 수 있습니다 나, 큐의 옛 꼬리. 큐의 옛 말, 13과 10를 가리합니다. 그리고 지금,이 시점에서, 우리가 이 큐에 수 (10)를 큐에. 우리가 지금해야 할 일은 바로 이동한다 꼬리는 10 대신 13을 가리 키도록. 

대기열에서 제외가 실제로 팝핑 매우 유사 인 스택에서 연결리스트로 구현 당신은 스택 비디오를 본 적이 있다면. 우리가해야 할 일은 시작이다 시작, 두 번째 요소를 발견, 첫 번째 요소를 확보, 다음 머리를 이동 두 번째 요소를 가리 키도록. 아마 더 나은 그것을 시각화 단지에 대한 추가 명확해야합니다. 그래서 여기에 우리의 큐는 다시입니다. (12)은 가장 오래된 요소 우리의 큐, 머리에. 도 10은 최신 요소 우리의 큐, 우리의 꼬리. 

그래서 우리는 할 때 큐에서 제거하는 요소를, 우리는 가장 오래된 요소를 제거 할 수 있습니다. 그래서 우리는 무엇을해야합니까? 그런데 우리는 순회 포인터를 설정 즉, 머리에서 시작 우리는 수 있도록 이동 그것 두 번째 요소를 가리키는 이런 TRAV을 말하여 무엇인가를 queue-- TRAV 다음 화살표에 해당, 예를 들어, 를 가리 키도록이 TRAV을 움직일 것입니다 우리가 12 대기열에서 제외 후, 15 일, 우리는 (12)를 제거한 후 또는 것 당시 가장 오래된 요소가된다. 

이제 우리는 처음에 보류있어 포인터가 머리를 통해 요소 그리고 두 번째 요소 포인터 TRAV를 통해. 우리는 지금 무료로 머리를 수 있고, 우리는 할 수 있습니다 아무것도 더 이상 15 전에 온다 말한다. 그래서 우리는 15의 이전 변경할 수 있습니다 포인터가 null로 가리 키도록, 그리고 우리는 단지 머리를 통해 이동합니다. 그리고 거기 우리는 간다. 이제 우리는 성공적으로이 12 대기열, 지금 우리는 4 요소의 다른 큐가 있습니다. 즉, 거의 전부 큐에있다 두 배열 기반 및 링크 된 목록을 기반으로. 나는 더그 로이드입니다. 이 CS 50입니다.