[알고리즘 자료구조] 스택(Stack)과 큐(Queue)는 뭘까?
- 2022-12-30 14:26
- SW마에스트로
SW마에스트로 연수생이 되기 위해선
꼭 거쳐야 할 하나의 관문이 있죠...
바로바로 코딩테스트!
SW마에스트로 지원,
IT 취업, 원하는 동아리에
지원 등의 여러 분야에서
기본기를 테스트하는 수단으로
많이 사용되기 때문에 이미
많은 분들이 준비하실 거예요.
대표적으로 알고리즘 문제를
많이 보게 되실 텐데 이때
꼭 참고해야 할 점은
좋은 알고리즘을 위한 필수 조건에
좋은 자료 구조가 있다는 거예요.
그래서 오늘은 알고리즘과
자료구조를 주제로
기본적 자료구조 중 하나인
스택과 큐에 대해 알아봐요 :)
우선 스택에 대해 알아보죠.
스택(stack)이란 가장 대표적인
선형 자료구조 중에 하나로,
데이터를 하나씩 쌓아 올린
형태의 자료구조예요.
스택은 '가장 먼저 들어온 데이터가
가장 마지막에 나가는 자료구조'라고
요약을 할 수 있어요.
그림을 보면 뭔가 '탑' 같지 않나요?
후입선출 구조(LIFO)는
가장 나중에 들어온 게 가장 먼저
나간다는 말로 Last in First Out을
말하거든요?
예를 들면,
우리가 종이컵을 쌓아놓고 쓸 때
가장 나중에 쌓아놓은 종이컵을
제일 먼저 사용하게 되죠?
이런 것처럼 스택에서는
가장 나중에 들어온 데이터가
제일 먼저 나가요.
또 이처럼 스택에 데이터가 들어오는
연산을 삽입(push) 연산이라 하고
데이터가 나가는 연산을 삭제(pop)
연산이라고 부르니 참고해 주세요.
이 연산들이 리스트의 한쪽에서만
진행되는 게 스택의 다른 특징이에요.
그럼 우리는 스택을 어디서 활용할까요?
보통 스택을 실행 취소(undo) 할 때,
웹 방문 기록을 볼 때,
혹은 뒤로 가기를 할 때 사용해요.
가장 늦게 들어온 데이터가
가장 먼저 나가게 된다는 게
확 와닿으시죠?
또한, 역 문자열을 만들거나
*후위 표기법을 계산할 때,
*재귀적 알고리즘 등을 만들 때
사용한다는 거!
*후위 표기법: 연산자를 연산 대상의
뒤에 쓰는 연산 표기법, 1 + 2를 1 2 +로 쓰는 것.
*재귀적: 자신을 정의할 때,
자기 자신을 재창조하는 방법
이렇게 배운 스택, 직접 구현해 봐요!
C++에서 스택은 표준 라이브러리에
있기 때문에 직접 구조를 짜지 않아도
#include <stack>을 통해 stack이
들어있는 헤더 파일을 선언하여
사용할 수 있어요.
아까 말했던 것처럼,
데이터를 넣는 것은 push,
데이터를 삭제하는 걸 pop.
데이터를 넣고 싶다면,
스택의이름.push(넣을 데이터)를 하고
스택의이름.pop()을 하면 알아서
제일 나중에 들어간 데이터가
삭제 처리가 됩니다.
push와 pop말고도 가장 나중에
들어간 데이터를 출력해 주는 top(),
스택의 크기를 출력해 주는 size(),
스택이 비어있는지 알려주는
empty() 등의 연산이 있어요.
큐 역시 스택과 같은
선형 자료구조 중에 하나로,
스택과는 반대로 가장 먼저 들어온
데이터가 가장 먼저 나가는 형태의
자료구조예요. 아예 반대로 알면 돼요.
그림을 보면 뭔가 터널 같지 않나요?
터널이라고 생각하면 좀 더 편하실 거예요 :)
선입선출 구조란 말은,
가장 먼저 들어온 데이터가
가장 먼저 나가는
FIrst in First Out을 의미해요!
스택과 반대죠?!
예를 들면,
우리가 카페에 가서 주문하고 기다릴 때,
먼저 들어온 손님이
먼저 음료를 받고 나가잖아요?
이런 거라고 생각하시면 돼요 ㅎㅎ
또한, 큐에 데이터가 들어오는 것은
push 연산 혹은 Enqueue 연산,
데이터를 빼는 것은 pop 연산
혹은 Dequeue 연산이라고 합니다.
이런 연산이 스택처럼
한쪽에서만 실행되는 것이 아니라,
한쪽에서는 데이터가 들어오고,
한쪽에서는 데이터가 삭제되는 연산을
각각 수행한다는 점이
큐의 가장 큰 특징이에요!
그럼 큐는 어디서 활용할까요?
큐는 보통 우선순위의 예약,
프로세스 관리 등에 사용해요.
또한 은행 업무에서도 사용해요!
어떤 거냐면,
우리가 은행에 가서 번호표를 뽑으면
그 순서에 맞게 업무가 이루어지잖아요?
내가 먼저 들어왔는데
나보다 늦게 들어온 사람이
먼저 업무를 보는 일은 거의 없어요.
이때 이러한 상황을 큐로 치환하면
내가 번호표를 뽑는 것은 Enqueue,
내 차례가 돼서 창구에 가는 것은
Dequeue라고 볼 수 있어요.
대기손님이라는 Queue에
우리가 들어가게 되는 거죠.
또 *너비 우선 탐색 (BFS) 알고리즘에 사용돼요!
*너비 우선 탐색 알고리즘: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
큐 역시, C++ 기본 라이브러리에 있어서
#include <queue>를 통해 큐가
들어있는 헤더 파일을 포함해 주면
바로 사용할 수 있어요.
큐에 데이터를 넣는 연산 즉 Enqueue는
큐이름.push(넣을 데이터)로 할 수 있고
데이터를 삭제하는 연산 즉 Dequeue는
큐이름.pop()을 통해 할 수 있어요!
이외에도
큐가 비어있는지 알려주는 empty(),
큐의 맨 앞 원소를 반환해 주는 front(),
맨 뒤 원소를 반환해 주는 back() 등이 있어요!
오늘은 이렇게 알고리즘과 자료구조를
주제로 스택과 큐에 대해 알아보았는데요.
스택과 큐, 처음에 들었을 땐
저게 무슨 단어야 싶었지만
지금은 좀 감이 오시죠?
이제 스택과 큐 마스터했으니
알고리즘 문제 풀이하러 가봅시다!