목차
1. 스택
2. 스택 그림으로 이해
3. 큐
4. 큐 그림으로 이해
5. 느낀점
알고리즘 공부를 하다보면 "스택을 이용해서 ..."이런 부분을 많이 듣게 된다.
앞으로 알고리즘 공부할 때 필요한 핵심적인 자료구조라고 생각한다.
스택과 큐의 개념은 그렇게 어렵지 않으니 그렇게 긴 포스팅이 될것 같지는 않다.
스택
스택은 자료구조의 일종으로 LIFO(Last-In-First-Out)라는 특징을 가지고 있다.
LIFO란, 마지막으로 들어온 데이터가 가장 먼저 나간다는 의미이다. 흔히 "후입선출"이라고 말한다.
파이썬에서는 리스트를 이용하여 스택을 표현할 수 있다.
알다시피 리스트는 한곳에서만 삭제와 삽입이 이루어지는데 이것이 스택의 특징이다.
- 스택은 DFS에서 재귀함수가 작동하는 원리와 같다고 봐도 무방하기에 여기서 개념을 확실하게 알아가야 한다.
스택 그림으로 이해
아래와 같은 스택과 저장할 데이터가 존재한다고 가정하자.
우리는 이 데이터를 순차적으로 스택이라는 자료구조에 넣을 것이다.
스택은 밑이 막혀있는 상자정도로 이해하면 된다.
A라는 데이터를 스택에 넣으면 아래와 같이 된다.
이 과정을 반복해 넣으면 이것이 스택에 데이터를 넣는 방식이다.
이런 식으로 스택에 데이터 C까지 넣었다.
이제 우리는 스택에서 데이터를 다시 빼내야 한다.
빼내는 과정을 알아보자.
이때 처음으로 빠지는 데이터는 마지막으로 들어온 데이터인 C가 빠지게 된다.
이 과정을 우리는 LIFO(Last-in-First-out)라고 부른다.
이게 바로 스택의 원리이다.
다음으로 큐에 대해 알아보자.
큐
큐 또한 자료구조의 일종으로 FIFO(First-in-First-Out)라는 특징을 가지고 있다.
FIFO란, 먼저 들어온 데이터가 가장 먼저 나간다는 의미이다. 흔히 "선입선출"이라고 말한다.
파이썬에서는 덱이라는 자료구조를 이용해서 큐를 표현할 수 있다.
덱은 내장메소드로 append(),pop() 뿐만 아니라 appendleft(),popleft()를 가지고 있어 큐의 기능을 할 수 있다.
- 큐는 BFS에서 자주 사용하므로 잘 알아두어야 한다.
큐 그림으로 이해
큐는 아래와 같이 양쪽이 뚫려있는 상자라고 생각하면 된다.
큐에 데이터를 넣을 때는 아래와 같은 방식으로 작동한다.
이 방식을 반복하는 것이 데이터가 큐라는 자료구조에 들어가는 방식이다.
즉, 데이터 C까지 반복해서 넣어주면 아래와 같이 된다.
여기까지는 스택과 다른 점이 없는 것 같다.
하지만 데이터에 접근 하는 부분에 있어서 스택과 다른 점이 생긴다.
데이터에 접근,삭제 하려고 할 때 아래와 같이 가장 먼저 들어온 A데이터가 빠지게 된다.
우리는 이런 방식을 FIFO(First-In-First-Out)라고 한다.
이게 바로 큐의 작동 원리이다.
느낀점
스택과 큐는 그렇게 어려운 개념은 아닌것 같다.
하지만 평소 코딩 문제에 접근을 할 때 스택과 큐를![]
많이 사용하고 LIFO,FIFO와 같은 원리 자체를 묻는 코딩 문제가 많이 존재하고 관련 알고리즘이 존재하기에 중요한 개념이라고 생각한다.
