이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
두 가지 항목 저장 방식
- 스택(stack) 과 큐(queue) 은 모두 항목들의 줄(line)을 유지하지만, 어떤 항목이 먼저 나올지에서 차이가 있습니다.
- 스택은 LIFO: Last In, First Out — 접시 더미(pile of plates)와 같습니다.
- 큐는 FIFO: First In, First Out — 사람 줄(people line)과 같습니다.
스택은 LIFO입니다
- push는 항목을 맨 위에 더합니다. pop은 맨 위(top) 항목을 제거하여 반환합니다. peek은 제거하지 않고 맨 위 항목만 봅니다.
- 마지막으로 push한 항목이 가장 먼저 pop됩니다.
- 항목들은 배열
data와 내부 개수를 세는 인덱스top에 저장됩니다.
배열 기반 스택(array-backed stack)
top가 개수(count)라면, 맨 위(top) 항목은data[top - 1]에 위치합니다.- push:
data[top]에 쓰기, 이후top++. pop:top--, 이후data[top]반환. - (이 작업들에서는 배열이 충분히 커서 '차고 있음'을 확인할 필요가 없습니다.)
큐는 FIFO입니다
- enqueue는 항목을 뒤에 추가합니다. dequeue는 앞의 항목을 제거하여 반환합니다.
- 첫 번째로 enqueue된 항목이 가장 먼저 dequeue됩니다.
- 두 개의 인덱스를 유지합니다:
front(나갈 차례인 next to leave)와back(다음 빈 슬롯 next free slot).
배열 기반 큐(array-backed queue)
- enqueue:
data[back]에 쓰기, 이후back++. dequeue:data[front]읽기, 이후front++, 그리고 이를 반환합니다. - 항목이 들어오고 나감에 따라
front가back을 쫓아갑니다. - (이 작업들에서는 배열 크기가 충분히 커서 원형(wrap around)이나 '빈(empty)' 상태 검사는 필요 없습니다.)
흔한 실수
- 스택은 last-in-first-out이고, 큐는 first-in-first-out입니다.
- pop하거나 dequeue하기 전에 구조체가 비어 있지 않은지 확인하십시오.
이제 직접 해보기
Stack와Queue구조체는 스타터에 이미 제공되어 있습니다.s->top,q->front, 그리고q->back를 사용하십시오.main을 작성하지 마십시오—체크기가 하나 제공합니다.
탐색하기
스택과 큐
스택은 LIFO이며, 큐는 FIFO입니다. 연산 단계를 따라가십시오.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
Stack 구조체(data과 개수 top 포함)가 주어졌습니다. void push(Stack *s, int v)과 int pop(Stack *s)을 완성하여 스택이 LIFO로 작동하도록 하십시오. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
Stack 구조체가 주어졌습니다. int peek(const Stack *s)을 완성하여 최상단 요소를 제거하지 않고도 반환하십시오. 스택이 비어 있지 않다고 가정하십시오. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
Queue 구조체(data, front, back 포함)가 주어졌습니다. 큐를 FIFO로 만들기 위해 void enqueue(Queue *q, int v)와 int dequeue(Queue *q)를 완성하십시오. 반드시 main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.