스택, 큐, 연결 리스트, 추상 자료형

스택(Stack)은 LIFO이므로 마지막에 넣은(push) 원소가 먼저 빠진다(pop). 큐(Queue)는 FIFO이므로 먼저 넣은(enqueue) 원소가 먼저 빠진다(dequeue). 단일 연결 리스트(singly linked list)는 보통 next만 있어 뒤로 순회하거나 임의 인덱스에 직접 접근할 수 없다. 추상 자료형(ADT)은 값·연산·행동을 정하는 것이며 구체적 구현(concrete implementation)이나 실행시간 표 자체가 아니다.

스택의 push·pop은 보통 \(O(1)\)O(1)이다. 큐의 enqueue·dequeue는 원형 배열 또는 front/rear 연결 리스트 구현에서 보통 \(O(1)\)O(1)이다. 연결 리스트에서 값 탐색·인덱스형 접근은 \(\Theta(n)\)Θ(n)이고, 위치를 이미 알고 있을 때 포인터 갱신으로 하는 삽입·삭제는 \(O(1)\)O(1)이다.

문장에 beide, jedes, direkt, nur, typischerweise, konkrete Implementierung이 나오면 용어와 숨은 전제를 먼저 표시한다.

2025년 여름학기(SoSe 2025) 복원 객관식의 섹션 I과 II이다.

이 단원 문제는 계산보다 단어 함정이 중요하다. LIFO·FIFO, 단일·이중 연결, ADT·구현, 그리고 '이미 알고 있는 포인터(known pointer)' 같은 전제어를 먼저 확인해야 한다.

정답 문장을 외우는 대신 각 선택지가 ADT 수준의 주장인지 구현 수준의 주장인지 분리해 변형 객관식(altered MC)도 판정하도록 훈련한다.

스택(Stack)은 접시 더미와 같다. 위에 올린 것을 위에서 먼저 꺼낸다. 큐(Queue)는 줄과 같아서 먼저 선 사람이 먼저 나간다. 연결 리스트(linked list)는 배열처럼 칸 번호로 바로 뛰어가는 구조가 아니라, 노드가 다음 노드를 가리키는 길이다. ADT는 '메뉴판'이고 구현(implementation)은 '주방 설비'다.

스택 ADT(Stack ADT)는 new, isEmpty, push, pop을 제공하고 후입선출(LIFO)을 만족한다. 큐 ADT(Queue ADT)는 new, isEmpty, enqueue, dequeue를 제공하고 선입선출(FIFO)을 만족한다. 단일 연결 리스트(singly linked list, einfach verkettete Liste)의 각 원소는 다음 원소를 가리키는 next 포인터를 가지지만 이전 원소를 가리키는 prev 포인터는 없다. 이중 연결 리스트(doubly linked list, doppelt verkettete Liste)는 next와 prev를 모두 가져 앞뒤 순회가 가능하다. 추상 자료형(ADT, abstrakter Datentyp)은 가능한 값과 연산 및 행동을 설명하며, 배열인지 리스트인지 같은 저장 방식은 별도의 구현 문제다.

• 원소 삽입 순서와 제거 순서를 작은 예시로 추적할 수 있어야 합니다.
• next 포인터와 prev 포인터의 차이를 알아야 한다.
• \(O(1)\)O(1)과 \(\Theta(n)\)Θ(n)의 차이를 '입력 크기에 따라 비용이 변하는가'로 판단할 수 있어야 한다.

스택 불변식(Stack invariant)에 따르면 pop은 아직 제거되지 않은 원소 중 가장 최근에 push된 원소를 반환한다. 큐 불변식(Queue invariant)에 따르면 dequeue는 아직 제거되지 않은 원소 중 가장 오래전에 enqueue된 원소를 반환한다. 단일 연결 리스트는 현재 노드에서 next 방향으로 갈 수 있지만 prev 포인터나 보조 정보 없이는 뒤로 갈 수 없다. 같은 큐 ADT도 원형 배열(circular array), 단일 연결 리스트 또는 두 스택(two-stack) 방식 등 여러 구현을 가질 수 있다.

강의 03의 실행시간 표에서 스택의 push·pop과 큐의 enqueue·dequeue는 보통 \(\Theta(1)\)Θ(1)이다. 연결 리스트에서 값 탐색은 \(\Theta(n)\)Θ(n)이며 인덱스처럼 임의 위치에 곧바로 접근하는 것은 기본 직접 연산이 아니다. 이미 알고 있는 노드·위치에서 삽입·삭제는 \(\Theta(1)\)Θ(1)일 수 있지만, 값이나 이전 노드를 찾는 데는 \(\Theta(n)\)Θ(n)이 들 수 있다. 단일 연결 노드는 prev가 없으므로 이중 연결 노드보다 포인터 저장 공간이 적다.

빈 스택이나 큐에서 pop 또는 dequeue를 하면 명세에 따라 언더플로(underflow)나 오류가 발생한다. enqueue(x) 직후 dequeue()가 x를 반환하는 것은 enqueue 전에 큐가 비어 있었을 때뿐이며, 그렇지 않으면 더 오래된 맨 앞 원소가 먼저 나온다. 단일 연결 리스트 끝에 추가하는 비용은 표현 방식에 따라 달라서 tail 포인터가 있으면 \(O(1)\)O(1)이지만 head 포인터만 있으면 순회가 필요할 수 있다. 또한 이미 알고 있는 노드를 삭제하는 것과 값으로 삭제하는 것은 다르며, 값으로 삭제하려면 이전 노드를 찾아야 할 수 있다.

• beide
• jedes
• direkter Zugriff
• nur dann
• typischerweise
• konkrete Implementierung
• einfach
• doppelt
• ohne Entfernen

2026년 강의의 연결 리스트 알고리즘은 주로 이중 연결 리스트 연산을 보여 주지만, Sheet05는 단일 연결 리스트를 명시적으로 묻는다. 단일 연결 리스트에 관한 주장은 해당 연습문제와 공식 풀이를 직접 근거로 삼는다.

스택 = LIFO, 큐 = FIFO. 단일 연결 리스트 = next만, 이중 연결 리스트 = next + prev. ADT는 행동 계약이며 메모리 배치가 아니다.

스택 push·pop은 \(O(1)\)O(1), 전형적인 front/rear 구현의 큐 enqueue·dequeue는 \(O(1)\)O(1), 연결 리스트 탐색·인덱스형 접근은 \(\Theta(n)\)Θ(n), 위치를 안 뒤 포인터 삽입·삭제는 \(O(1)\)O(1)이다.

enqueue(x) 뒤 dequeue()가 x를 반환하는 것은 이전에 큐가 비어 있었을 때뿐이다. tail 포인터가 없으면 단일 연결 리스트 끝에 추가할 때 순회가 필요할 수 있다.

원소 두 개의 추적을 쓰고 node(value,next)를 그린 뒤, 문장이 ADT 수준인지 구현 수준인지 표시한다.