[WEEK02] 스택(Stack)과 큐(Queue) + Collections.deque

[Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬]  + [이것이 취업을 위한 코딩테스트다] 
+ [Introduction to Algorithms] 개념 정리

1. 스택 (Stack)

: 데이터를 임시 저장할 때 사용하는 자료구조

: 접시 쌓기에 비유할 수 있음

: 후입 선출 (Last In First Out)

: 스택 사용시 "별도의 라이브러리를 사용할 필요 없음" => 기존 리스트로 사용하면 됨

: 스택에 데이터를 넣는 작업을 푸시(push) / 데이터를 꺼내는 작업은 팝(pop)

: append() : 리스트 가장 뒤쪽에 데이터를 삽입

: pop() : 리스트 가장 뒤쪽에서 데이터를 꺼냄

: 윗부분 - top / 아랫부분 - bottom

용어정리

stk

: 스택배열 (list형 배열)

 

capacity

: 스택 최대 크기 (= len(stk))

 

ptr (스택 포인터)

: 스택 포인터 (비어 있을 시 ptr = 0 / 가득 차 있을 시 ptr = capacity)

 

2. 큐 (Queue)

: 데이터를 임시 저장할 때 사용하는 자료구조

: 대기 줄에 비유할 수 있음

: 선입 선출 (First In First Out)

: 큐에 데이터를 넣는 작업 - 인큐(enqueue) / 데이터를 꺼내는 작업 - 디큐(dequeue)

: 데이터를 꺼내는 쪽을 front(head) / 데이터를 넣는 쪽을 rear(tail)

: collection 라이브러리의 deque를 활용하여 큐를 구현함 (리스트 자료형에 비해 효율적, 큐 라이브러리에 비해 간단)

: deque를 사용하면 deque객체가 나오는데 리스트 자료형으로 변환하기 위해서는 list method를 활용하면 됨

 

배열로 큐 구현하기

인큐 : 처리의 복잡도는 O(1)

디큐 : 삭제 후 모든 원소를 앞 쪽으로 옮겨야함 ⇒ 처리의 복잡도는 O(n)

 

링 버퍼(ring buffer)로 큐 구현하기

: 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조

: 프런트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아님

: 원소를 옮길 필요없이 front와 rear 값을 업데이트 하는 것만으로 인큐와 디큐 수행 가능

: 모든 처리의 복잡도는 O(1)

 

3. Collections.deque

: 맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입, 삭제할 수 있는 자료구조

: 두개의 포인터를 사용하여 양쪽에서 삭제, 삽입을 할 수 있으며, 큐와 스택을 합친 형태

: collections 모듈의 deque 컨테이너 (python 내장 container)

: collections.deque는 빠르고 프로그램이 간단함 (but, 자료구조를 배우려면 FixedStack Class를 이해할 필요가 있음)

주요 속성

1) maxlen 속성 : deque의 최대크기

2) append( )   : 맨 끝에 추가

3) appendleft( ) : 맨 앞에 추가

4) clear( ) : 모든 원소 삭제

5) copy( ) : shallow copy

6) extend(iterable) / extendleft(iterable) : iterable의 원소를 끝에 추가하여 확장

7) index(x[, start[, stop]]) : deque 안에 있는 x 가운데 가장 앞쪽 원소의 위치를 반환

8) insert(i, x) : deque i 위치에 x를 삽입

9) pop( ) : 맨 끝 원소 1개 삭제

10) popleft( ) : 맨 앞 원소 1개 삭제

11) remove(value) : value 첫번째 항목 삭제

12) reverse( ) : deque 원소를 역순으로 재정렬 

13) rotate(n=1) : 모든 원소 n 만큼 오른쪽으로 밀어냄 

자료형과 deque의 비교

	리스트	deque	명령어
가장 앞쪽에 원소 추가	O(N)	O(N)	appendleft( )
가장 뒤쪽에 원소 추가	O(1)	O(N)	append( )
가장 앞쪽에 있는 원소 제거	O(N)	O(N)	popleft( )
가장 뒤쪽에 있는 원소 제거	O(1)	O(N)	pop( )

: 큐 자료 사용시에는 append( )로 삽입하고 popleft( )로 삭제하면 됨

: 리스트 자료형과는 다르게 indexing, slicing 등의 기능은 사용할 수 없음