큐(Queue) 와 스택(Stack) 자료구조

큐와 스택은 문제를 해결하면서 굉장히 많이 사용하는 자료구조이다.

 

큐(Queue)

큐는 먼저 들어온 원소가 가장 먼저 나간다는 특징이 있다. 이러한 특징을 FIFO(First-In First-Out) 이라고 한다.

큐에 원소가 들어가는 것을 인큐(enqueue) 라고 하고, 반대로 나가는 것을 디큐(dequeue)라고 한다.

 

예를들어, [1, 2, 3, 4] 라는 데이터를 큐에 담고 뺀다고 해보자

• 1을 넣는다. => queue: 1
• 2를 넣는다. => queue: 1, 2
• 값을 뺀다. => 1이 나온다. => queue: 2
• 3를 넣는다. => queue: 2, 3
• 4를 넣는다. => queue: 2, 3, 4
• 값을 뺀다. => 2가 나온다. => queue: 3, 4
• 값을 뺀다. => 3이 나온다. => queue: 4

 

스택(Stack)

스택은 큐와 다르게 가장 늦게 들어온 원소가 가장 먼저 나간다는 특징이 있다. 이러한 특징을 LIFO(Last-In First-Out)이라고 한다.

스택에서는 값이 들어올때는 푸쉬(push), 나갈때는 팝(pop) 이라고 한다.

 

예를들어, [1, 2, 3, 4] 라는 데이터를 큐에 담고 뺀다고 해보자

• 1을 넣는다. => stack: 1
• 2를 넣는다. => stack: 1, 2
• 값을 뺀다. => 2가 나온다. => stack: 1
• 3를 넣는다. => stack: 1, 3
• 4를 넣는다. => stack: 1, 3, 4
• 값을 뺀다. => 4가 나온다. => stack: 1, 3
• 값을 뺀다. => 3이 나온다. => stack: 1

 

큐와 스택을 이용해서 팰린드롬(회문) 찾는 알고리즘을 만들 수 있다. (아래 글 참고)
2020/03/28 - [Algorithm] - 회문, 팰린드롬(Palindrome) 알고리즘 (with Python3)

정리

큐

• First-In First-Out
• enqueue: 값을 넣는다.
• dequeue: 값을 뺀다.

스택

• Last-In First-Out
• push: 값을 넣는다.
• pop: 값을 뺀다.

 

큐와 스택을 이용해서 탐색 알고리즘 DFS, BFS 을 구현할 수 있다. 2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3)

Reference

• https://thebook.io/006935/part04/ch13/01-01/