1. 스택/큐
스택 자료구조는 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다.
스택에서 삽입하는 연산을 push , 삭제하는 연산을 pop 이라고 합니다.
스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조적인 특징을 가지고 있습니다.
큐는 놀이동산에서 줄을 서서 기다리는 것처럼 먼저들어온 자료가 먼저 나가는 자료구조를 말합니다.
큐는 한쪽에서 삽입과, 삭제가 이루워지는 스택과 달리 삭제연산만 수행되는 곳과, 삽입연산만 수행되는 곳으로 나뉘어져 있습니다.
PART 01 스택
영어로 Stack '쌓다'라는 의미를 가지고 있다. 프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조.
LIFO(Last-In, First-Out)가 기본원리.
대표적인 내장함수로는 push, peek, pop을 가지고 있다.
■ <<스택의 구조>>
push 함수를 통해 가장 마지막 층에 BOOK4를 넣는다.
그 다음, 책이 쌓인 곳 바로 위에서 쳐다보면, 가장 마지막에 넣은 데이터인 BOOK4만 보이게 된다. 그 데이터를 보는 함수가 peek이다.
마지막 pop 함수는 가장 마지막 데이터를 꺼내오는 함수이다.
■ <<스택의 구현 방법>>
① 직접 구현
class Stack(list): #리스트를 가지고 있는 스택을 선언
push = list.append #append는 하나의 배열에 뒤에 새로운 데이터를 삽입하는 함수
def peek(self):
return self[-1]
#pop함수는 이미 list의 내장 함수이므로 별도로 만들지 않는다#스택을 선언
s = Stack()
#스택에 1,5,10을 담겠다
s.push(1)
s.push(5)
s.push(10)
#데이터를 담은 스택을 살펴보면
print("my stack is : ",s)
#그다음 pop함수도 사용해보면
print("popped value is : ",s.pop())
#다시 한번 스택을 출력해보면
print("my stack is : ",s)
#마지막으로 peek함수를 출력해보면, 가장 마지막 데이터인 5가 출력된다!!
print("peeked value is : ",s.peek())
② List를 스택으로 활용
#리스트 선언
s = []
s.append(1)
s.append(5)
s.append(10)
print("my stack is : ",s)
print("popped value is : ",s.pop())
print("my stack is : ",s)
#인덱스값을 활용하여 peek 해오기!
print("peeked value is : ",s[-1])
■ <<스택의 활용>>
브라우저에서 우리가 편리하게 사용하는 '이전 페이지 ←' 와 '다음 페이지 →' 를 생각해보자!
우리는 현재 네이버 페이지에 있는 상태이다.
구글로 넘어온 순간, 네이버 페이지는 '이전 페이지'라는 스택에 담기게 된다!
또 다시 유튜브 페이지로 넘어간 순간, 구글 페이지가 '이전 페이지' 스택에 담기게 된다!
이때 이전 페이지 버튼 (←) 을 눌러 구글 페이지로 돌아간다면,
유튜브 페이지가 '다음 페이지'라는 스택에 담기게 된다! 그리고 '이전 페이지' 스택에서 구글이라는 주소가 pop되어서 빠져나왔다!
한번더 이전 페이지 버튼 (←) 을 눌러 네이버 페이지로 돌아간다면,
구글이 '다음 페이지' 스택에 들어가고, 네이버가 '이전 페이지' 스택에서 pop되어서 빠져 나왔다.
PART 02 큐
영어로 Queue '일이 처리되기를 기다리는 리스트'라는 의미로, 프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조로 FIFO(First-In, First-Out)가 기본원리! 즉, 선착순 구조!
대표적 함수 3 가지는 put, peek, get이 있다.
■ <<큐의 구조>>
put 이라는 함수를 통해 BOX4를 컨베이어 벨트에 담는다!
peek 함수는 데이터 중 가장 먼저 들어가 있는 것을 확인할 수 있다. 요기서는 BOX1을 확인할 수 있는 함수다.
get 이라는 함수에 의해 가장 먼저 들어가 있는 BOX1을 트럭에 옮겨둘 수 있다.
■ <<큐의 구현방법>>
① 직접 구현
#list를 갖고 있는 클래스를 선언. 클래스 이름이 Queue
class Queue(list):
#데이터를 넣을 수 있는 함수 pop를 구현. list의 append함수를 그대로 이용
put = list.append
#큐에서는 가장 앞에 있는 데이터를 보기위해 0 인덱스
def peek(self):
return self[0]
#스택에서 pop은 파라미터가 없었기 때문에 가장 마지막 데이터를 꺼냈지만,
#pop에 파라미터 0을 주게 되면, 0번째 인덱스 값을 추출할 수 있다
def get(self):
return self.pop(0)#앞서 만든 클래스를 선언!
q = Queue()
q.put(1)
q.put(5)
q.put(10)
#1,5,10 데이터가 차례로 담겨져 있을 것이다
print("my queue is : ",q)
#get을 활용해 1을 추출해자
print("removed value is : ",q.get())
#그러면 남아있는 5,10이 담겨져 있을 것이다
print("my queue is : ",q)
#peek함수로 맨 앞의 데이터를 확인해보면, 5가 출력될 것이다!
print("peeked value is : ",q.peek())
② 이미 구현된 클래스 import
③ List를 큐로 구현
#list 선언
q = []
#put 함수를 만들지 않고, 기존에 있던 append를 활용하여 데이터 삽입!
q.append(1)
q.append(5)
q.append(10)
print("my queue is : ",q)
#get 함수를 만들지 않고, 기존의 pop함수에 인덱스 0값을 빼내기! 가장 먼저 들어간 데이터!
print("removed value is : ",q.pop(0))
print("my queue is : ",q)
#peek 함수를 만들지 않고, 인덱스 0값을 출력해보기!
print("peeked value is : ",q[0])
■ <<큐의 활용>>
프린터 인쇄 대기열
컴퓨터가 문서1, 문서2, 문서3 을 출력하라고 프린터에 명령을 내리면, 프린터는 1,2,3 순서대로 출력한다!