알고리즘 1 | 스택과 큐

스택

스택이란?
영어로 Stack '쌓다'라는 의미로
프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조로
LIFO(Last In First Out)가 기본 원리

대표적인 내장함수 [ push | peek | pop ]

스택의 구조

책이 3권 쌓여있다. 여기에 한권을 더 쌓는 것이 push
책을 위에서 내려다 보면 가장 위에있는 책만 확인할 수 있다. 이렇게 확인하는 것이 peek
가장 마지막에 들어온 책을 꺼내는 것이 pop

스택의 구현방법 (파이썬)

1. PYTHON 스택 직접 구현

list를 가진 클래스 선언 (클래스명: stack)

push = list.append
def peek(self):
	return self[-1]
    	self[len(self)-1]

list의 append함수는 하나의 배열의 뒤에 새로운 데이터를 추가하는 함수로 stack에서 push와 동일함.
peek함수는 스택에서 가장 마지막 값을 보는 것, return -1로 peek을 대신함.
pop함수는 파이썬에서 list의 내장함수로 이미 존재.

2. PYTHON List를 스택으로 활용하여 구현

스택의 활용

인터넷창에서 이전페이지, 다음페이지의 구현방법

깊이 우선 탐색

---

큐

영어로 Queue는 일이 처리되기를 기다리는 리스트 라는 의미
프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조로
FIFO가 기본원리이다.

대표함수 [ put | peek | get ]이 있다.

큐의 구조

• put을 쓰면 제일 뒤에 들어감.
• peek을 쓰면 제일 먼저 들어온 것을 보게 됨. 확인만 할 뿐.
• get을 쓰면 제일 먼저 들어온 것을 가져감.

큐의 구현방법

1. PYTHON 직접 구현

class Queue(list):
	put = list.append // 데이터를 넣는 함수
	def peek(self):
		return self[0] // 맨 첫번째 값 0
	def get(self):
	return self.pop(0)

// 인덱스 값이 0번째인 데이터 추출

1.1 PYTHON 큐 직접 구현 활용

q = Queue() // Queue클래스를 q라고 선언

q.put(1)	// q에 1 담음
q.put(5)	// q에 5 담음
q.put(10)	// q에 10 담음
print("my queue is : ", q)  => my queue is : [1, 5, 10]
print("removed value is : ", q.get())  =>removed value is : 1
print("my queue is : ", q)  => my queue is : [5, 10]
print("peeked value is : ", q.peek())  => peeked value is : 5
print("my queue is : ", q)  => my queue is : [5, 10]

2. PYTHON 구현된 클래스 import

from queue import Queue // Queue클래스 import

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

3. PYTHON List를 큐로 활용

q = []
q.append(1)
q.append(5)
q.append(10)
print("my queue is : ", q)  => my queue is : [1, 5, 10]
print("removed value is : ", q.pop(0))  =>removed value is : 1
print("my queue is : ", q)  => my queue is : [5, 10]
print("peeked value is : ", q[])  => peeked value is : 5
print("my queue is : ", q)  => my queue is : [5, 10]

큐의 활용

• 프린터 인쇄 대기열

• 컴퓨터가 문서1, 문서2, 문서3을 프린트하도록 명령