[자료구조] 스택(Stack)과 큐(Queue)
● 스택[Stack] : 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조
스택이란 프링글스의 과자를 위에서부터 꺼내 먹는 것처럼 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조를 말합니다.
위의 그림을 보면 empty stack에 새값이 하나씩 들어가고, 스택에서 값을 빼낼 때는 제일 위에 있던 값이 나오게 되는 것을 볼수 있다. 파이썬에서는 리스트를 이용하여 쉽게 스택을 구현할수 있다.
1. 스택의 특징
1. 후입선출은 삽입과 삭제가 한 쪽으로만 일어나는 특징을 가지고 있다.
2. 스택에서 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.
3. 파이썬에서 스택을 사용할때 별도의 라이브러리가 필요없다.
4. 깊이 우선 탐색[DFS], 백트래킹 등의 알고리즘에 주로 사용된다.
5. top위치 이외의 데이터에 접근할수 없기 때문에 탐색이 불가능하다.
2. 스택에서 사용하는 용어
1. top : stack에서 제일 위에 있는 위치, 즉 stack의 길이를 뜻함 (데이터의 입출력 위치)
2. bottom : 데이터가 0인 상태를 말하며, 즉 stack의 길이가 0인 상태
3. push : top의 위치에 데이터를 추가
4. pop : top의 위치에 데이터를 제거
5. LIFO (Last In First Out) : 시간적으로 제일 나중에 기록된 정보가 제일 먼저 처리되는 방식
3. 파이썬의 스택 연산
1. append() : top의 위치[가장 뒤쪽]에 새로운 데이터를 추가하는 연산
2. pop() : top의 위치에 데이터를 삭제하고 삭제된 데이터를 확인하는 연산
3. 스택[-1] : top의 위치에 있는 데이터를 확인하는 연산
4. if문 : 파이썬의 if문에서 empty list는 False를, empty가 아닌 list는 True를 리턴
4. 스택 문제
ㅇ
● 큐[QUEUE] : 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조
큐란 선착순으로 표를 나눠주는것 처럼 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO)로 이뤄지는 자료구조를 말합니다.
위의 그림을 보면 empty Queue에 새값이 하나씩 들어가고, 스택에서 값을 빼낼 때는 제일 처음 들어간 값이 나오게 되는 것을 볼수 있다. 그래서 Stack과는 다르게 삽입과 삭제가 양방향으로 이뤄지는것을 볼수 있으며, 일반적으로 파이썬에서는 deque를 이용하여 Queue를 구현한다.
1. 큐의 특징
1. 먼저 들어간 자료가 먼저 나오는 구조 특징을 가지고 있다.
2. 큐에서 데이터 삽입 삭제가 바로 이루어지기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.
4. 넓이 우선 탐색[BFS], 스트리밍 등의 알고리즘에 주로 사용된다.
2. 큐에서 사용하는 용어
1. Front : 큐에서 가장 앞의 데이터를 가리키는 영역
2. Rear : 큐에서 가장 뒤의 데이터를 가리키는 영역
3. put : Rear의 위치에 데이터를 넣는 것
4. get : Front의 위치에 데이터를 꺼내는 것
5. OverFlow : 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우
6. UnderFlow : 큐가 비어 있어 자료를 꺼낼 수 없는 경우
7. FIFO (First In First Out) : 시간적으로 제일 처음에 기록된 정보가 제일 먼저 처리되는 방식
3. 파이썬의 큐 연산
1. append() : Rear 위치에 새로운 데이터를 삽입하는 연산
2. popleft() : Front 부분에 있는 데이터를 삭제하고 확인하는 연산 [pop(0)을 사용하면 속도 이슈 발생]
3. 큐[0] : Front 부분에 있는 데이터를 확인하는 연산
4. 큐 문제
0
※ 순서와 관계없이 우선순위가 높은 데이터가 먼저 나오는 우선순위 큐도 있다.
List 자료형을 사용하는 큐의 한계
pop, insert 등의 함수를 사용하여 큐의 문제를 충분히 해결할수 있다. 그러나 list는 랜덤 액세스(random access)에 최적화된 자료 구조이기 때문에 데이터의 개수가 많아질수록 불리한 연산이다. 왜냐하면 pop(0)과 insert(0, x)의 연산을 리스트로 수행할때 O(N)의 복잡도를 가지고 있기 때문이다. 그러한 문제를 해결하기 위해 나온것이 Collections 모듈의 덱(deque) 라이브러리를 사용하거나 queue 모듈의 큐(Queue)
클래스를 사용하여 이러한 한계를 해결할수 있다.
[자료구조] 데크(Deque)
데크(Deque) : 앞ㆍ뒤 양쪽 방향에서 엘리먼트를 추가하거나 제거 보통의 큐(Queue)나 스택(Stack)의 경우 한방향으로 진행되지만 Deque의 경우 양쪽 방향으로 엘리먼트를 추가하거나 제거할수 있으며
sjm2449.tistory.com
참고서적