[기초 알고리즘 #02][선형 자료구조] 스택 / 큐 / 덱
자료구조는 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있습니다.
선형 자료구조는 자료를 연속적으로 연결한 형태를 갖춘 자료구조입니다.
대표적으로 스택(Stack) / 큐(Queue) / 연결 리스트 (Linked List) 등이 있구요.
비선형 자료구조는 말 그대로 비연속적으로 연결하며, 트리(Tree) / 그래프(Graph) 등이 대표적입니다.
프로그래밍을 한다는 것은, 구현하는 기능에 따라서 상이하겠지만, 주어진 자료를 잘 구조화 하고 이를 잘 사용해내는 것 부터 시작 한다고 할 수 있습니다.
그렇기 때문에 많은 개발자 지망생들이 자료구조와 알고리즘을 공부하고 있는 것이겠죠 🤣
이번 게시글은 선형 자료구조의 얼굴, 스택(Stack) / 큐(Queue) / 덱(Deque) 에 대해서 알아보겠습니다.
1. 스택 (Stack)
냉장고에 캔음료를 안쪽부터 꽉채워 넣었다고 생각해봅시다.
다시 냉장고문을 열고 음료수를 꺼낼 때, 가장 마지막에 넣은 캔음료를 꺼내들게 되겠죠?
이게 스택입니다.
나중에 들어간 데이터가 먼저 나온다.
스택은 후입선출(LIFO, Last-in First-out) 원칙에 따라 동작하는 자료구조입니다.
대표적으로, 함수를 호출하는 과정에서 메모리에 적재될 때, 혹은 괄호가 잘 열리고 닫혔는지를 판단하는 알고리즘을 구현할 때, 스택의 개념이 활용됩니다.
이러한 원칙과 개념은 자료구조라기 보다는 ADT라고 보는게 맞습니다.
지난 게시글에서 ADT에 개념에 대해 훑어보았는데요, 스택 자료구조의 ADT에 대해서 한번 엿보자면…
이렇게 되겠습니다~
스택은 후입선출 원칙에 따르기 때문에,
아무래도 나중에 들어간 데이터를 (특정한 상황에) 먼저 빼내야 하는 알고리즘 을 구현할 때 사용하게 되겠죠?
push()와 pop()을 적극 활용해서요 😁
⚫ 연습해볼 수 있는 문제
2. 큐 (Queue)
큐는 선입선출(FIFO, Firts-in First-out) 원칙에 근거합니다.
공연장에 먼저 온 사람이 먼저 입장하는 그런 느낌!
BFS 알고리즘을 구현할 때도 사용되는 유용한 자료구조입니다.
바로 ADT 보겠습니다.
front는 큐 자료구조의 가장 앞에 있는 데이터의 위치 index를 뜻합니다.
rear는 큐 자료구조의 가장 뒤에 있는 데이터의 위치 index를 뜻하구요.
값을 넣으면 enqueue(), rear는 증가하고,
값을 빼면 dequeue(), rear는 감소하게 되겠습니다.
⚫ 연습해볼 수 있는 문제
- 백준 10845 큐 » 링크
3. 덱 (Deque, Double-Ended-Queue)
스택과 큐는 삽입과 삭제를 제한했습니다.
스택은 반드시 top() 위치에 값을 넣고 뺄 수가 있었고,
큐는 반드시 front와 rear 위치에서만 값을 넣고 뺄 수가 있었습니다.
덱은 이런 제한에서 벗어나 보다 자유롭게(?) 데이터를 삽입/삭제하기위해 스택과 큐의 특징을 모두 합친 자료구조 입니다.
앞뒤로 push(), pop()이 모두 가능하다는 이야기 입니다.
⚫ 연습해볼 수 있는 문제
⚫ 참고 자료
- 자료구조의 개념과 종류. 한빛출판네트워크. https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS2832062046
댓글남기기