[알고리즘]STEP 1-1주차 스택/큐(내용정리)

✅ 스택

• 프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조
• LIFO(Last-In, First-Out)가 기본원리

✍🏻함수

• push : 리스트의 가장 마지막에 원소를 추가
• peek : 가장 마지막에 넣은 원소를 확인
• pop : 제일 마지막에 넣은 원소를 추출

✍🏻 Python에서 스택의 구현 방법

Python은 List가 스택으로 사용 가능하도록 구현되어 있다.

• 직접 구현

 class Stack(list):
	push=list.append
    
    def peek(self):
    	return self[-1]
    #pop은 list의 내장함수로 이미 존재한다.

  s=Stack()
  s.push(1)      #[1]
  s.push(5)      #[1,5]
  s.push(10)     #[1,5,10]

  print("popped value is:", s.pop())     #popped value is 10
  print(s)       #[1,5]
  print("peeked value is:", s.peek())    #peeked value is 5
  print(s)       #[1,5]

• List를 스택으로 구현

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

  print("popped value is:", s.pop())     #popped value is 10
  print(s)       #[1,5]
  print("peeked value is:", s[-1])    #peeked value is 5
  print(s)       #[1,5]

✍🏻 스택의 활용

• 브라우저의 이전/다음페이지
  이전페이지를 담을 스택/ 다음페이지를 담을 스택
  👉🏻 새로운 페이지로 이동 시에 현재페이지를 이전페이지 스택에 push
  👉🏻 이전페이지로 이동 시에 현재페이지를 다음 페이지에 push, 이전페이지의 마지막 페이지를 pop

• 깊이 우선 탐색(DFS)

✅ 큐

프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조로 FIFO(First-In, First-Out)가 기본원리

✍🏻함수

• put :큐의 가장 마지막에 원소를 추가
• peek :큐에 가장 먼저 들어간 원소를 확인
• get :큐에 가장 먼저 들어간 원소를 추출

✍🏻 Python 큐의 구현방법

• 직접 구현

class Queue(list)
	put=list.append
    def peek(self):
    	return self[0]
    def get(self):
    	return self.pop(0)
        
q=Queue()
q.put(1)
q.put(5)
q.put(10)
print(q)		#[1,5,10]
print("removed value is:", q.get())		#removed value is: 1
print(q)		#[5,10]
print("peeked value is:", q.peek())		#peeked value is: 5
print(q)		#[5,10]

• 이미 구현된 클래스 import

from queue import Queue

q=Queue()
q.put(1)
q.put(5)
q.put(10)
print(q)		#[1,5,10]
print("removed value is:", q.get())		#removed value is: 1
print(q)		#[5,10]
print("peeked value is:", q.peek())		#peeked value is: 5
print(q)		#[5,10]

- List를 큐로 구현

q=[]

q.append(1)  #큐의 put
q.append(5)
q.append(10)
print(q)		#[1,5,10]
print("removed value is:", q.pop(0)) #큐의 get		#removed value is: 1
print(q)		#[5,10]
print("peeked value is:", q[0])		#peeked value is: 5
print(q)		#[5,10]

✍🏻 deque

❗ 리스트로 큐의 연산을 수행하기에는 효율적이지 않음

큐를 위해 Deque라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있음
데큐를 이용해 스택, 큐 모두 구현 가능

삽입

• deque.append(item) : item을 데크의 오른쪽 끝에 삽입함
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입함

삭제

• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
• deque.remove(item): item을 데크에서 찾아 삭제

from collections import deque
deq=deque()

deq.appendleft(10) 	#[10]
deq.append(0)		#[10,0]
deq.appendleft(5)	#[5,10,0]

deq.pop()			#[5,10]
deq.popleft()		#[10]

✍🏻 큐의 활용

• 프린트 인쇄 대기열
• 너비 우선 탐색(BFS)