DOUG 로이드 : 좋아, 당신이있어이 점 때문에 아마 꽤 익숙한 배열과 연결리스트와 두 가지 기본이되는 것입니다 데이터 구조 우리가했습니다 세트 유지에 대해 얘기 유사한 데이터 유형의 데이터를 조직했다. 이제 우리는 얘기거야 변화의 몇 가지에 대한 배열과 연결리스트에. 이 비디오에서 우리는거야 스택에 대해 이야기합니다. 특히 우리가 이야기하는거야 에 대한 데이터 구조는 스택이라고. 이전 토론에서 리콜 포인터와 메모리에 대한, 스택도입니다 메모리 세그먼트의 이름 정적으로 선언 된 경우 memory-- 메모리 당신을 당신의 이름을 변수, 이름, 등 등일과 기능 프레임있는 또한 우리 호출 스택 프레임이 존재한다. 그래서 이것은 스택 데이터 구조는 메모리가 아닌 스택 세그먼트. 그래. 

그러나 스택은 무엇인가? 그래서 그것은 단지를 꽤 많이있어 구조의 특별한 종류의 즉, 조직적인 방법으로 데이터를 유지한다. 그리고 두 개의 매우를있다 일반적인 방법은 구현하기 두개의 데이터 구조를 사용하여 스택 우리가 이미 잘 알고 있음, 배열과 연결리스트. 무엇 스택 특별하다 만든다 우리가 정보를 넣어하는 방법 스택, 그리고 그 길을 우리에 스택에서 정보를 제거합니다. 스택과 함께 특히 규칙은 가장입니다 최근에 추가 된 요소를 제거 할 수있다. 

이 스택의 경우 그래서 그것에 대해 생각합니다. 우리는 정보를 말뚝 박기있어 자체의 상단에, 상단 만 건 더미 제거 할 수 있습니다. 우리는 아래에있는 것을 제거 할 수 없습니다 다른 모든 때문에 붕괴 및 넘어. 그래서 우리는 정말 스택을 구축하고 그 우리는 조각으로 조각을 제거해야합니다. 이 때문에 우리는 일반적으로 참조 LIFO 구조로 스택에, , 첫 번째 아웃 지속됩니다. LIFO 먼저, 아웃 지속. 

그래서 때문에 이러한 제한에의 정보가 추가 될 수 있는지 와 스택에서 제거, 거기에 정말 두 가지가 우리는 스택과 함께 할 수 있습니다. 우리는 인, 푸시 할 수 있습니다 우리는 추가에 사용하는 용어 상단에 새로운 요소 스택, 또는 경우를 스택이 존재하지 않는다 우리는 처음부터 만드는 첫 번째 장소에서 스택을 생성 밀어 것입니다. 그리고 팝, 즉 CS의 일종 용어 우리는 가장 최근를 제거하는 데 사용할 스택의 상단에서 요소를 추가했다. 

그래서 우리는 모두에서 볼거야 구현, 모두 배열 기반 과 연결리스트 기반. 그리고 우리는 갈거야 기반 배열로 시작합니다. 그래서 여기의 기본적인 아이디어는 무엇 어레이 기반의 스택 데이터 구조 같을 것이다. 우리는 여기에 입력 된 정의가 있습니다. 그 내부에서 우리는 두 멤버가 구조 또는 필드. 우리는 배열을 가지고있다. 그리고 또 내가 사용하고 임의의 데이터 유형 값. 

그래서이 모든 데이터 유형이 될 수있다, INT의 문자 또는 다른 데이터 이전에 만든 입력합니다. 그래서 우리는 크기 용량의 배열을 가지고있다. 용량은 파운드, 상수 정의되는 아마 다른 곳에서 우리의 파일. 그래서이 특정 이미 알 우리가 경계하고 있습니다 구현 자신은 일반적이었다 어레이의 경우, 우리가 동적으로 크기를 조정할 수있는, 여기서 특정 숫자가있다 소자의 최대 우리는 우리의 스택에 넣을 수 있습니다. 이 경우에는 용량 소자이다. 

우리는 또한 추적 스택의 상단. 대부분의 어떤 요소 최근 스택에 추가? 그래서 우리는 추적 변수라는 상단에. 그리고이 모든 것이 함께 싸서됩니다 스택이라는 새로운 데이터 타입으로. 그리고 우리는 생성하고 나면 새로운 데이터 유형 우리는 그것을 같이 처리 할 수​​있다 다른 데이터 유형입니다. 우리는 같은 스택의를 선언 할 수 있습니다 우리는 INT의 X, 또는 문자 y를 할 수 있습니다. 그리고 우리는 스택 말할 때 들, 잘 무슨 일이 우리는 세트를 얻을 수있다 메모리는 우리를 위해 따로 설정합니다. 

이 경우, 용량 나는 분명히 결정했습니다 내가있어 때문에 10 형 스택의 하나의 변수 이는 두 개의 필드가 기억이 포함되어 있습니다. 이 경우 어레이는 것입니다 정수의 배열하는 로 내 대부분의 예제의 경우입니다. 그리고 또 다른 정수 변수 가기를 저장할 수있는, 가장 최근에 추가 된 스택 요소입니다. 그렇게 하나의 스택 우리 다만이 같은 모습을 정의했다. 그것은 포함하는 상자의 어레이 (10)의 어떤 이 경우 정수가 될 것이며, 녹색 거기에 또 다른 정수 변수 스택의 상단을 나타냅니다. 

의 상단을 설정하려면 스택 우리는 단지 s.top을 말한다. 즉, 우리가 접근 방법 구조 리콜의 필드. s.top 효과적으로 0 같음 우리의 스택이 작업을 수행합니다. 그래서 다시 우리는 두 가지 작업을 우리가 지금 수행 할 수 있습니다. 우리는 푸시 할 수 있습니다 우리는 팝업 수 있습니다. 의 푸시 시작하자. 다시, 새를 추가 추진 스택의 상단에 요소입니다. 

그래서 우리가 어떻게해야합니까 이 배열 기반 구현? 그럼 일반에 푸시 기능을 것입니다 동의해야합니다 스택 포인터. 이제 두 번째를 타고 그것에 대해 생각합니다. 왜 우리는 동의 할 것이다 스택에 대한 포인터? 에 이전 비디오에서 리콜 변수 범위와 포인터, 우리가 보낸 경우 무슨 일이 일어날 지 스택, 매개 변수로 오히려이야? 실제로 거기에 어떻게 전달 될 것인가? 우리가 복사본을 만드는 기억 우리는 함수로 전달 될 때 하지 않는 한 우리는 포인터를 사용합니다. 그리고이 기능은 요구를 밀어 스택 포인터를 수락 우리가 실제로 변화하고 있기 때문에 스택은 우리가 변경할 계획입니다. 

다른 것은 푸시 아마에 싶어 받아들이는 입력 값의 데이터 요소이다. 이 경우, 다시, 그 정수 우리는 스택의 상단에 추가 할 것입니다. 그래서 우리는 우리의 두 개의 매개 변수를 가지고있다. 우리는 무엇을하려고 지금 푸시 내부합니까? 음, 간단하게, 우리는 단지 추가거야 스택의 상단에 해당 요소 다음의 경우 상단을 변경 스택은 최고 값을 점이야입니다. 그래서 이것은 무엇 기능입니다 푸시에 대한 선언 에서처럼 보일 수 있습니다 배열 기반의 구현입니다. 

다시이 단단하고 빠른 규칙 아닙니다 당신은이를 변경 할 수 있음 그것은 다른 방법으로 다릅니다. 아마도 S는 전 세계적으로 선언된다. 그리고 당신도 필요하지 않습니다 이 매개 변수로 전달하는 것입니다. 이것은 다시 단지이다 푸시에 대한 일반적인 경우. 그리고 다른있다 방법을 구현합니다. 그러나이 경우 우리의 푸시은 걸릴 것입니다 두 개의 인수, 스택 포인터와 타입 값, 정수의 데이터 요소 이 경우에는. 

그래서 우리는 우리의 선언 s.top 0과 동일했다. 이제 밀어 보자 스택에 수 (28). 그럼 그게 무슨 뜻 이죠? 그럼 현재 스택의 상단은 0입니다. 그래서 무슨 일이 기본적이다 무슨 일이 일어날 것은 우리는 수를 스틱거야 배열 위치 0에 (28). 매우 간단, 오른쪽, 그 정상이었고, 지금은 갈 수 있어요. 그리고 우리는 무엇을 변경해야 스택의 상단이 될 것입니다. 다음 번에 ​​너무 우리는의 요소를 밀어 우리는 그것을 저장하는거야 배열 위치, 아마 0. 우리는 덮어 쓰기를 원하지 않을 우리는 단지 거기에 무엇을 넣어. 그래서 우리는 단지 상위 1로 이동합니다. 그건 아마 의미가 있습니다. 

이제 우리는 다른 요소를 넣어하려는 경우 스택에, 우리는 (33)를 밀어하고 싶은 말은 물론 지금 우리는 단지 33을거야 및 배열 위치 번호에 넣어 (1) 다음의 상단을 변경 우리 배열 위치 두 번째로 스택. 그래서 다음에 경우 우리는 원하는 스택에 요소를 밀어 그것은 배열 위치 2에 넣을 수 있습니다. 그리고 이제 그 한 번 더하자. 우리는 스택 오프 (19)를 밀어 것입니다. 우리는 배열 위치 2 (19)를 놓을 게요 우리의 스택의 상단을 변경 배열 위치 3되어야한다 그래서 우리는 다음의 경우, 우리가 갈 수 있어요 푸시를 확인해야합니다. 

좋아, 그럼 그 한마디에 밀어입니다. 무엇 터지는 어떻습니까? 그래서 터지는는의 일종이다 추진에 대응. 그것은 우리가 스택에서 데이터를 제거하는 방법은 다음과 같습니다. 그리고 일반 대중의 요구에 다음을 수행합니다. 이 포인터를 수용해야 일반적인 경우에 다시 스택. 다른 경우에 당신은 수도 전 세계적으로 스택을 선언, 이 경우 당신은 그것을 통과 할 필요가 없습니다 때문에 그것을 이미 액세스를 보유 글로벌 변수로. 그러나 다른 그 다음 우리가 어떻게해야합니까? 그런데 우리는 증가 하였다 푸시의 스택의 상단 그래서 우리는 아마 원하는거야 스택의 상단을 감소하기 팝, 오른쪽? 그리고 물론 우리는 또한 원하는거야 우리가 제거 값을 반환합니다. 우리는 요소를 추가하는 경우, 우리는 원하는 나중에 요소를 얻으려면, 아마 실제로 우리 그들을 우리가 저장할 단지에서 삭제하지 않습니다 스택 다음 그들과 함께 아무것도 할 수 없습니다. 일반적으로 우리가하는 경우 밀고 여기 터지는 우리는이를 저장할 의미있는 방식으로 정보 그리고 그것은하지 않습니다 의미는 폐기합니다. 따라서이 기능은해야 아마 우리에게 값을 반환합니다. 

그래서 이것은 대중에 대한 어떤 선언이다 왼쪽 상단에이 같을 수 있습니다. 이 함수가 반환 입력 값의 데이터. 다시 우리는 사용하고 정수에 걸쳐. 그리고 스택으로의 포인터를 받아 단독 인수 또는 유일한 매개 변수입니다. 그래서 팝은 할거야? 의 우리가 지금하고 싶은 말은하자 S 떨어져 요소를 팝업. 그래서 스택이 마지막이다라고 기억 첫 번째 아웃, LIFO 데이터 구조에. 어떤 요소 것은 가고있다 스택에서 제거? 당신은 19을 생각 했습니까? 당신은 잘 될 것 때문입니다. 19 우리가 추가 된 마지막 요소였다 우리가 요소를 밀어 때 스택, 그리고 그것은 최초의 것 제거됩니다 요소입니다. 우리가 28 말했다 것처럼, 그리고 우리는, 그 위에 (33)를 넣어 우리는 그 위에 (19)을 넣어. 우리가 이륙 할 수있는 유일한 요소는 19입니다. 

지금 여기 그림에 내가 무슨 짓을했는지 종류의 배열에서 19 삭제됩니다. 그건 사실이 아니에요 우리는 무엇을 할 것입니다. 우리는 종류에가는거야 의 그것이없는 척. 그것은 거기에 아직 그 메모리 위치, 그러나 우리는 그냥 무시하는거야 우리의 스택의 상단을 변경하여 3 대 2 인에서. 우리가 있었던 경우에 따라서 지금 밀어 스택에 다른 요소, 그것은 이상 (19)을 작성합니다. 

그러나의가없는 문제를 통해 가자 스택에서 19 삭제. 우리는 그냥이없는 척 수 있습니다. 스택의 목적은 경우에 사라 졌어요 우리는 2 대신 3로 정상을 변경합니다. 그래, 그게 꽤 많이했을 정도로. 즉, 우리가해야 할 전부입니다 요소를 팝업합니다. 이제 다시 해 보자. 그래서 나는 여기에 빨간색을 강조했습니다 우리가 다른 통화를하고 나타냅니다. 우리는 같은 일을 할 것입니다. 

그래서 무슨 일이 일어날? 음, 우리는 저장거야 X 33과 우리는거야 1 스택의 상단을 변경합니다. 우리가 밀어 지금이라면 있도록 우리가있어 스택에 요소 지금 할 거, 무슨 일이 일어날 것 우리는 덮어 쓰기려고하고있다 배열 위치 번호 1. 종류의 왼쪽 된 그 33 있도록 그 뒤에 우리는 단지 척 더 이상 거기, 우리는거야 그것을 소지품 대신 거기에 40을 넣어. 그리고 물론, 우리가 푸시를 만든 이후, 우리는을 증가거야 1-2 스택 맨 그래서 우리는 지금 추가하는 경우 그 다른 요소는거야 배열 위치 두 번째로 이동합니다. 

이제 연결리스트는 또 다른입니다 스택을 구현하는 방법. 그리고에이 정의 경우 화면은 여기, 당신에게 익숙 거의 보인다 때문입니다 똑같은 사실, 그것은 거의 정확하게이다 단일 연결리스트와 같은, 당신은 우리의 토론에서 기억하는 경우 단독으로 다른 비디오 목록을 연결. 여기에 유일한 제한 프로그래머로서 우리를 위해입니다 우리는 허용하지 않을 삽입하거나 임의로 삭제 단일 연결 목록에서 우리가 이전 할 수있다. 우리는 지금 삽입에서 삭제할 수 있습니다 전면 또는 링크의 상단 목록. 그것은 정말로 단지이다 차이가 있지만. 이것은 달리 단일 연결 목록입니다. 그것은 단지 제한있어 자신에 교체 프로그래머로서 그 스택으로 변경됩니다. 

여기서 규칙은 항상 유지하는 것이다 연결리스트의 헤드 포인터. 물론 이것은 일반적이다 첫 번째 중요한 규칙. 단독으로 당신에게 목록을 어쨌든 연결을 위해 오직 헤드 포인터를 필요 것을 갖기 위해 체인은 참조 할 수 다른 모든 요소에 링크 된 목록. 그러나 특히이다 스택 중요합니다. 그래서 일반적으로 당신이있어 실제로 원하는 것 이 포인터는 글로벌 변수가 될 수 있습니다. 그것은 아마 것 더 쉽게 그 방법이 될 수. 그래서 푸시와 팝의 유사체는 무엇인가? 권리. 그래서 다시 밀어 추가하고있다 스택에 새로운 요소입니다. 링크 된 목록에서 그 우리가 할 겁니다 의미 우리가있어 새 노드를 만들 수 있습니다 링크 된 목록에 추가 할 것, 다음주의 단계를 수행 우리는 이전에 설명했다고 단일 연결 목록에 그것을 추가하려면 체인을 깨지 않고 체인 및 손실 또는 orphaning 연결리스트의 요소. 그리고 기본적으로 무슨이다 텍스트의 작은 덩어​​리가 요약되어 있습니다. 그리고 이제 살펴 보자 다이어그램으로는시. 

그래서 여기에 우리의 링크 목록입니다. 그것은 동시에 네 개의 요소가 포함되어 있습니다. 그리고 더 완벽하게 여기에 우리의있어 네 가지 요소를 포함하는 스택. 그리고 이제 우리가 지금하고 싶은 말은하자 이 스택에 새로운 항목을 누릅니다. 그리고 우리는 새로운 밀어 싶어 그 데이터 값 항목은 12입니다. 그런데 우리가 무슨 말을하는 건가요? 그럼 먼저 우리는 갈거야 동적 malloc에​​ 공간, 새 노드에 대한 공간을 할당합니다. 그리고 물론 직후 우리는 항상 우리를 malloc을하기 위해 전화를 걸 , 널 (null)를 확인해야합니다 우리가 널 가지고있는 경우 때문에 문제의 어떤 종류가 있었다. 우리는 널 역 참조하지 않으려는 포인터 또는 당신은 SEG 오류를 겪게 될 것이다. 그 좋지 않다. 그래서 우리는 노드의 malloc으로 할당했습니다. 우리는 우리가 여기에 성공 했어 가정합니다. 우리는로 (12)를 넣어거야 해당 노드의 데이터 필드. 지금 당신은 기억합니까 우리의 포인터의 어느 그래서 우리는 체인을 중단하지 않는 다음 이동? 우리는 여기에 몇 가지 옵션을 가지고 있지만 안전 할 것 하나 포인터 다음에 뉴스를 설정하는 것입니다 목록의 이전 머리에 포인트 또는 곧 될 것입니다 무엇 목록의 이전 머리. 그리고 지금의 모든 것을 우리의 요소는 서로 연결되어, 우리는 단지 가리 목록을 이동할 수 있습니다 새가하는 같은 장소에. 그리고 우리는 지금 효과적으로 추진해 왔습니다 스택의 전면 상에 새로운 요소. 

우리 팝 단지 원하는 그 첫 번째 요소를 삭제합니다. 그래서 기본적으로 무엇을 우리는 여기에서해야 할 물론 우리는 두 번째 요소를 찾을 수있다. 결국 그 새로운 될 것 우리는 첫 번째를 삭제 한 후 머리. 그래서 우리는 단지에서 시작해야 시작은, 하나 앞으로 이동합니다. 우리는 하나 파악을했으면 여기서 우리의 앞으로 현재 우리가 안전하게 첫 번째를 삭제할 수 있습니다 다음 우리는 단지 머리를 이동할 수 있습니다 무엇을 가리 키도록 이제 다음 두 번째 항과 그 후 첫 번째입니다 노드가 삭제되었습니다. 

그래서 다시 살펴 본다 그것에 다이어그램으로 우리 지금 팝업 할 이 스택의 오프 요소입니다. 그래서 우리는 무엇을해야합니까? 그럼 우리가 처음 만들거야 무슨 새로운 포인터 머리와 동일한 지점을 가리 키도록. 우리는 그것을 하나의 위치를​​ 이동거야 앞으로 TRAV의 등호를 말하여 예를 들어 다음 트래비스하는 TRAV 포인터를 전진 것이다 앞으로 위치. 지금 우리가 가지고있는 첫 번째 요소에 개최 포인터라는 목록 및 관통 라는 포인터를 통해 두 번째 요소 TRAV, 우리는 안전하게 그것을 삭제할 수 있습니다 스택에서 첫 번째 요소 나머지를 잃지 않고 체인의 우리 때문에 참조하는 방법이 두 번째 요소에 의 방법에 의해 전달 포인터 TRAV을했다. 

그래서 지금 우리는 그 노드를 확보 할 수 있습니다. 우리는 목록을 확보 할 수 있습니다. 그리고 우리가 지금 할 필요가있다 같은 장소에 지점으로 목록으로 이동 그 TRAV는 않습니다, 우리는 뒷면의 일종이야 우리는 (12)을 밀어 전에 우리가 시작했던 곳 처음에에 오른쪽. 우리가 있었던 곳은 정확히이다. 우리는이 네 가지 요소 스택을했다. 우리는 다섯 번째를 추가했습니다. 우리는 다섯 번째를 밀어 요소에, 그리고 우리 팝이 가장 최근에 백 오프 요소를 추가했다. 

즉 거의 정말 모든 스택을 할 수있다. 당신은 배열로 구현할 수 있습니다. 당신은 연결리스트로 구현할 수 있습니다. 다른 하나는, 물론있다 방법뿐만 아니라이를 구현합니다. 우리가 사용하는 것이 기본적 이유 스택은 이러한 방식으로 데이터를 유지하는 것이다 가장 최근에 추가하는 요소는 우리가있어 제일 먼저 돌아 가야 할 것. 내가 더그 로이드 해요,이 CS50입니다.