Stack
a pile of things arranged one on top of anotherStack이 지닌 의미입니다. 뜻 그대로 어떤 물체를 다른 것 위에 차곡차곡 쌓아 놓은 더미를 의미합니다. 게임을 하신 분이라면 좀 더 친근하게 와닿습니다. 캐릭터가 능력을 발휘하기 위해 특정 동작을 여러 번 반복하는 행위를 '스택을 쌓는다'라고 표현합니다. 이처럼 데이터를 차곡차곡 쌓아 올린 자료구조를 stack이라고 부릅니다.
Stack은 다음 그림처럼 밑이 막혀 있는 상자에 똑같은 구조와 크기를 가진 상자 A, B, C, D를 넣는 것과 같습니다. 상자를 A, B, C, D 순서대로 넣으면 그대로 쌓입니다. 상자를 꺼낼 때는 D, C, B, A 순서로 꺼낼 수 있습니다. 이런 구조를 LIFO Last-in, First-out 구조라고 합니다.
Stack이 사용되는 다음과 같은 예시를 생각해 볼 수 있습니다.
- ⊙ 실행 취소: 취소 단축키(Ctrl + z)는 가장 마지막에 실행된 동작부터 차근차근 취소합니다.
- ⊙ 접시 꺼내기: 찬장 안 쌓아놓은 접시를 꺼낼 때 가장 위에서부터 하나씩 꺼낼 수 있습니다.
- ⊙ 뒤로 가기: 웹 브라우저의 뒤로 가기 버튼은 가장 마지막에 열린 페이지로 되돌아갑니다.
Queue
a line of people, usually standing or in cars, waiting for something
Queue가 지닌 의미입니다. 간단히 사람들이 서있는 줄을 연상할 수 있습니다. 커피를 주문하기 위해 줄을 서면 가장 먼저 온 사람부터 차례대로 순서를 기다립니다. 이처럼 데이터가 들어가는 입구와 나가는 출구가 다른 자료구조를 queue라고 부릅니다.
Queue는 다음 그림처럼 위, 아래 모두 뚫려 있는 상자에 똑같은 구조와 크기를 가진 상자 A, B, C, D를 넣는 것과 같습니다. 상자를 A, B, C, D 순서대로 넣으면 그대로 쌓입니다. 상자를 꺼낼 때는 들어간 A, B, C, D 순서대로 꺼낼 수 있습니다. 이런 구조를 FIFO First-in, First-out 구조라고 합니다.
Queue는 다음 그림처럼 위, 아래 모두 뚫려 있는 상자에 똑같은 구조와 크기를 가진 상자 A, B, C, D를 넣는 것과 같습니다. 상자를 A, B, C, D 순서대로 넣으면 그대로 쌓입니다. 상자를 꺼낼 때는 들어간 A, B, C, D 순서대로 꺼낼 수 있습니다. 이런 구조를 FIFO First-in, First-out 구조라고 합니다.
Queue가 사용되는 다음과 같은 예시를 생각해 볼 수 있습니다.
- ⊙ BFS Breadth First Search 구현: 매 단계 깊이의 노드들을 순서대로 대기열에 넣고 들어온 순서대로 탐색합니다.
- ⊙ 스타벅스 DT: 자동차를 타고 줄을 서서 먼저 온 순서대로 커피를 주문하고 받아갑니다.
- ⊙ Sungrid engine qsub: qsub 명령어를 실행하면 queue 대기열에 들어간 순서대로 명령어를 실행합니다.
마지막으로 Stack vs Queue를 비교한 자료화면을 보며 마치겠습니다.
