[Powered by Google Translate] [섹션 6 : 이하 편안한] [네이트 Hardison] [하버드 대학] [이 CS50 수 있습니다.] [CS50.TV] 괜찮아요. 제 6에 오신 것을 환영합니다. 이번 주, 우리는 섹션에서 데이터 구조에 대해 이야기 할 수있을 것 이번 주 문제는 spellr에 자리 잡고 주로하기 때문에 다른 데이터 구조 탐험의 전체 무리는하지 않습니다. 이 문제 세트 함께 갈 수있는 여러 가지 방법이 몰려있다 그리고 당신이 알고있는 더 많은 데이터 구조, 당신이 할 수있는 더 멋진 일들. 

그럼 시작하자. 먼저 우리는 스택에 대해 이야기 할거야 우리가 얘기하는거야하는 스택과 큐 데이터 구조. 우리가 그래프에 대해 얘기 시작할 때 스택과 큐, 정말 도움 우리는 지금 너무 많은 일을 할거야 안된다. 하지만 CS의 가장 큰 기본 데이터 구조 중 하나를 이해하기 정말 잘하네요. 문제 세트 사양에 설명 유사한으로 스택에 대한 당신이 그것을 뽑아 경우, 대화 당신이 식당 홀에서 식당에서 가지고 식사 트레이의 더미 식당 직원이 와서 그들이 청소 한 후, 식사 트레이를 만들어 곳 때 그들은 그들에게 다른 상단에 하나를 쌓아. 그리고 아이들은 음식을 사러 올 때 그들은 먼저 상단 하나 트레이를 당겨 다음, 그 아래 한 다음, 그 아래 한. 그래서, 효과, 식당 직원은 내려 놓고하는 첫 번째 줄 이륙됩니다 마지막 하나입니다. 식당 직원이 입고있는 마지막 하나는 저녁 식사를 위해 이륙됩니다 첫 번째입니다. 당신이 이미하지 않은 경우이 문제 세트의 사양에, 당신은 어떤을 다운로드 할 수 있습니다 우리는 이런 종류의 구조체를 사용하여 스택 데이터 stucture를 모델링에 대해 이야기. 

그래서 우리가 가진 게 무엇,이 강의에서 제시 한 것과 유사합니다 강의를 제외하고 우리는 숯불 * s에 반하여 ints로이를 제시했다. 이 그 가게 어떤 스택하실 건가요? 다니엘? 우리는이 스택에 무엇을 저장하는거야? [다니엘] 문자열? >> 우리는 분명,이 스택에 문자열을 저장합니다. 당신이 스택을 만들려면이 필요합니다 모든 배열입니다 특정 용량의이 경우있는 용량은 상수이기 때문에 모두 대문자로 될 것입니다. 그리고 배열뿐만 아니라, 우리가 추적해야하는 모든 배열의 현재 크기입니다. 하는 진짜 멋진 일이지 여기서주의해야 할 점 우리가 다른 데이터 구조, 배열의 상단에 스택 데이터 구조를 작성하는 것입니다. 스택을 구현하는 여러 가지 방법이 있습니다. 우리는하지만, 희망적으로 연결된 목록 문제 일 후, 아직 그렇게하지 ​​않습니다 당신은 쉽게뿐만 아니라 연결된 목록의 상단에 스택을 구현하는 방법을 볼 수 있습니다. 그러나 지금, 우리는 배열에 충실합니다. 그러니 다시 우리가 필요로하는 모든 배열이며, 우리는 배열의 크기를 추적해야합니다. [샘] 죄송합니다, 왜 당신이 스택 문자열 위에 말했다입니까? 문자열은 스택 내에있는 식으로는 같습니다. [Hardison] 그래. 우리는 우리 어레이 데이터 구조를하고, 만드는거야 - 정말 좋은 질문입니다. 그래서 질문은이 온라인을 감상하는 사람들을 위해, 왜 왜 우리는, 스택 문자열의 상단에 있다는 말을 여기에는 문자열은 스택 안에있는 것 같습니다? 때문에 어느 완전히 경우가 있습니다. 내가 얘길하는 것은 우리가 배열 데이터 구조를 가지고 한 것이 었습니다. 우리는 숯불 * s의 배열, 문자열의 배열을 해 우리는 스택 데이터 구조를 생성하기 위해 해당에 추가 할 수 있습니다. 

따라서 스택은 배열보다 약간 더 복잡합니다. 우리는 스택을 구축 할 배열을 사용할 수 있습니다. 우리는 스택이 배열의 상단에 내장되어 말 몫이다. 마찬가지로, 내가 전에 말했듯이, 우리는 링크 목록의 상단에 스택을 구축 할 수 있습니다. 대신 우리의 요소를 보유 할 배열을 사용, 우리는 우리의 요소를 개최하고 주위 스택을 구축하는 링크 목록을 사용할 수 있습니다. 몇 가지 코드를보고, 그럼 예를 몇 통과하자, 실제로 여기서 무슨 일이 있었는지 확인합니다. 왼쪽에서, 그 스택 구조체가 메모리에 모습을 버려 한 용량은 # 포워드하도록 정의 된 경우. 우리는 우리의 네 요소 숯불 * 배열이 있어요. 우리는 문자열 [0] 문자열 [1], 문자열 [2] 문자열 [3]이 있어요 그런 다음 크기의 정수에 대한 마지막 공간. 이 말이 돼? 좋아요. 이건 내가 오른쪽에 무엇한다면 어떤 일이 일어입니다 내 코드 할 것입니다, 그냥 구조체, S라는 스택 구조체를 선언하는 것입니다. 이것은 우리가 얻을거야. 이 메모리에서이 발자국을 보내고. 여기서 첫 번째 질문이 스택 구조체의 내용이 무엇입니까입니까? 지금 그들은 아무것도 아냐,하지만 그들은 완전히 아무것도하지 않습니다. 그들은 쓰레기 이러한 종류의하고 있습니다. 우리는 아무 생각 그 안에 뭐가 있는지이 없습니다. 우리가 스택을 선언 할 때, 우리는 메모리의 상단에 그를 던져 요. 이 정수 i를 선언하고 초기화하지 않은 거 가지입니다. 거기 엔 뭐가 들어 있는지 알아하지 않습니다. 당신이 거기에 뭐가 읽을 수 있습니다 하지만 도움이 슈퍼 영웅이 될하지 않을 수 있습니다. 니가 항상 기억하고 싶은 한 가지가 초기화해야합니다 무엇이든 초기화합니다. 이 경우, 우리는 제로로 크기를 초기화 할거야 그 우리를 위해 매우 중요하다고 판명 겁니다 때문입니다. 우리는 가서 포인터의 모든 문자 * s을, 초기화 할 수 아마도 null이 어떤 이해 값이 있어야합니다. 그러나 우리가 그렇게 할 수있는 완전히 필요가 없습니다. 

이제 스택에있는 두 개의 주요 작업은? 사람은 스택으로 뭘 강연에서 기억나요? 그래? [스텔라]는 넘기고 터지는? 정확히 >>. 넘기고 터지는 것은 스택에있는 두 개의 주요 작업입니다. 그리고 푸시 어떻게합니까? >>이 상단에 뭔가를두고 스택의 후 다시 시도해가 벗겨집니다. [Hardison] 그렇지. 그래서 밀어은 스택의 상단에서 뭔가를 등록합니다. 이 카운터에 식사 트레이를 내려 놓고 식사를 직원 같아. 그리고 터지는은 스택의 식사 트레이를하고있다. 자, 무슨 일이 일어날 지의 예 몇 통과 우리는 스택에 물건을 밀어 때. 우리는 스택 상에 문자열을 '안녕하세요'밀어한다면, 이게 우리 다이어그램 현재 모습입니다. 어떻게되는지 알아요? 우리는 문자열 배열의 첫 번째 요소로 밀어 우리는 1 일 우리의 크기 수를 늘어. 우리가 두 슬라이드 사이의 차이를 볼한다면, 여기 10 살때, 여기에 누르기 전에 있습니다. 여기에 푸시 한 후입니다. 누르기 전에, 푸시 후. 그리고 지금 우리는 스택에 한 요소가 있습니다. 이 문자열 "안녕하세요"이고, 바로 그 거에요. 배열의 다른 모든 우리의 문자열 배열에서 여전히 쓰레기입니다. 우리가 초기화되지 않았습니다. 자, 우리가 스택에 다른 문자열을 밀어 말한다. 우리는이 시간에 "세계"를 강요하고 있습니다. 그래서 당신은, "세계가 '여기'안녕하세요 '의 상단에갑니다 볼 수 있습니다 와 크기 카운트 2까지갑니다. 이제 우리는 "CS50", 그 다시 정상에 가서 밀어 수 있습니다. 우리가 돌​​아 가면, 당신은 우리가 스택의 상단에 물건을 밀어하는 방법을 볼 수 있습니다. 그리고 지금 우리는 튀어 야지. 우리가 스택의 어떤 오프를 체포되었을 떼, 어떻게 된거야? 사람의 차이를 볼 수? 그것은 아주 미묘한 힘이있는 거지. [학생] 크기입니다. >> 네,, 크기가 변경되었습니다. 

다른이 변경 될 을까? 너무 [학생] 문자열. >>이 맞아. 너무 문자열. 그것은 판명 당신이 이런 식으로 일을 할 때, 우리는 우리의 스택에 요소를 복사하지 않았기 때문에, 우리는 실제로 아무것도 할 필요가 없습니다, 우리는 크기를 사용할 수 있습니다 우리 배열에 일의 수를 추적 할 수 있도록 우리가 다시 나타 때, 다시 우리가 1 우리의 크기를 감소. 실제로에 가서 뭔가를 덮어 쓰게 할 필요가 없습니다. 펑키의 종류. 우리가해야 할 것이 더 작업이기 때문에 우리가 일반적으로 혼자 일을 유지하는 것이 밝혀졌다. 우리가 돌​​아가서 뭔가를 덮어되어 있지 않은 경우, 왜 그렇게? 그래서 우리는 스택의 두 배에서 튀어 때 않네요 모든 크기 몇 번을 감소 연산이다. 그리고 다시, 우리가 우리 스택에 물건을 복사하지 수 있기 때문입니다. 그래? 어서. [학생, 이해할 수없는] >> 그리고 다시 뭔가를 밀어 때 어떻게 되겠습니까? 다시 뭔가를 밀어 때, 어디로 가야합니까? 어디에서, 바질 요? 문자열 [1] 안으로 >>? >>이 맞아. 왜 문자열 [3]로 이동되지 않는 이유는 무엇입니까? [바질]는 아무 문자열에서가 있다고 잊었 때문에 [1]과 [2]? [Hardison] 그렇지. 우리 스택은, 본질적으로, 그것이 무엇이든에 쥐고 있었다고 "잊었" 문자열에서 [1] 또는 문자열 [2], 우리는 "woot"를 밀어 있으므로 때, 그냥 문자열 [1]에서 요소로 그를 게재 할 수 있습니다. 기본 수준에서, 어떻게 작품을 거기에 질문 있습니까? [샘] 그래서이 금액의 측면에서, 어떠한 방식으로 동적이지 또는 스택의 크기의 관점에서? [Hardison] 그렇지. 입니다 - 중요한 점은이 동적으로 growning 스택 아니라고했다. 이것은 대부분의 네 가지로, 대부분의 네 번째 문자 * s의, 보유 할 수있는 스택입니다. 우리는 다섯 번째의 것을 시도하고 밀어한다면, 당신은 무슨 일이라도 어떻게 생각하세요? [학생 이해할 수없는] [Hardison] 그렇지. 일어날 수있는 여러 가지가 있습니다. 그것은 아마도 우리가 무엇에 따라 잘못을 감금 할 수 - 정확히 어떻게 우리는 백 엔드를 구현했다. 그것은 덮어 쓸 수 있습니다. 우리가 수업 시간에 말씀하신 그 버퍼 오버 플로우를 만들 수 있습니다. 어떻게 덮어 쓰기 될 수 가장 눈에 띄는 일이 될 것입니다 우리는 스택에 추가 일을 보내버 리려고한다면? 그럼 당신은 버퍼 오버 플로우를 언급. 에 이상 작성 또는 밟은받을 것이다 일이 될 수도 있습니다 무엇 우리는 여분의 일을 밀어하려고하면 실수로 넘쳐? 경우 [대니얼, 이해할 수없는] >> 가능. 그러나 처음에, 어떻게됩니까? 우리가 사분의 일 일을 밀어하려고하면 어떨까요? 그것은 적어도 우리가 가진 한이 메모리 다이어그램으로, 크기를 덮어 쓰기 할 수 있습니다. 

문제 설정 사양에있는 우리가 오늘 구현 할 거냐 우리가 원하는 것은 단지 false를 반환합니다. 우리 푸시 방법은 부울 값을 반환 것입니다 압박이 성공하면 그 부울 값 사실이 될 것입니다 과 거짓 스택이 가득 차서 더 아무것도 누르지 할 수 있습니다. 의 지금 그 코드를 약간의 통과 보자. 다음은 푸시 기능입니다. 스택에 대한 푸시 기능은 스택에 넣어 문자열에 데려 갈 수 있습니다. 문자열이 성공적으로 밀려 된 경우는 TRUE를 반환 거예요 스택과 거짓 그렇지 있습니다. 무엇에 대한 모든 제안 여기서 할 수있는 좋은 제일 먼저 할 수 있을까요? 크기는 용량을 동일 경우 [샘] 후 false를 반환? [Hardison] 찾았다. 잘 했어. 크기가 용량 인 경우에는 FALSE를 반환거야. 우리는 스택에 더 아무 것도 삽입 할 수 없습니다. 그렇지 않으면, 우리는 스택의 상단에 뭔가를 넣어 싶습니다. 처음에 "스택의 최상위 (top)는"무엇입니까? [다니엘] 크기 0? >> 크기 0. 스택의 하나가 후 스택의 최상위 (top)은 무엇입니까? 아가씨, 넌 알지? [미시] 하나입니다. >> 크기가 정확히 한 것입니다. 당신은 크기에 추가 유지 하고 배열의 인덱스 크기의 새로운 요소에 주력하고 때마다. 그 말이 경우에, 한 - 라이너의 종류로 할 수 있습니다. 우리는 문자열 배열이 있어요 그래서, 우리는 크기 지수에서 액세스 할거야 우리는 그냥 우리의 숯불 *를 저장하는거야. 더 문자열 복사 여기에가에 갈 수 없어 어떻게주의, 메모리의 동적 할당? 그리고 미시 우리가 지금 할 일을 올렸어 우리가 배열의 해당 위치에 문자열을 저장 한 때문에, 그녀는 우리가 다음 공격을 위해 준비하도록 하나의 크기를 증가해야한다고 말했다. 그래서 우리는 s.size 랑 할 수 있습니다 + +. 이 시점에서, 우리는 배열로 만든 것. 우리가해야 할 마지막은 무엇입니까? [학생] TRUE를 반환. >> 사실 돌아갑니다. 그럼, 아주 간단한 코드 아주 간단합니다. 너무 많이. 일단 당신이 스택의 작동 방식 중심으로 머리를 감싸 한 이 구현하기 아주 간단합니다. 

자,이의 다음 부분은 스택의 문자열에서 보여주고 있습니다. 당신이 사람들에게 약간의 작업을 할 시간을 주겠어. 거의 기본적으로 우리가 여기에 푸시에 무슨 짓을했는지의 역입니다. 내가 한 것은 사실입니다 - 죄송합니다. I, 여기, 그리고 어플라이언스에 기기를 부팅 한 나는 문제가 5 명세를 설정 찾았습니다. 우리가 확대되면 내가 cdn.cs50.net/2012/fall/psets/pset5.pdf에있어 볼 수 있습니다. 너희들이 여기 section6.zip에 위치하고있어이 코드를 다운로드하신 적이 있습니까? 괜찮아요. 당신은 정말 신속하게 지금 그렇게, 그런 짓을하지 않은 경우. 내 터미널 창에서 할 수 있습니다. 사실 여기까지 했어요. 그래. 네, 샘? >> 나는 왜 = str을 크기의 s.string의 괄호를하던가요에 대한 질문이 있으십니까? 으로 str은 무엇입니까? 그 전에 어디 선가 정의되거나 - 오, 숯불 *의 str을에? [Hardison] 예, 맞아요. 그것은 인수했다. >> 아, 그래. 미안 해요. [Hardison]이 (가) 우리는 여기에 전달하는 문자열을 지정하는 우리가 여기서 얘기하지 않았 음을 마련 할 수있는 다른 질문은 우리가 S라는 변수가 있다는 당연한 우리는했습니다 그 범위와 우리에게 접근으로했다. S이 스택 구조체이라고 당연한 우리는했다. 그래서,이 푸쉬 코드를 다시보고 당신은 우리가 통과 했어요이 문자열로 일을하고 것을 알 수 있습니다 하지만 갑자기, 우리는 같은 s.size에 액세스, S 어디에서 왔는가?하는 우리가 섹션 아카이브에 보는거야하는 코드 다음 문제에서 뭘 할 거라고 물건, 세트 우리는 우리의 스택이 전역 변수를 구조체했습니다 우리는 모든 다른 기능에 대한 액세스 권한이 수 있도록 수동으로 주변을 통과하고 참조하여 통과 할 필요없이, 거기에 물건을 모든 종류의 해. 우리는 친절 일을하기 위해, 당신이 경우, 조금 속이고하고 있습니다. 그리고 그 얘기가 재미 있기 때문에 우리가하는 일이 뭔가, 그것은 쉬워졌습니다. 사람들이 큰 데이터 구조가있는 경우 종종, 사람들은 이렇게 볼 수 있습니다 그들은 프로그램 내에서 운영되고있어. 

의가 어플라이언스에 다시 가자. 모두가 성공적으로 section6.zip 받으셨어요? 다들 지퍼 section6.zip를 사용하여 압축을 풉니 다? 당신은 제 6 항 디렉토리에 가면 - 아, 사방 - 당신이 여기에 무슨리스트, 당신은 세 가지. C 파일이 있어요 것을 볼 수 있습니다. 당신은 단독으로 연결된 목록입니다 큐, sll, 그리고 스택있어. 당신은 stack.c을 열면, 당신은 우리가 우리에 대해 정의이 구조체있어 것을 알 수 있습니다 우리가 슬라이드에 대해 얘기하는 정확한 구조체. 우리는 스택에 대한 우리의 전역 변수 있어요 우리는 우리의 푸시 기능이있어 그리고 우리는 우리의 팝업 기능을있어. 여기에 슬라이드에 다시 밀어 줄은, 코드를 올려 놓을 게요 하지만 너희들이 어떻게하고 싶은 것은 최선을 다해입니다 가서 팝업 기능을 구현합니다. 일단 당신이 그것을 구현 한, 당신은 스택을하여이를 컴파일 할 수 그리고, 결과 스택 실행 파일을 실행 그 아래가 메인에 해당이 테스트 코드를 모두 실행됩니다. 그리고 메인은 실제로 푸시와 팝 호출을 담당한다 모든 괜찮아지나 확인하고. 또한 여기에 스택 크기를 초기화 그럼 당신은 초기화에 대해 걱정할 필요가 없습니다. 당신은 제대로 초기화 된 것으로 간주 할 수 있습니다 당신이 팝업 함수에서 액세스하는 시간으로. 그게 말이나 돼? 그래서 여기에 우리가 이동합니다. 푸시 코드가 있습니다. 난 자네들과 5 10 분을주지. 그리고 당신이 코딩하는 동안 중간에 질문이 있으면, 을 크게 문의 해 주시기 바랍니다. 당신이 그걸 고정 지점에 도착하면, 그냥 물어보십시오. 다른 사람들에게 알려, 내가 알려 주시기 바랍니다. 도 이웃과 협력합니다. [다니엘] 우리는 단지 지금 팝업 구현거야? >> 그냥 팝업. 원하는 경우이 압력의 구현을 복사 할 수 있지만 테스트가 작동 할 수 있도록. 그것은에 점점 물건을 테스트하는 하드 으니까 - 아니면, 처음부터 스택에 뭔가가없는 경우 스택의 터지는 것을 테스트 어렵습니다. 

반환 될 예정 팝업은 무엇입니까? 스택의 최상위 (top)에서 요소입니다. 그것은 스택의 최상위 (top)의 요소를 하차해야하는 그리고 스택의 크기를 감소 그리고 지금 당신은 상단에있는 요소를 잃었습니다. 그리고 당신은 상단에있는 요소를 반환합니다. [학생, 이해할 수없는] [Hardison] 당신이 그렇게하면 어떻게 되겠습니까? [학생, 이해할 수없는] 어떤 일이 끝나는 것을 당신은 아마 중 하나를 액세스 그 요소가 아직 초기화되지 않은하므로 계산 이 마지막 요소가 꺼져 어디. 잘 보면 그래서 여기, 푸쉬에, 우리는 s.size 요소에서 문자열에 액세스하는 이 새 색인 때문입니다. 그것은 스택의 새로운 최상위입니다. 팝업에 반해, s.size는 다음 공간이 될 것입니다 당신의 스택에있는 모든 요소 위에 공간. 따라서 최상위 요소는 s.size에 없다 오히려, 그것은 아래입니다. 

당신이해야 할 또 다른 문제 - 팝업에서 당신은 크기를 감소해야하나요합니다. 당신은 여기에 우리의 작은 그림으로 기억한다면, 정말 우리가 무슨 일이 본 유일한 우리가 팝업 호출 할 때 이 정도 크기 후 1 먼저 2, 떨어 것이 었습니다. 그럼 우리가에 새로운 요소를 밀 때, 그것은 적절한 자리에 계속합니다. [바질] s.size은 2 인 경우는 엘리먼트 (2)에 갈거야, 그리고 그 요소를 나타 싶어 하죠? 우리가 졌으면 - >> 그럼 다시 살펴 보자. 이이 시점에서 우리 스택 인 경우 우리는, 팝업 전화 되는 인덱스는 맨 위 요소입니다? [바질]는 2에서는 만 3 열어거야. >>이 맞아. 따라서 우리의 크기는 3 곳이지만, 우리는 색인을 2 요소를 나타 싶습니다. 당신이 배열의 제로 색인을 가지고 하나에서의 전형적인 이죠. 그래서 세 번째 요소를 나타하려는 않지만, 세 번째 요소는 인덱스 3에 없습니다. 그리고 우리가 밀어 때 그 마이너스 1 할 필요가 없습니다 이유 지금 있기 때문에, 당신은 발견되는 최상위 요소, 우리가이 시점에서 스택 위에 뭔가를 강요한다면, 우리는 인덱스 3에서 밀어 붙일 것입니다. 그리고 그냥 당신이 추진하고 때의 크기와 인덱스가 줄 것으로 발생합니다. 

누가 작동 스택 구현있어? 당신은 작업 스택 하나가있어. 팝 아직 작업이 있습니까? [다니엘] 예. 그런 것 같아요. >> 프로그램 실행 오류있는을 감금가 아니야, 이건 출력 거죠? 당신이 그것을 실행할 때 "성공"을 인쇄합니까? 그래. 가 "성공"을 출력하고 붐을 이동하지 않는 경우, 스택 확인을 실행 다음 모든 좋네요. 괜찮아요. 진짜로 빠르게 어플라이언스의로 가자, 우리는이를 통해 안내합니다. 우리는 아빠 랑 여기서 뭐하는거야 만난다면 다니엘, 당신이 한 짓 처음하는 일이 무엇 이었습니까? [다니엘] s.size이 0보다 큰 경우. [Hardison] 좋아. 그리고 왜 그런 짓을 했지? [다니엘] 스택 내부의 뭔가가 있는지 확인합니다. [Hardison] 맞아. 당신은 s.size가 0보다 큰 있는지 확인하기 위해 테스트 할; 그렇지 않으면, 당신은 일어날 것 무엇을 원하는 겁니까? [다니엘] 반환 null이? >> 반환 null이, 맞아요. 그래서, 만약 s.size은 0보다 커야합니다. 우리는 무슨 일을하는거야? 스택이 비어 있지 않으면 우리는 어떻게해야합니까? [스텔라] 당신은 크기를 감소? 괜찮아, 크기를 감소 >>. 그래서 당신은 어떻게하는거야? >> s.size ... -. [Hardison] 좋아요. 그리고 당신이 무슨 짓을 한거야? [스텔라] 그리고는 반환 s.string 말 [s.size]. [Hardison] 좋아요. 그렇지 않으면 null을 반환합니다. 네, 샘? [샘] 왜이 + 1 s.size 할 필요가되지 않는 이유는 무엇입니까? [Hardison] 플러스 1? >> 그래. >>은 알았어. 당신이 하나를 꺼내겠다 있기 때문에 [샘] 내 생각 엔, 그러면 안에게 그들이 요구하는 하나를 반환 할거야. [Hardison] 그리고 우리는 0 인덱스의이 모든 문제를 얘기를 했어요 그냥 뭐이었다. 그래서 우리가 여기에 다시 확대합니다. 우리가 여기에서이 남자를 보면, 당신은 우리가 나타 때 것을 알 수 있습니다 우리는 색인을 2 요소를 보여주고하고 있습니다. 

그래서 우리는 우리의 크기는 색인과 일치, 먼저 크기를 줄이십시오. 먼저 크기를 감소하지 않는 경우, 우리는 -1 후 감소 크기를해야 해. 좋아요. 괜찮아? 여기에 대한 질문? 이뿐만 아니라를 작성하는 다른 방법에는 여러가지가 있습니다. 사실, 우리는 뭔가를 할 수 - 우리는 하나 라이너를 할 수 있습니다. 우리는 한 줄 수익을 수행 할 수 있습니다. 우리가 그렇게함으로써 반환하기 전에 그래서 우리가 실제로 감소 할 수 있습니다. 그래서를 넣어 - s.size 전에. 그 거랑은 정말 조밀합니다. 어디의 차이 -.의 크기와 s.size .. - 즉이 접미사 - 때문에 그들이 접미사 전화 - 제공 후 s.size .. - s.size은 색인을 찾는 목적으로 평가된다는 것을 의미합니다 만약이 줄이 실행될 때 현재와 같이 그리고이 - 줄이 실행되고 나면 발생합니다. 인덱스 s.size의 요소에 액세스 한 후. 우리가 감소 먼저 일이 원하기 때문에 그것은, 우리가 원하는 게 아니에요. Othewise, 우리는 배열을 액세스 할 수있어, 효과적으로 범위를 벗어. 우리는 실제로 액세스 할 수있는 유일한 위의 요소에 액세스 할거야. 그래, 샘? >> 더 빨리 또는 한 줄 여부에 있도록 적은 RAM을 사용하여입니까? [Hardison]는 솔직히, 정말 따라 달라집니다. [샘, 이해할 수없는] >> 네, 따라 달라집니다. 당신은 컴파일러 트릭을 수행 할 수 그를 인식하도록 컴파일러를 얻을, 보통, 내가 상상. 

그래서 우리는이 컴파일러 최적화 물건에 대해 조금 언급 한 당신은 컴파일에 할 수있는 그는 컴파일러가 알 수있을 수 있다는 것은의 종류입니다 오처럼, 이봐, 어쩌면 내가, 하나의 작업이 모두 수행 할 수 로 RAM에서 크기 변수를로드에 반대하는 것은 그걸 decrementing 다시를 저장 한 다음 다시 다시로드 이 작업의 나머지 부분을 처리 할 수​​ 있습니다. 그러나 일반적으로, 아냐,이 것들 아냐 그 속도가 매우 빠르고 프로그램을 만들거야. 스택에 대한 질문 더 있습니까? 

따라서 밀 들락 거리지. 당신들은 해커 버전을 시도 할 경우 우리가 해커 판에 한 건 정말 사라 졌어요 이 스택은 동적으로 성장했다. 여기까지 푸시 함수에서 기본적으로이 도전, 그 배열이 성장하는 방법을 찾아 야지 당신은 스택에 더 많은 요소를 계속 밀고 있습니다. 사실은 너무 많은 추가 코드 없습니다. 제대로 거기에 malloc에​​ 전화를한다는 점을 기억해야합니다 - 도보로 전화 당신은 realloc를 호출 할 때 다음 해결. 당신이 관심이 있다면 그건 재미 도전입니다. 

그러나 당분간, 그럼 이동하게하고, 큐에 대해 이야기합시다. 여기까지 스크롤합니다. 대기열이 스택의 가까운 형제입니다. 그래서 스택에 그 일이 마지막에 넣어되었습니다 그런 다음 검색 할 첫 번째 일이 있었다. 우리는 주문이에서 마지막을 먼저, 또는 LIFO있어. 대기열에 반면에, 당신이 줄에 서 때의 기대로, 일렬로 한 최초의 사람 대기열에 갈 수있는 먼저, 대기열에서 검색됩니다 먼저입니다. 우리가 그래프를 처리 할 때 큐도 종종 사용됩니다 우리는 스택을 짧게 이야기처럼 그리고 큐는 다른 것들의 무리에도 편리합니다. 자주 올라 오는 한 가지 예를 들어, 유지하기 위해 노력하고 있습니다 요소의 정렬 목록입니다. 그리고 당신은 배열이 작업을 수행 할 수 있습니다. 당신은 배열의 가지 정렬 목록을 유지 관리 할 수​​ 있습니다 하지만 까다로운 도착 그때 어디 있는지 항상 찾아 내야 다음 일을 삽입 할 수있는 적절한 장소. 가 10을 통해 숫자의 배열, 1을면하는 것은, 그리고 당신은 100를 통해 모든 숫자 1에 해당을 확장하려면 그리고 당신은 무작위 순서로 숫자를 받고 모든 것을 유지하려는 당신은 통과로 정렬, 당신은 변화를 많이 할 필요가 결국. 대기열 및 기본 데이터 구조의 특정 유형의 특정 형식에, 당신은 실제로 매우 간단하게 할 수 있습니다. 뭔가를 추가 한 다음 모든 것을 할 때마다 개편 할 필요가 없습니다. 또한 당신은 주변의 내부 요소의 이동을 많이해야 돼. 우리가 큐를 볼 때, 당신은 그것을 볼 수 -도 queue.c의 섹션 코드에서 - 우리가 제공 한 구조체는 우리가 스택에 준 구조체에 아주 비슷합니다. 

이 한 예외가있어, 그 한 가지 예외 우리가 머리라고이 추가 정수를 가지고 것은, 여기 머리가 대기열의 머리의 트랙을 유지입니다 대기열 또는 첫 번째 요소입니다. 스택으로, 우리는, 우리는 검색하려고 줄 수있는 요소를 추적 할 수 있었다 단지 크기를 사용하여 스택 또는 상단, 대기열이있는 반면, 우리는 반대 끝을 처리 할 필요하고 있습니다. 우리는 압정으로 고정 말에 일을하려고 노력하지만 전면에서 물건을 반환하고 있습니다. 따라서 효과적으로 머리, 우리는 대기열의 시작의 색인을 가지고 그리고 크기는 우리에게 큐의 끝의 색인을 제공합니다 우리는 머리에서 물건을 검색하고 꼬리에 물건을 추가 할 수 있도록. 스택 반면, 우리는 어느 스택의 최상위 (top) 처리했다. 우리는 스택의 하단에 액세스 할 수 없었어요. 우리는 상단에 물건을 추가하고 상단의 일을 벗고 그래서 우리는 우리의 구조체 안에 여분의 필드를 필요하지 않았다. 그는 일반적으로 이해합니까? 괜찮아요. 네, 샬롯? [샬롯, 이해할 수없는] [Hardison] 그건 좋은 질문이고, 그 강의에 와서 하나였습니다. 아마 몇 가지 예를 통해 들어가는 것은 설명 할 이유 우리는 문자열에게 큐의 머리로 [0]를 사용하지 않습니다. 

그래서 우리는 우리의 큐를 가지고 상상, 우리는 대기열에 전화거야. 처음에, 우리는 그것을 인스턴스화되면, 우리가 그것을 선언했을 때, 우리는 아무 것도 초기화되지 않았습니다. 다 쓰레기입니다. 그럼 당연히 우리는 우리가 초기화되었는지 확인하려면 크기와 머리 입력란 모두 합리적인 0, 무언가 있어야합니다. 우리는 또한 우리를 계속 큐에 요소를 null로 수 있습니다. 그리고이 다이어그램 적합한를 만들기 위해, 이제 큐는 세 가지 요소를 개최 할 수있는 것을, 우리 스택 네를 개최 할 수 반면, 우리의 큐는 세 수용 할 수 있습니다. 그리고 그 다이어그램 적합한를 만들기 위해 단지입니다. 여기서 무슨 일이 일어날 먼저 우리는 "안녕하세요"문자열을 인큐입니다. 그리고 마찬가지로 우리가 스택과 함께 한, 여기 정말 다른 아무것도, 우리는 문자열에 [0] 1하여 크기를 증가에 문자열을 던져. 우리는 "안녕"을 인큐, 그것은 입고됩니다. 그래서이 대부분 스택 것 같습니다. 우리는 여기에 새로운 요소, 새로운 요소를 시작 크기는 올라가고 유지합니다. 우리가 뭔가를 dequeue 할 때 어떻게이 시점에서 어떻게됩니까? 우리가 dequeue 할 때, 그건 우리가 dequeue 할 요소입니까? [바질] 문자열 [0]. >> 제로. 정확히 맞아, 바질. 우리는 첫 번째 문자열이 한 "안녕하세요"를 제거하고 싶습니다. 따라서 변경 다른 점은 무엇 이었습니까? 우리가 스택의 어떤 오프를 때린 공지, 우리는 방금 크기를 변경 하지만 여기, 우리는 변화 그 몇 가지있어. 크기 변경하지만, 머리를 변경 않습니다 만. 이 이전 샬롯의 지점으로 돌아 간다됩니다 왜 우리는뿐만 아니라이 머리를해야합니까? 그것은, 지금 샬롯을 이해합니까? 의 >> 종류. 의 [Hardison]인가? 우리가 dequeued했을 때 무슨 일 있었나요? 머리는 이제 재미입니다 무슨 짓을 한거야? 그 변경 [샬롯] 오, 까 - 알았어. 알 겠어요. 때문에 머리 - 머리는 위치의 측면에서의 변화를 가리키고있다. 더 이상 항상 제로 인덱스의 하나. >> 네, 맞아요. 높은 요소를 dequeueing 경우 무슨 일이 있었 냐면했습니다 완료되었으며, 우리는이 머리 필드가 없었 우리가 항상 0 색인에 큐의 머리에이 문자열을 호출했기 때문에, 그러면 우리는 대기열의 나머지 부분을 아래로 이동 할 것입니다. 우리는 문자열에서에서 "안녕"[1] 이동하기 위해 [0] 문자열이있을 것이다. 그리고 문자열 [2] 다운 문자열 [1]. 그리고 우리는, 요소의 전체 목록을 보려면이 작업을 수행해야 할 요소의 전체 배열입니다. 그리고 우리가 배열이 일을 할 때, 정말 비싼옵니다. 그래서 여기, 그것은 큰 문제가 아니에요. 우리는 우리의 배열의 세 가지 요소가 있습니다. 하지만 우리는 천 요소의 대기열 또는 만 요소가 있다면, 그리고 갑자기, 우리는 dequeue의 무리를 만들기 시작하면 루프의 모든 호출 일이 진짜가 지속적으로 모든 것을 내려 주던로 천천히 것입니다. 알다시피, 1 명 근무 시간, 1 1, 변화에 의해, 1 교대를 바꿔 주죠. 정말 포인터 있진 않지만 대신이 머리를 사용, 우리는 "포인터"라고 엄격한 의미에서, 그것은 포인터 취향이 아니야. 이 정수 * 또는 문자 * 또는 그런 건 아닙니다. 그러나 포인팅 또는 대기열의 머리를 보이고 있어요. 응? 

[학생]는 머리에 무엇이든 오프 팝업하는 방법 dequeue는 알 수 있습니까? [Hardison] 어떻게 dequeue이 머리에 있다고든지 튀어하는 방법을 알고 있습니까? >> 오른쪽, 그래. >> 모습이보고있어는로 설정되어있는 단지 어떤 머리 영역입니다. 우리는 바로 여기 봐봐 첫 번째 경우에, 경우, 우리의 머리는 0, 인덱스 0입니다. >>이 맞아. [Hardison]는 그냥 그래, 인덱스 0의 요소 문자열 "안녕하세요"이라고 말했다 그래서 우리 대기열의 머리에있는 요소입니다. 그래서 우리는 그 사람을 dequeue거야. 그래서 호출자에게 반환됩니다 요소 될 것입니다. 예, 사드? >> 그래서 머리는 기본적를 설정 - 당신이 색인을 생성 할 걸세 어디? 그거의 시작이야? >> 그래. 좋아요 >>. [Hardison] 우리 배열의 새로운 시작되고 야. 당신이 뭔가를 dequeue 때 당신이해야 할 모든, 색인 q.head에서 요소를 액세스가 그리고 그 말은 당신이 dequeue 할 요소입니다. 당신은 또한 크기를 감소해야합니다. 일이있는 약간 까다로운 잡는 곳이 어디 우리 잠시 표시됩니다. 우리가 다시 인큐 경우 우리는 지금 dequeue하고, 우리가 어디를 인큐합니까? 어디 다음 요소는 우리 대기열에 가서는 무엇입니까? 우리는 문자열 "CS"를 인큐 싶은 말. 그 어떤 색인에가는거야? [학생] 문자열 [2]. >> 둘. 왜이 아니라 0? [바질] 이제 머리는 1이기 때문에, 목록의 시작처럼 그래? [Hardison] 맞아. 그리고이 목록의 끝을 나타냅니다? 우리는 우리의 큐의 끝을 나타 내기 위해 무엇을 사용하는거야? 머리는 우리 대기열의 머리, 우리의 큐의 시작입니다. 우리 큐의 끝은 무엇입니까? [학생] 크기입니다. >> 크기, 맞아요. 그래서 우리의 새로운 요소는 크기로 들어가서, 우리가 수행하는 요소는 오프 머리에서 하차 있습니다. 우리는 다음 요소를 인큐 때, 우리는 크기에에에 무리가 올 수 있습니다. [학생]하기 전에 알고있는, 크기는 오른쪽, 1이라고 넣어? [Hardison] 맞아. 그래서별로 크기에. 크기 +,하지 +1,하지만 + 헤드. 우리는 머리를 한 금액을 기준으로 모든 이동 때문입니다. 그래서 여기, 이제 우리는 인덱스 1에서 시작 크기 (1)의 대기열에있어. 꼬리 부분은 인덱스 2입니다. 그래? 

[학생] 어떻게됩니까 때 메모리에 당신이 dequeue 문자열 [0], 그리고 문자열 '슬롯 단지 기본적으로 비우지하게하거나 잊어? [Hardison] 그래. 이런 점에서 우리가 그들을 잊고하고 있습니다. 우리는 그들의 사본을 저장 한 경우 - 많은 데이터 구조는 종종 요소의 자신의 사본을 저장합니다 데이터 구조를 관리하는 사람은 걱정할 필요하지 않도록 모든 포인터 가는지에 대해. 데이터 구조 다에 보유, 모든 사본에 개최 모든 적절하게 지속 있는지 확인합니다. 그러나,이 경우, 이러한 데이터 구조, 그냥 단순 들어, 우리가 그들에 저장 있다는 것도 사본을하지 않습니다. [학생] 그래서이 연속 배열 - >> 예. 우리가 정의가이 구조 뭔지를 다시 확인하면됩니다. 그것은 당신이 본 것 같은 단지 표준 배열 숯불 * s의 배열입니다. 그 있습니까 -? >> 그래, 난 그냥 궁금 해서요 당신은 결국 어느 정도까지 메모리가 실행됩니다 경우 귀하의 배열에 모든 빈 곳이 있다면? [Hardison] 그래, 그게 좋은 점입니다. 

우리는이 시점에서 지금 무슨 일이 일어 났는지를 보면 우리 대기열을 채워 한, 그것은 것 같습니다. 그러나 우리는 정말 우리의 대기열을 작성하지 않았습니다 우리가 사이즈 2입니다 대기열을 가지고 있지만, 인덱스 1에서 시작하기 때문에하면, 우리 헤드 포인터가있는 곳 이니까. 당신이 말한 것 같은, 그 문자열의 요소 [0] 인덱스 0에서 정말 없다. 그것은 더 이상 우리 대기열에 없습니다. 우린 그냥 가서 우리가이 일을 dequeued 때를 덮어 할 생각은하지 않았다. 그래서 우리가 메모리가 부족 한 것 같아하더라도, 우리는 정말 없어요. 우리가 사용하기에 그 자리를 이용하실 수 있습니다. 적절한 행동, 우리는 dequeue 뭔가를 처음으로 할 경우 바이 오프 나타 거라고, "안녕"좋아. 우리의 대기열이 지수 2 시작 및 크기 일입니다. 우리가 다시 무언가를 시도하고 인큐 경우 그리고 지금, 50 말 50 인덱스 0에이 장소에 가야 그것은 여전히​​ 우리 사용할 때문입니다. 예, 사드? [사드]는 그이 자동으로 발생합니까? [Hardison] 그것은 아주 자동으로되지 않습니다. 당신은 수학을해야 작동하게하지만, 기본적으로 우리가 한 것은 우리가 감싸 한 것입니다 수 있습니다. 이 사건의 한가운데에 구멍이있는 경우 [사드] 그리고는 괜찮아? [Hardison] 우리는 계산이 제대로 작동 할 수 있다면입니다. 

그리고 그런 일이 실제로 모드 연산자와도 복잡하지 않아서 것을 밝혀졌다. 그래서처럼 우리는 시저와 암호화 재료로 한 모드를 사용, 우리는 일들이 주위에 포장을하고 계속 할 수 있습니다 우리 대기열 주변과 주위와 주변과, 그 헤드 포인터가 움직이는 유지. 그 크기를 공지 사항은 항상 대기열에서 실제로 요소의 수를 존중합니다. 그리고 이건 그냥 순환 유지 헤드 포인터입니다. 우리는 처음으로 돌아 가야하는 경우, 여기서 무슨 일이 있었는지를 보면 그리고 당신은 머리에 어떤 일이 일어 났는지 우리가 뭔가를 인큐 때, 아무 머리에게 무슨 일이 있었 않습니다. 우리가 다른 것을 enqueued 때, 아무 것도 머리에게 무슨 일이 있었 않습니다. 우리가 뭔가를 dequeued 마자 머리 하나에 의해갑니다. 우리가 뭔가를 enqueued 아무것도 머리에 변화가 없습니다. 우리가 뭔가를 dequeue 때, 갑자기 모두 머리가 증가됩니다. 우리가 뭔가를 인큐 때, 아무 것도 머리에 변화가 없습니다. 

우리가 다시 무언가를 dequeue 할 경우 어떻게이 시점에서 무슨 일이 일어날? 어떤 생각? 어떻게 머리에 무슨 일이 일어날? 머리는 어떻게해야하나요 우리가 다른 것을 dequeue 할 경우? 머리는 지금, 색인 2입니다 이는 대기열의 머리는 문자열 [2]을 의미합니다. [학생] 0을 반환입니까? >>이 0이되어야합니다. 그것은 정확히, 주변에 다시 포장해야합니다. 지금까지, 우리는 dequeue라고 때마다, 우리는 머리에 한을 추가 했어요 머리에 한 추가 머리에 한 추가 머리에 한을 추가합니다. 그 헤드 포인터는 우리 배열의 마지막 색인에 도착, 가능한 빨리, 그리고 우리가 처음으로 주위를 돌려 포장을해야합니다 0으로 돌아갑니다. [샬롯] 어떤 스택의 큐의 용량을 결정? [Hardison]는이 경우에, 우리는 # 정의 상수를 사용하고 있습니다. 좋아요 >>. [Hardison]는 실제. C 파일에서, 당신이 약간의와 추문 갈 수 그리고 큰 또는 원하는만큼 약간으로합니다. [샬롯]는 그래서 당신은 그것을 대기열을 할 때, 당신은 컴퓨터를 알고 어떻게해야합니까 당신은 스택이되고 싶어 얼마나 큰? [Hardison] 그건 큰 문제입니다. 몇 가지 방법이 있습니다. 하나가 앞을 사실을 정의하는 것입니다 이 말을 4 요소 또는 50 요소 또는 만이 큐가 될 것입니다. 다른 방법은 해커 판 사람들이하는 일을하는 것입니다 더 많은 일이 인치 추가 할로 큐가 동적으로 성장해야하는 함수를 만들 

[샬롯]는 그래서 첫 번째 옵션으로 가서, 어떤 구문을 사용합니까 프로그램을 알려 대기열의 크기는 무엇인가? [Hardison] 아. 그럼이 나가자. 여기 stack.c 란 말이야, 그래서 그냥 위로 스크롤거야. 이 바로이 부​​분을 볼 수 있나요? 이것은 # 용량 (10) 정의입니다. 그리고 우리가 큐에 가지고 거의 동일한 구문입니다. 대기열에를 제외하고, 우리는 여기에 그 여분의 구조체 필드있어. [샬롯] 오, 용량이 문자열에 대한 능력을 의미 알았는데. [Hardison] 아. 이 단어의 최대 길이 거라고 생각 >>. >>은 알았어. 그래. 여기에 용량은 - 그 좋은 점입니다. 그리고이 까다로운 뭔가있다 우리가 여기에 선언 한 것은 문자 * s의 배열이기 때문이다. 포인터의 배열입니다. 이 문자의 배열입니다. 이렇게하면 파일에 대한 버퍼를 선언했을 때 당신이 본 게 뭔지 아마 I / O, 당신은 스택에 수동으로 문자열을 생성했을 때. 그러나 우리가 여기 가진 건 숯불 * s의 배열입니다. 그럼 포인터의 배열입니다. 사실, 우리는 다시 축소 우리는 여기서 무슨 일이 벌어 보면 프리젠 테이션에, 당신이 실제 요소, 문자 데이터를 볼 수 배열 자체 내에 저장되지 않습니다. 여기서 우리 어레이 내에 저장된 것은 문자 데이터에 대한 포인터입니다. 좋아요. 그래서 우리는, 큐의 크기가 단지 스택과 마찬가지로하는 방법을 본 적이 크기는 항상 대기열에 현재 요소 수를 존중합니다. 이 enqueues을 한 후, 크기는 2입니다. dequeue을 한 후 크기는 현재 1입니다. 다른 인큐을 한 후 크기는 2로 돌아합니다. 따라서 크기는 분명히 큐에 요소 수를 존중 그리고 머리는 자전거를 보관합니다. 이 0-1-2, 0-1-2, 0-1-2에서갑니다. 그리고 우리가 dequeue를 호출 때마다, 헤드 포인터는 다음 색인에 증가됩니다. 머리를 가서하려고하​​는 경우 그리고, 그 뒤로 0 루프. 그래서 그와 함께, 우리는 dequeue 함수를 쓸 수 있습니다. 우리는 너희들이 대신 구현하기위한 인큐 기능을 떠날거야. 

우리는 큐의 요소를 dequeue 때, 우리가 스택에 대한 팝업 기능을 쓰기 시작한 다니엘했던 처음하는 일이 무엇 이었습니까? 저 아직 말을하지 않은 사람의 말을 들어 봅시다. , 어디 한번 사드하자, 당신은 대니얼 그가 팝업 처음 쓴 것은으로 무슨 짓을했는지 기억하나요? [사드]가 발생했습니다되었다 - 그는 무언가에 대한 테스트 >>. [사드] 크기가 0보다 큰 경우. 정확히 >>. 그리고에 대해 해당 테스트는 무엇 이었습니까? [사드] 배열 내부 것이 있는지 확인하는 테스트 거예요. [Hardison] 그래. 그렇지. 이 비어 있다면 그래서 당신은 스택의에서 아무 열어 할 수 없습니다. 이 비어 있다면 마찬가지로, 당신은 대기열에서 아무것도 dequeue 할 수 없습니다. 우리 마을은 우리가 dequeue 함수에서 어떻게해야 가장 먼저는 무엇입니까, 당신 생각은? [사드] 크기가 0보다 큰 경우? >> 그래. 이 경우, 사실은 그냥 0 있는지 확인하기 위해 테스트되었습니다. 가 0 인 경우는 null 반환 할 수 있습니다. 그러나 동일한 논리. 그리고의이을 계속 보자. 크기가 0이 아닌 경우, 우리는 dequeue 할 요소는 어디 있죠? [사드] 머리에서? 정확히 >>. 우리는 우리 대기열의 첫 번째 요소를 뺄 수 머리에서 요소를 액세스하여. 미친 아무것도. 그 후, 우리는 어떻게해야합니까? 어떻게 무슨 일이 있나요? 우리가 dequeue에 대해 이야기하는 다른 것은 무엇입니까? 우리의 큐가 변경 되었기 때문에 두 가지가 일어날 수 있습니다. [다니엘]의 크기를 줄입니다. >> 우리는 크기를 줄일 수 있으며, 머리를 높일 수 있나요? 그렇지. 머리를 높이려면, 우리는 맹목적으로 기억 머리를 늘릴 수 없습니다. 우리는 queue.head을하지 못하는 + +. 우리는 또한 용량으로이 모드를 포함해야합니다. 그리고 왜 우리는 용량에 의해 스텔라 MOD 어떻게해야합니까? [스텔라]는 주변에 줄 바꿈하는 때문입니다. 정확히 >>. 용량에 의해 우리는 모드가 0에 다시 포장을해야하기 때문. 그래서 지금,이 시점에서 우리는 다니엘이 말을 할 수 있습니다. 우리는 크기를 감소 할 수 있습니다. 그리고 우리가 대기열의 맨 위에있는 요소를 반환 할 수 있습니다. 처음에는 밥맛 가지 보입니다. 당신은 질문이있을 수 있습니다. 뭐라고 요? 

[샘] 왜 큐의 상단에 처음이다? 그 어디가는 거지? [Hardison] 그것은 아래에서 네 번째 라인에서 제공합니다. 우리는 우리의 큐가 비어 있지 않도록 테스트 한 후 우리가 처음 숯불 *를 꺼내, 우리는 머리를 색인에 앉아 요소를 뽑아 우리의 배열, 우리의 문자열 배열, >>를 호출 첫 번째의? [Hardison] 우리는 처음 전화하십시오. 그래. 그에 따라, 당신은 왜 우리가 그 일을 할 수 밖에없는 생각합니까? [샘] 각 처음으로 단지 q.strings를 제공하고 있습니다 [q.head]? >> 그래. >> 우리가 모듈로 기능을 q.head이 변화하고 있어요 때문에, 또한 리턴 라인 내에서 해당 작업을 수행 할 수있는 방법은 없습니다. [Hardison] 그렇지. 당신은에 자리하고 있습니다. 샘은 완전히에 반점입니다. 우리는 큐의 첫 번째 요소를 꺼내 변수로를 저장하는 이유는,,, 우리가이 줄을 q.head 한 곳 때문입니다 거기에 모듈로 연산자는 우리가 할 수있는 뭔가가, 안 그래 그리고없이 머리에 적용했습니다 - 한 줄 인치 우리가 실제로 첫 번째 요소를 뽑아 내야하고, 머리를 조정 크기를 조정 한 다음 우리가 철수하는 요소를 반환합니다. 그리고 우리는 나중에 마련 볼 수 있습니다 왔던 것입니다 연결리스트, 우리는 그들과 주변 연주로. 당신은 연결 목록의 해방 또는 폐기하고 종종 때 당신은 다음 요소, 연결리스트의 다음 포인터를 기억해야 현재 하나 폐기 처분하기 전에. 때문에 그렇지 않으면 당신은 목록에 남아있는의 정보를 버린다. 귀하의 어플라이언스로 가면 이제,이 중 queue.c--X를 엽니 다. 제가 queue.c을 열고 경우, 나를 여기에 확대하게 당신이 비슷한 파일이 것을 확인할 수 있습니다. 우리가 stack.c과 이전에했던 일에 비슷한 파일입니다. 우리는 슬라이드에서 본대로 방금 정의한 대기열에 대한 우리의 구조체있어. 

우리는 당신 할 것입니다 우리의 인큐 기능을 갖추고 있습니다. 그리고 우리는 여기 dequeue 함수가 있습니다. 파일의 dequeue 함수는 unimplemented되고, 원하는 경우에 그것을 입력 할 수 있도록하지만 파워 포인트에서 다시 올려드립니다. 따라서 향후 5 분 정도를 들어, 너희들은 인큐에서 작동 이는 거의 단지 dequeue의 맞은 편에 위치해 있습니다. 당신이 enqueueing 때 머리를 조정할 필요는 없습니다,하지만 당신은 조정해야하나요? 크기입니다. 그래서 인큐, 머리는 손길이 닿지 않은 유지하면 크기가 변경됩니다. 그러나 약간의 시간이 걸립니까 - 그 모드들을 플레이해야합니다 새로운 요소가에 삽입해야하는지 인덱스 것인지 알아 내려고합니다. 그래서 너희들에게 조금주지, 슬라이드에 다시 dequeue를 넣어 그리고 사람들이 질문을 가지고, 그래서 우리가 할 수있는 그들을 큰소리 그룹으로 그들에 대한 모든 이야기. 또한 하지마 크기 - 당신은 크기를 조정했을 때, 당신은 항상 할 수 - 혹시 크기를 모드해야합니까? [다니엘] 번호 >> 당신은 크기를 MOD 오른쪽이 없습니다. , 당신은면의 크기는 항상 것입니다 - 가정 당신이 적절하게 물건을 관리하는 크기는 항상 0과 3 사이 여야합니다. 여기가 어디 인큐을 채취 할 때 MOD해야하나요? 만 머리에 [학생]. 만 머리에 >>, 맞아요. 그리고 왜 인큐에 전혀 MOD해야하나요? 때 MOD하는 수 밖에 없어요있는 상황입니까? 이 공간에 물건이 있으면 [학생], 공백 1, 2에 좋아 다음은 0에서 뭔가를 추가 할 필요가있었습니다. [Hardison] 네, 맞아요. 머리 포인터가 매우 끄트머리에 위치해 자한다면, 또는 크기 플러스 머리가 큰 경우, 또는 오히려 대기열 주위에 래핑 할 것이다. 

그래서 우리는 지금 슬라이드에 여기에있어 한 상황에서, 나는 지금 무언가를 인큐하려는 경우 우리는 인덱스 0에서 뭔가를 인큐하고 싶습니다. 당신은 50 어디로 가는지보고, 나는 인큐 50 전화면 그 아래에 내려갑니다. 이 인덱스 0에갑니다. 이미 dequeued 된 '안녕'을 대체합니다. [다니엘]이 (가) 당신이 이미 dequeue에 그 처리하지 마십시오? 왜 인큐의 머리를 짓입니까? [Hardison] 오, 그럼, 넌 머리를 수정하지, 미안 해요. 하지만 당신은에 액세스 할 때 모듈로 연산자를 사용해야합니다 당신이 액세스 할 때 인큐 할 요소 대기열의 다음 요소입니다. [바질] 그 짓도 안 했어, 그리고 난 거기에 "성공"을 가지고. [다니엘] 아, 난 당신이 무슨 말을하는지 알아. [Hardison]이 그래서 그냥 .. - 방금 q.size에서나요? [바질] 그래. 난 그냥면을 변경, 내가 머리를 아무 짓도하지 않았어요. [Hardison] 당신은 실제로 아무것도 할 머리를 재설정 할 필요가 없습니다 하지만 문자열 배열로 할 때 인덱스 당신은 실제로 가서 다음 요소가있는 곳 계산해야 스택을 실 가지로 묶다 때문에, 당신의 스택에있는 다음 요소는 항상 크기에 해당하는 색인​​에. 우리가 우리의 스택 푸시 기능에서 다시 만난다면 우리는 항상 오른쪽 인덱스 크기의 새로운 요소에 쿵하는 소리 수 있습니다. 대기열 반면, 우리는 할 수 없어 우리가이 상황에 있으면 때문에, 우리가 enqueued 경우 50 새로운 문자열은 문자열 [1]에서 오른쪽으로 갈거야 있는 우리는하고 싶지 않아요. 우리는 새로운 문자열 인덱스 0에 가서하길 원한다. 

않는 사람이 - 네? [학생] 내가 질문이 있지만 정말 관련이 없습니다. 누군가가 단지 pred 포인터 같은 것을 호출 할 때 무엇을 의미합니까? 그 이름이 무엇에 줄여서 그런 건가요? 나는 그냥 이름 알아. [Hardison] Pred 포인터? 어디 봅시다. 어떤 맥락에서? [학생]는 삽입하는 것은이었다. 당신이 원하는 경우 나중에 요청할 수 있습니다 정말 관련이 없습니다 만, 난 그냥 있기 때문에 - [Hardison] 강의에서 다윗의 삽입 코드에서? 우리는 그를 끌어와 그 부분에 대해 이야기를 할 수 있습니다. 우리는 다음, 일단 우리가 링크 된 목록에 도착에 대해 얘기하자. 

따라서 인큐 함수가 어떻게 생겼는지 살펴 정말 빠르게 까. 사람들이 귀하의 인큐 줄에 수행하려고하는 첫 번째 것은 무엇입니까? 이 대기열에? 당신이 밀어 스택에 무슨 짓을했는지와 유사합니다. 당신은 스텔라, 무슨 짓을 한거야? [스텔라, 이해할 수없는] [Hardison] 그렇지. (== 용량을 q.size) 경우 - 내가 그럴 권리가 장소에 내 괄호를 넣어해야 할 것은 - false를 반환합니다. 조금 확대합니다. 좋아요. 이제 우리는 짓을 할 수 밖에 없었던 그 다음은 뭐죠? 그냥 스택을 좋아하고, 그 장소에 삽입. 그리고 그렇게를 삽입 할 수있는 권리 장소는 무엇 이었습니까? 스택과는별로 그건이 일과, 색인 크기이​​었다. [다니엘] 내가 q.head - 또는이 - >>의 q.strings를? >> 그래. q.strings [q.head + q.size MOD 능력]? [Hardison] 우리는 아마도이 문제를 해결 괄호를 넣었 으면 좋겠어 우리는 모두에게 cleart 인 것 적절한 우선 순위를 받고 그래야. 그리고 그 같은 설정? 으로 str에게 >>? 으로 str에게 >>. 좋아요. 그리고 지금 우리가해야 할 것이 마지막이 뭐죠? 우리는 스택에 그랬던 것처럼. >>의 크기를 증가? >>의 크기를 증가. 붐. 그리고, 시작 코드부터, 그냥 기본적으로 false를 반환 우리 모두는지나 모두가 잘되면 true로를 변경하고 싶습니다. 괜찮아요. 해당 섹션에 대한 정보의 많은입니다. 우리는 상당히 이상하지. 우리는 단독으로 연결된 목록은 정말 빠르게 얘기하고 싶어요. 이를 놓을 게요 그래서 우리는 나중에 다시 이동할 수 있습니다. 그러나의 더 몇 슬라이드에 우리의 프리젠 테이션으로 돌아 가자. 따라서 인큐가 TODO이며, 이제 우리는 그것을 한 적이있어. 

이번에는 단독으로 연결된 목록을 살펴 보자. 우리는 강의에서이 조금 더 이야기. 우리가 사람들을 한 곳에서 몇 너희들의 데모를 본 어색 서로 홀딩 숫자를 가리키고? >> 난 그했다. >> 당신들은 어떻게 생각 했어? 그 짓을, 희망이 조금 demystify? 목록으로 우리가 우리가 노드에 전화를하고있는 이러한 유형의 처리을 이용할 수 있습니다. 대기열과 스택 반면 우리는 우리가 스택에 큐를 호출한다고 structs를했다 우리는 스택 타입의 새 큐를 가지고 여기에 목록이 단지 노드의 무리로 구성되어 있습니다. 문자열이 문자들 뿐이 것을 같은 방식으로 모든 서로 옆에 줄 지어. 연결리스트는 노드와 다른 노드와 다른 노드와 다른 노드입니다. 그리고 오히려 함께 모든 노드를 마쳤와 contiguously를 저장하는 것보다 메모리에 서로 바로 옆에 모두, 이 다음 포인터를 갖는 것은 우리가 무작위로, 노드 곳을 저장할 수 있습니다. 그리고 전선의 종류 다 함께 하나에서 다음을 가리 키도록. 

그리고이 배열을 통해 있다는 큰 장점 였죠? 저장 모든 걸 contiguously 서로 옆에 붙어? 기억 나? 응? >> 동적 메모리 할당? 어떤 의미에서 >> 동적 메모리 할당? 당신이 더 당신이 전체 배열을 이동 할 필요가 없습니다 만들기 유지할 수 있다는 점에서 [학생]? [Hardison] 그렇지. 따라서 배열로, 당신은 그것의 중간에 새로운 요소를 넣어하려는 경우, 당신은 공간을 만들기 위해 모든 이동해야합니다. 그리고 같은 우리는 대기열에 대한 이야기 우리가 헤드 포인터를 유지 거로군요 우리는 지속적으로 물건을 이동하지 않도록. 당신이 큰 배열이 있다면 그 돈이 정말 많이 들어 있기 때문에 그리고 당신은 항상이 무작위로 삽입을 다하고 있습니다. 목록 반면, 당신이해야 할 모든은 새로운 노드에 던져 is 포인터를 조정하면됩니다. 어떻게이 사실을 엿? 이외에도이 배열로 작동하도록 쉬운 일이 아닙니다 사실에서? 응? [다니엘] 글쎄, 난이 연결리스트의 특정 요소에 액세스하기가 훨씬 더 어렵 겠죠? [Hardison] 당신은 당신의 연결리스트의 중간에 임의의 요소로 바로 이동할 수 없습니다. 어떻게 대신해야합니까? 당신은 모든 게를 탐색해야합니다 >>. [Hardison] 그래. 당신은 한 번에 한, 한 번에 하나의 통과해야합니다. 그것은 거대한 - 이건 고통입니다. 다른 하나는 무엇입니까 -이 또 다른 몰락이 있어요. [바질] 당신은 앞으로 및 뒤로 갈 수 있습니까? 한 방향을 가야 해요? [Hardison] 그래. 그럼 우리는 때때로 그 해결합니까? [바질] 목록에게 이중 - 연결? 정확히 >>. 이중 - 링크 목록이 있습니다. 도 있습니다 - 뭐라고 요? 

[샘]이 그 pred 것을 사용과 동일합니다 - 난 그냥 기억, pred 것은 무슨 일 것을이 아닌 것은 무엇입니까? 저 사람 이중과 단독 사이에? 그가 무슨 짓을하는지 정확히에서 [Hardison] 가자의 모습. 그래서 여기에 우리가 이동합니다. 다음은 그 목록 코드입니다. 여기 우리가 여기에 predptr 있습니다. 당신이 무슨 말을하는지인가요? 그래서이 였어요 - 그 목록을 자유롭게 있고 그가에 대한 포인터를 저장하려고합니다. 이 이중, 단독으로 연결된 - 목록이 아닙니다. 이 이야기이기 때문에 우리는 목록을 해방에 대해 나중에이에 대한 자세한 내용을 이야기 할 수 그리고 처음 다른 물건을 보여주고 싶어. 하지만 그건 단지 - 이건 PTR의 가치를 내고 있잖아 [학생] 오, preceeding 포인터거야? >> 그래. 우리는 predptr가 무엇인지, 우리가 무료 전에 PTR 자체를 증가시킬 수 있도록. 우리는 무료 PTR 및 전화 PTR = PTR 다음, 그렇죠? 할 수 없으므로 그거 나쁜 것입니다. 그러니까이 남자에게, 어디 보자. 

목록에 대한 또 다른 나쁜 것은, 배열이있는 반면 우리는, 스스로가 서로 옆에 쌓여있는 모든 요소가 여기에 우리는이 포인터를 도입했습니다. 그래서 우리가 사용하는 데 메모리의 추가 덩어리가 있어요 우리 목록에 저장중인 모든 요소. 우리는 유연성을하지만 비용이 부과됩니다. 그것은이 시간 비용이 있습니다 그리고 너무이 메모리 비용이 함께 제공됩니다. 우리가 배열의 모든 요소를​​ 통과해야하는 의미에서 시간 색인 10시 하나 또는 그 배열에 인덱스 열 있었을 거라고을 찾으십시오. 

정말 빠르게 때 그림에서이 목록을 일반적으로 우리는 목록의 머리 나 목록의 첫 번째 포인터에 개최 그리고이 진정한 포인터됩니다. 단지 4 바이트입니다. 그것은 실제 노드 자체 없습니다. 그래서 그것에 int 값, 거기에 더 옆에 포인터를가 없음을 참조하십시오. 그것은 말 그대로 단지 포인터입니다. 그것은 실제 노드 구조체없는 일을 가리 키도록거야. [샘] 노드라는 포인터? >>입니다 - 안돼. 이 유형의 노드의 무언가에 대한 포인터입니다. 이 노드 구조체에 대한 포인터입니다. >> 아, 그래. 오른쪽에있는 왼쪽, 코드에 다이어그램. 우리는 시작하는 좋은 방법입니다 0,로 설정할 수 있습니다. 때 그림을, 그런 당신도 그 널 (null)로 작성하거나 그것을 통해 라인을 넣어. 

목록에서 작동 할 수있는 가장 쉬운 방법 중 하나는, 우리는, 당신은 모두 앞에 짓을 요청하고 둘 사이의 차이를 볼 수 추가 하지만 prepending는 확실히 쉽습니다. 어디에 당신이 앞에 때이입니다 - 때 앞에 (7) 당신은 노드 구조체에 가서 만들 당신은 지금 있기 때문에 그것을 prepended 때문에, 그것을 가리 먼저 설정 이 목록의 시작 부분에있을거야. 우리 다른 노드를 생성 앞에 (3), 지금 3 7 전에 온다면. 그래서 우리는 기본적으로 목록에 물건을 밀어하고 있습니다. 지금, 당신은 앞에은, 가끔 사람들이이 밀어 전화 것을 알 수 있습니다 때문에 귀하의 목록에 새로운 요소를 밀어하고 있습니다. 이 목록의 앞에 삭제도 간단합니다. 그래서 사람들은 자주 팝업을 호출합니다. 그리고 그 방법으로, 당신은 연결리스트를 사용하여 스택을 에뮬레이션 할 수 있습니다. 죄송합니다. 죄송합니다, 지금 우리는 추가로지고있어. 그래서 여기 우리 앞에 (3) 이제 (7) prepended. 만약 우리가 prepended 경우 우리는 (4),이 목록에 다른 일을 prepended, 그러면 우리는 4가 있으며 3 다음 다음 7 할. 그럼 우리가 나타나서 제거 3, 4를 제거 할 수, 7을 제거합니다. 종종이 생각하는보다 직관적 인 방법은 추가로 있습니다. 그래서 여기 추가로 모습을 무엇인지 diagrammed했습니다. 여기 추가 (7) 다를 보이지 않는다 때문에 목록에 하나의 요소가 있습니다. 그리고 첨부 (3) 끝을 넣습니다. 아마 당신은 지금 추가로 트릭을 볼 수 있습니다 즉, 목록의 시작 부분이 어디에은 알고부터입니다 이 목록을 통해 모든 방법을 걸어서 가야 목록에 추가 할 , 마지막까지 중지 한 다음 노드 아래로 쿵하는 소리 모든을 구축 할 수 있습니다. 모든 물건을 다 와이어. 그럼 앞에있는 것처럼 우리가 정말 빨리이 일을 냈 더라면 이 목록에 덧붙이 때, 상당히 간단합니다. 

당신은 새 노드를 일부 동적 메모리 할당을 포함한다. 그래서 여기에 우리가 malloc을 사용하여 노드 구조체를 만들고 있어요. malloc 그래서 그 이후에 우리 메모리를 따로 설정합니다 때문에 우리는 사용 우리가이 원하지 않기 때문에 - 우리는이 기억이 오랫동안 유지하고 싶습니다. 그리고 우리는 우리가 할당하는 메모리 공간에 대한 포인터를 얻을. 우리는 노드의 크기를 사용, 우리는 필드를 합계가 1이되지 않습니다. 우리는 수동으로 바이트 수를 생성하지 않습니다 대신에 우리는 우리가 바이트의 해당 번호를 알아내는 걸 알아요 있도록 sizeof 사용합니다. 우리는 우리의 malloc 호출이 성공하는지 테스트해야합니다. 이렇게하면 일반적으로하고 싶은 일입니다. 현대적인 기계에서 메모리가 부족하면 쉽게 일이 아닙니다 당신은 물건 톤을 할당하고 큰 목록을하지 않는, 하지만 아이폰이나 안드로이드 같은 말에 물건을 구축하는 경우, 당신은 강렬한 무언가를하고있는 경우 특히 당신은 제한된 메모리 자원을 가지고 있습니다. 그래서 연습에 들어가 두는 건 좋은 일입니다. 

여기 몇 다른 기능을 사용납니다 당신은 새로운 종류의가 있다고 보았 으니까. 따라서 fprintf 단지 printf처럼되어 있습니다 첫 번째 인자를 제외하고 인쇄 할 수있는 스트림입니다. 이 경우, 우리는 표준 오류 문자열로 인쇄 할 이는 표준 outstream 다릅니다. 기본적으로는 같은 장소에 나타납니다. 또한 터미널 출력,하지만 당신은 할 수 - 이러한 명령을 사용하면 약, 리디렉션 기술을 배웠습니다 이런 문제 세트 4 토미의 동영상에 대해 배웠습니다, 당신이 직접 할 수 있습니다 서로 다른 영역에, 다음 종료 프로그램, 여기 종료합니다. 그것은 메인에서 돌아처럼 본질적입니다 여기에 반환 아무 짓도 안하기 때문에 우리는 출구를 사용하는 경우를 제외하고. 우리는 메인에없는거야, 자, 재 우리가 원하는 것처럼 프로그램을 종료하지 않습니다. 그래서 우리는 출구 기능을 사용하고 그것을 오류 코드를 제공합니다. 그럼 여기서 우리는 전이어야 할 새 노드의 값 필드의 전 분야를 설정하고 우리는 그걸 송금. 우리는 먼저 가리 키도록 새 노드의 다음 포인터를 설정 그리고 처음에 이제 새 노드를 가리 킵니다. 코드의이 첫번째 라인은, 우리가 새 노드를 구축하고 있습니다. 이 함수의 마지막 두 줄하지만 최초로 없습니다. 당신은 실제로 도우미 함수로, 함수로 당겨 수 있습니다. 자주하는 일입니다 사실, 난 함수로 뽑아 나는 빌드 노드 같은 전화 그리고 그 앞에 함수가 아주 작은 유지, 그것은 불과 3 선 다음입니다. 내 빌드 노드 함수를 사용하여 전화를 걸하고 최대 I 와이어 모든. 

나는 당신에게 보여주고 싶은 마지막으로 한가지, 그리고 당신이 직접 추가 한 모든 작업을 수행 알려드립니다 목록을 통해 반복하는 방법은 다음과 같습니다. 목록을 통해 반복 이동하기 위해 다른 방법의 무리가 있습니다. 이 경우, 우리는 목록의 길이를 찾을거야. 그래서 우리는 길이 = 0로 시작합니다. 이 문자열을 나 strlen를 작성과 매우 유사합니다. 이것이 내가 여기에 루프이 당신을 보여 드리고자합니다. 그것은 약간 펑키 보이는, 그것은 일반적인 아닙니다 INT I = 0, 나는 <무엇이든, 내가 + +. 대신에이 목록의 시작 부분으로 우리 변수 n을 초기화있어. 우리 반복자 변수가 null이되지 않습니다 동안 그리고, 우리는 계속. 관례 상, 목록의 끝은 null 될 것 때문입니다. 그리고, 오히려 + +을하고보다 증가 +의 연결리스트로 이에 상응 + N = N-> 옆에 위치해 있습니다. 

우리가 시간이 있기 때문에 당신이 여기 메워 알려드립니다. 귀하의 spellr의 psets에서 작업하지만 기억해야합니다. 링크 된 목록, 당​​신은 해시 테이블을 구현하는 경우, 확실히 매우 유용합니다. 그리고 일을 통해 반복이 관용구를 갖는 것은 희망, 더 쉽게 생활을 할 것입니다. 질문 빨리? [샘] 당신은 완료 sll 및 SC를 보낼 수 있습니까? [Hardison] 그래. 나는 완료 슬라이드와 완료 sll 스택과 queue.cs을 보내드립니다. [CS50.TV]