알고리즘 이론 : 스택/큐

_플레이데이터 빅데이터캠프 알고리즘 수업  + 개인 공부 내용 정리

알고리즘 이론 : 스택/큐

- 가장 기본. 여러 곳에서 쓰인다.

1. 스택

1. 스택 자료구조

: 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조.

: 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조

 

2. 스택의 구조

LIFO(Last-In, First-Out) 후입선출

: 스택은 시간 순서에 따라 자료가 쌓여서

가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조적인 특징을 가지고 있다.

 

3. 대표적인 내장 함수

- push : 스택에서 삽입하는 연산.

- peek : 가장 마지막에 넣은 데이터을 조회하는 연산. (확인만하고 가져가지 않는다.)

- pop : 가장 마지막에 있는 데이터를 꺼내는 연산. 삭제하는 연산.

 

4. PYTHON 스택의 구현 방법

일반적으로 자료 구조를 구현하는 방법에는

1) 직접 구현, 2) 이미 구현된 클래스 import, 3) List를 스택으로 구현 이 세 가지 방법이 있다.

그러나, 파이썬의 경우 내장된 리스트가 스택으로 활용될 수 있도록 잘 구현이 되어있기에

==> 직접 구현 방법만을 사용한다.

 

1) 직접 구현 방법

- pop은 list의 내장함수로 이미 존재하기 때문에 만들 필요 없다.

class Stack(list):

    push = list.append # 리스트 append 함수처리가 push와 일치하기 때문에 
    def peek(self):
        return self[-1] # 가장 마지막 값을 얻어야 하므로 음수인덱스 -1
        
s = Stack()
s.push(1)
s.push(5)
s.push(10)

# pop 원소 추출
print("my stack is",s) # [1,5,10]
print("popped value is :", s.pop()) # 10
print("my stack is",s) # [1,5]

# peek 원소 조회
# 마지막 원소 조회만. 추출하는 건 아님.
print("peeked value is:",s.peek()) # 5

 

 

2) List를 스택으로 구현

# 파이썬 리스트를 스택으로 활용
s = []

# push
s.append(1)
s.append(5)
s.append(10)
print(s) # [1,5,10]

# pop
print(s.pop()) # 10
print(s) # [1,5]

# peek
print(s[-1]) # 5
print(s) [1,5]

 

5. 스택의 활용

1) 브라우저. ( 뒤로, 앞으로 가기 기능. 새로운 페이지를 여는 기능)

페이지가 스택에 들어가는 요소이며, 이때 2개의 스택이 필요하다.

prev 스택 : 뒤로 가기에 사용하는 스택

next 스택 : 앞으로 가기에 사용하는 스택

 

세가지 경우, 상황으로 나눠 설명할 수 있다.

- 새로운 페이지 접속 시, prev 스택에 기존의 페이지를 push하고, next 스택은 비웁니다.

- 뒤로 가기 버튼을 누르는 경우, 현재의 페이지는 next 스택에 push 하고, prev 스택의 top 페이지를 pop하여 가져옵니다.

- 앞으로 가기 버튼을 누르는 경우, 현재 페이지를 prev 스택에 push 하고, next 스택의 값을 pop합니다.

 

2) 깊이 우선 탐색(DFS)

 

2. 큐

1. 큐 자료구조

: 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조.

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

: 놀이동산에서 줄을 서서 기다리는 것처럼 먼저들어온 자료가 먼저 나가는 자료구조를 말합니다.

 

2. 큐의 구조

FIFO(First-In, First-Out) 선입선출

: 한쪽에서 삽입과, 삭제가 이루워지는 스택과 달리

삭제연산만 수행되는 곳과, 삽입연산만 수행되는 곳으로 나뉘어져 있습니다.

 

3. 대표적인 내장 함수

- put : 스택에서 데이터를 넣는 연산.

- peek : 가장 먼저 넣은 데이터를 조회하는 연산. (확인만하고 가져가지 않는다.)

- get : 가장 먼저 넣은 데이터를 꺼내는 연산. 삭제하는 연산.

 

4. PYTHON 큐의 구현 방법

일반적으로 자료 구조를 구현하는 방법에는

1) 직접 구현, 2) 이미 구현된 클래스 import, 3) List를 스택으로 구현 이 세 가지 방법이 있다.

 

1) 직접 구현 방법

class Queue(list):
	put = list.append   # append와 동일한 처리
    def peek(self):
    	return self(0)  # 가장 앞에 있는 데이터를 보기 위해 인덱스 0 조회
    def get(self):
    	return self.pop(0)
        
q = Queue()

# put
q.put(1)
q.put(5)
q.put(10)
print(q)

# get
print(q.get()) # 1
print(q) # [5,10]

# peek
print(q.peek()) # 5
print(q) # [5, 10]

 

2) 파이썬 구현된 클래스 import

from queue import Queue # 1번처럼 queue 클래스 만든 필요 없음.

q = Queue()
q.put(1)
q.put(5)
q.put(10)
print(q) # [1,5,10]

print(q.get()) # 1
print(q) # [5, 10]

print(q.peek()) # 5
print(q) # [5,10]

 

3) 파이썬 리스트를 큐로 활용

q = []

q.append(1)
q.append(5)
q.append(10)
print(q) # [1,5,10]

print(q.pop(0)) # 1 # pop에 인덱스 0 넣어서 맨 앞 원소 꺼내게
print(q) # [5, 10]

print(q[0]) # 5
print(q) # [5,10]

그러나, 스택과 달리 큐를 list로 구현하지 않는다. 그 이유는?

위와 같이 list.append와 list.pop(0)을 이용하여 리스트를 큐처럼 사용할 수 있다.

하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다.

따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

 

 

5. 큐의 활용

1) 프린터 인쇄 대기열

컴퓨터가 문서1, 문서2, 문서3 하도록 명령했는데

이때 프린터는 가장 먼저 명령한 것들부터 문서1, 문서2, 문서3 이 처리될 것이다.

 

2) 너비우선탐색

 

 

3. Deque

deque :  스택과 큐를 합친 자료구조

 

- 메소드

from collections import deque

 

De = deque()  # deque 생성

De = deque(list)  # list를 deque화

 

De = deque(maxlen = v) 

# 큐의 최대 길이 명시 이보다 많이 넣으면 가장 왼쪽 원소부터 빼내어 넣으려고 하는 원소를 넣는다.

 

len(De) # 원소수 세기

 

De.append(x) # x를 가장 오른쪽에 삽입

De.popleft()  # 가장 왼쪽에 있는 원소를 제거하고 그 값을 리턴

De.clear()  # 모든 원소 제거