[PART3] 데이터베이스/자료구조 - TERMS 05

[ TERMS 05 ]  스택/큐

스택과 큐를 설명하는 이미지(출처 : https://gohighbrow.com/stacks-and-queues/)

 

1. 스택(Stack)/큐(Queue)의 정의

 스택과 큐는 개발할 때 접하는 기본적인 자료 구조이다. 자료 구조는 컴퓨터에서 데이터(자료)를 구성하는 방법이다.

 

2. 스택/큐는 어디서 접하게 될까?

 스택과 큐는 최근 개발자가 치르는 코딩 테스트를 준비할 때 꼭 알아야 하는 개념이다. 선형 자료 구조 유형에서 이 두 가지 개념을 활용한 문제를 많이 풀게 된다. 또한 프로그래밍 언어를 공부할 때 메모리 그림이 자주 나오는데 스택과 큐의 개념을 잘 알고 있어야 프로그래밍 언어의 특징을 이해할 수 있다.

컴퓨터 메모리에서 stack 활용(출처 : https://lovemesomecoding.com/data-structure-algorithm/data-structure-algorithm-memory)

 

3. 스택/큐 알아보기

>  스택

• 개념

 위키백과에서는 스택을 '제한적으로 접근할 수 있는 나열 구조'라고 정의했다. 원론적인 개념이 아닌 실제 현실에서의 사례를 활용하여 설명하자면, 추운 겨울이 되면 옷을 여러 겹을 껴입는다. 히트텍을 입고, 맨투맨을 입고, 패딩을 입는 것이 바로 스택의 Push 작업이다. 외출에서 돌아와서는 두꺼운 패딩부터 하나씩 벗는데 이 과정은 Pop이라고 부를 수 있다. 이후 편한 옷으로 다시 갈아입을 때 Push 작업이 일어나는 것이다. 옷을 갈아입을 때는 가장 마지막에 입은 두꺼운 패딩부터 벗어야 하듯 스택은 한쪽 끝에서 Push와 Pop 작업이 일어난다.

스택을 설명하는 이미지 (출처 : https://open4tech.com/stacks-vs-queues/)

위의 그림 왼쪽처럼 박스를 가장 위에 쌓고(Push) 다시 빼내는(Pop) 모습이 있는데 이와 같은 구조를 'LIFO(Last In First Out)'라고 한다. 가장 마지막에 'Push'한 것을 가장 먼저 'Out'한다는 개념이다. 반대로 생각하면 가장 먼저 Push한 것을 가장 나중에 Out하는 'FILO(First In Last Out)'라고도 할 수 있다. 이렇게 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료 구조이다.

 

• 스택의 예

 스택의 가장 대표적인 예는 크롬 브라우저이다. 인터넷을 사용하는 도중 중간중간 '뒤로 가기' 버튼을 클릭하며 작업할 때가 있다. 이처럼 인터넷을 하다가 뒤로 가기 버튼을 누르면 클릭하면 바로 이전 작업으로 돌아가게 되는데, 이 원리가 스택이다. 가장 최근에 검색한 창이 스택의 가장 위에 나타나고 그곳에서 뒤로 가기 버튼을 클릭하면 가장 위에 있던 것이 Pop되면서 바로 이전에 작업했던 창으로 돌아간다. 이렇게 순간적으로 Push와 Pop 작업이 계속 일어난다. 워드나 한글 프로그램을 이용할 때 작업을 취소하거나 이전 작업으로 복구하는 'Ctrl + z' 단축키도 스택을 이용해서 바로 이전 작업으로 복구될 때 순간적으로 Pop이 일어난다.

 

• 스택의 활용

 개발을 할 때 스택과 관련해서 '메모리'라고 부르는 그림을 자주 보게 된다. 프로그래밍을 할 때 값들을 보통 변수에 저장하는데 이 때 스택이라는 상자에 값을 넣고 이름을 붙인다. 이렇게 컴퓨터의 기억 공간이라고 불리는 메모리의 한 부분이 스택으로 이루어져 있다.

 

>  큐

• 개념

 위키백과에서는 큐를 '먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식'이라고 정의했다. 앞서 설명한 스택과는 반대 개념이다.

큐를 설명하는 이미지 (출처 : https://open4tech.com/stacks-vs-queues/)

 

• 큐의 예

 하루 계획을 세울 때 보통 어떤 일들을 할지 시간순으로 생각을 한다. 이 일들을 순차적으로 큐라는 자료 구조에 넣어서 Push하고, 하나씩 활동할 때는 Pop하여 수행하는 원리이다. 큐의 원리는 은행 창구와 같다. 은행에 가면 대기표를 뽑고 차례가 될 때까지 대기한다. 사람들이 하니씩 번호표를 뽑아갈 때 번호표가 Push되고, 창구에서 번호가 호출되면 번호표가 큐에서 Pop되어 은행 업무를 볼 수 있게 된다.

조금 더 확장해서 우선순위 큐를 알아보자면 응급실에 순차적으로 여러 상처를 입은 환자들이 들어오는데, 심각한 상처를 입은 환자가 뒤늦게 들어올 수 있다. 원칙상으로는 들어온 순서대로 환자를 치료해야 하지만 위독한 환자는 우선순위를 부여하여 먼저 치료해야 하는 경우가 생긴다. 이것이 큐에 들어 있는 특정 데이터에 우선순위를 부여해서 처리하는 우선순위 큐의 원리이다.

 

• 큐의 활용

 큐는 프린터 출력이나 컴퓨터에서 일을 순차적으로 처리할 때 활용한다. 키보드로 타이핑하면 그 작업이 모두 큐에 들어가서 차례대로 실행된다. 가끔 컴퓨터가 먹통이 되었을 때 무심결에 키보드를 여러 번 치는 경우가 있는데, 컴퓨터가 정지해 있다가 나중에 하나씩 천천히 처리된다. 이는 키보드로 입력한 작업이 큐에 들어갔다가 하나씩 나오면서 처리되는 것이다. 마찬가지로 인터넷이 네트워크를 통해 접속될 때도 그 내부에서는 명령들이 큐에 들어갔다가 나와서 실행된다.

 

>  스택과 큐 비교하기

 지금까지 스택과 큐의 기본 개념과 예를 알아보았다. 스택과 큐를 간단히 비교하자면, 스택은 나중에 Push한 데이터가 가장 먼저 Pop되는 LIFO(Last In First Out) 자료 구조이고, 큐는 가장 먼저 Push한 데이터가 가장 먼저 Pop되는 FIFO(First In First Out) 자료 구조이다.

 

4. 스택/큐를 알아야 하는 이유

 프로그래밍 언어의 실행 흐름을 제어하는 '콜 스택'이라는 메모리가 있다. 이름에서도 알 수 있듯이 스택이라는 개념을 알아야 프로그래밍 언어의 동작 원리를 제대로 이해할 수 있다. 또 여러 작업을 한 번에 처리할 수 없을 때 대기열이 필요한데 이때 사용되는 것이 큐이다. 큐를 알아야 코드 작업 순서를 이해할 수 있다.

 

5. 스택/큐 더 알아보기

>  함께 알아 두면 좋은 용어

• 메모리
• 변수
• 콜 스택

 

>  혼동하기 쉬운 용어

• 스택과 힙
• 선형/비선형 자료 구조