ki hyun's 개발블로그

🔗 연결 리스트? 연결 리스트(linked list)는 객체가 선형적 순서를 가지도록 배치된 자료구조다. 인덱스에 의해 선형적 순서가 결정되는 배열과는 달리 연결 리스트에서는 각 객체에 있는 포인터에 의해 순서가 결정된다. 양방향 연결 리스트 key 속성값과 두 개의 포인터인 prev와 next를 속성값으로 가지는 객체다. 리스트의 원소 x가 주어질 때, x.next는 연결 리스트의 바로 다음 원소를, x.prev는 바로 직전 원소를 가리킨다. x.prev = NIL 이라면 이전 원소가 없으므로 이 리스트의 첫 번째 원소 또는 head라 한다. x.next = NIL 이라면 원소 x는 바로 다음 원소가 존재하지 않으므로 이 리스트의 마지막 원소 또는 tail이라고 한다. 단순 연결 리스트: prev 포인..

스택에서는 가장 최근에 삽입된 원소가 삭제된다. 즉, 후입선출 정책을 구현한 것이다. 큐에서는 집합에서 가장 오랜 시간 동안 존재한 원소가 삭제된다. 즉, 선입선출 정책을 구현한 것이다. 🗂 스택 스택에서는 스택에 값을 추가하는 연산을 Push, 인자를 값을 삭제하는 연산을 Pop이라고 한다. 💡 이때 Pop은 인자를 가지지않고 가장 최근에 삽입된 원소를 제거한다. 💡 이 연산들의 이름은 카페테리아 식당에서 스프링으로 접시를 받쳐 올려주는 접시 스택에서 유래된 것이라고 한다. 배열 S[1..n]으로 최대 n개의 원소를 가지는 스택을 구현할 수 있다. 배열은 가장 최근에 삽입된 원소를 가리키는 S.top을 속성값으로 가진다. S[1]은 스택의 맨 밑에 있는 원소를 나타내고 S[S.top]은 맨 위에 있는 ..