스택, 큐, 덱

1) 스택(Stack)

- 데이터를 접시쌓듯이 차곡차곡 쌓는다 

- 맨 마지막에 들어온 데이터 먼저 차출됨(LIFO) 선입후출

- FILO(First In Last Out)구조로 삽입과 삭제 연산이 동일한 한군데에서 발생

- 삽입/삭제 연산에 있어 시간복잡도가 O(1)

- 이전에 활용한 데이터를 역으로 추적하거나 처음 들어온 데이터보다 나중에 들어온 데이터가 빨리나갈 때 사용

- List의 pop() 을 활용하면  Stack처럼 사용할 수 있음

- Python에서 LifoQueue라는 구현체가 있음

- 활용예시: 브라우저 뒤로가기 앞으로가기, 깊이 우선 탐색(DFS)

# 스택 직접 구현

class Stack(list):

	push = list.append
    
    def peek(self): # 가장 마지막에 있는 데이터를 보여줌(엿보다) 추출x
    	return self[-1] # 인덱스 넘버 가장 마지막
        	self[len(self) -1] #렌 함수로도 구현 가능
            
 -- pop()은 peek함수에서 가져가는 작업 추가
 스택에서 제일 마지막에 넣은 데이터를 추출하는 함수
 python 내장함수로 가지고 있음

 

2)  큐(Queue)

- 일이 처리되기를 기다리는 리스트

- FIFO(First In First Out)구조,  삽입과 삭제 연산이 서로 다른 한군데에서 발생

- 삽입/삭제 연산에 있어 시간복잡도가 O(1)

- front: 맨 처음에 들어온 데이터/ rear: 맨 마지막에 들어온 데이터

- 주로 순차적으로 진행되어야 하는 일을 스케줄링 할 때 사용됨.

- Python에서 Queue라는 구현체가 있음

- 활용 예시: 프린터 인쇄 대기열, 너비우선탐색(BFS)

• 1) empty() : Boolean 타입
  2) is_full() : 큐가 가득 찼으면 T, 아닌 경우 F
• 3) enqueue(data) : 큐 맨 뒤에 데이터 삽입
  4) dequeue() : 큐 맨 처음 데이터 삭제하면서 해당 데이터 반환
• get
  5) peek() : 큐의 맨 처음 데이터 값을 삭제없이 반환(추출x)

 

※리스트를 큐처럼 사용하는 것은 안됨

리스트 주소값을 갖고 있어 w

# 직접 구현

class Queue(list)
	
    put = list.append
    
    def peek(self):
    	return self[0] # 가장 앞에 있는 데이터 보기
        
  	def get(self):
    	return self.pop(o) # pop에 파라미터 주면 해당 인덱스 값 추출

 

3) 덱(Deque)

- Queue와 Stack의 구조를 합친 것. 양쪽에서 삽입/삭제 할 수 있음

- 순서대로 처리해야 하는 일을 수행할 때, 제거해야 하는 위치가 맨끝이 아닐 때

 

from collections import deque *덱을 사용하기 위해 import

dq = deque() 
dq = deque('12345')

dq.append(6) # 오른쪽에 데이터 저장
dq.appendleft(0) # 왼쪽에서 진행하는 연산은 left를 붙임

removed = dq.pop()
print(removed)
removed = dq.popleft()
print(removed)

dq.rotate(1)
dq.rotate(-2)

코딩테스트에서는 주로 스택과 덱을 사용