[플레이데이터][자료구조] 스택 & 큐
스택과 큐
🔊 2021.03.26 (금) 엔코아 플레이데이터 알고리즘 특강 1주차 내용을 정리한 노트 게시물입니다.
PART 1. 스택
- 영어로 stack ‘쌓다’라는 의미
- 프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조
- LIFO(Last-In, First-Out)가 기본원리
- push peek pop
※ 스택의 구조
BOOK 4를 추가하려고 한다.
책을 사이에 넣어 쌓는 것보다 위에 올려서 쌓는 것이 더 편하므로, 특정 이유가 없다면 BOOK 3 위에 BOOK 4를 얹어놓을 것이다. 이 작업을 push라고 한다.
push에 의해서 BOOK4가 리스트 안에 추가되었다.
그 다음, 책들이 쌓인 곳에서 우리가 위에서 내려다보면 어떤 책만 확인할 수 있을까?
가장 위에있는 책… 즉, 가장 마지막에 넣은 데이터가 무엇인지 확인할 수 있을 것이다.
그 아래에 있는 책은 무엇인지 모른다.
즉, 가장 마지막에 무엇인지 확인하는 함수가 바로 ‘엿보다’의 의미를 갖고있는 peek이다.
그 다음은 pop이다.
pop은 peek함수에서 책을 가져가는 작업을 추가한 것으로 스택에서 제일 마지막에 넣은 데이터를 추출하는 함수이다.
BOOK4가 pop에 의해서 리스트에서 빠져나온 것을 확인할 수 있다. (위 이미지)
스택의 구현방법을 보도록 한다.
일반적으로 자료구조를 구현하는 방법은 크게 세가지가 있다 (직접 구현, 이미 구현된 클래스 import, List를 스택으로써 활용하기)
그러나, 우리는 직접 구현을 제외한 나머진 여기서 다루지 않는다.
파이썬의 경우 내장된 리스트가 스택으로 활용될 수 있도록 너무나 잘 갖추어져 있기 때문이다.
※ Python 스택의 구현 방법
직접 구현
class Stack(list):
push = list.append
# append는 하나의 배열의 뒤에 새로운 데이터를 추가하는 함수로 스택에서 push와 100% 동일하므로, append 함수 자체를 push로 지정한다.
def peek(self):
return self[-1] # - 스택의 가장 마지막 데이터의 값을 보여줌. - 데이터 추출 X
# 이렇게 대신할 수도 있다 >> self[len(self) -1]
# - pop은 list의 내장함수로 이미 존재하므로 구현하지 않는다.
Python 스택 직접 구현 활용
Python List를 스택으로 활용
앞에서 push, peek, pop이 스택의 대표적인 함수라고 말했지만 함수명은 중요하지 않다.
그 함수들이 어떤 기능을 가지고 있는지 파악하면 된다.
※ 스택의 활용 (스택이 활용될 수 있는 기능)
뒤로가기 앞으로 가기
현재페이지는 네이버… 주소창에 열심히 입력해서 구글로 넘어가본다
네이버가 이전 페이지 스택으로 push되었다!
이번에는 구글에서 유튜브로 이동해본다.
구글이 이전페이지 스택에 들어간 것을 확인할 수 있겠다.
이번에는 이전 페이지 버튼을 눌러서 이전 페이지로 돌아가보도록 한다.
그랬더니, 유튜브가 다음페이지 스택으로 돌아가고 이전 페이지에서 구글이라고 하는 주소가 pop 되어서 빠져나온 것을 확인할 수 있겠다.
한번 더 이전 페이지를 눌러보도록 한다.
그럼, 구글이 다음 페이지로 들어가고 이전 페이지에서 네이버가 빠져나온 것을 우리는 확인할 수 있다.
깊이 우선 탐색(DFS)
자세한 내용은 다음 시간에…
PART 2. 큐
- 영어로 Queue ‘일이 처리되기를 기다리는 리스트’ 라는 의미
- 프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조
- FIFO(First-In, First-Out)가 기본원리
- 쉽게말해 선착순 방식을 고집한다.
- put peek get
※ 큐의 구조
여기 컨베이어 벨트가 있다. 우리는 지금부터 이 컨베이어 벨트를 하나의 큐라고 생각할 것이다.
직원이 컨베이어 벨트에 BOX 1, BOX 2, BOX 3을 얹어놓았다.
그럼 BOX 리스트에는 BOX 1, BOX 2, BOX 3가 들어있는 것을 우리는 확인할 수 있다.
직원이 BOX 4도 얹어놓으려고 한다. 우리는 이 작업을 put 이라고 한다.
put이 되면 컨베이어 벨트에 BOX 4가 올라갈 것이다.
그러면 BOX 리스트에는 BOX 4가 추가된 것을 확인 할 수 있을 것이다.
다음은 peek이다.
peek은 큐의 가장 먼저 들어간 데이터가 무엇인지를 확인 할 수 있다.
가장 먼저 올려뒀던 BOX 1이 있다는 것을 확인할 수 있다.
하지만, 스택에서와 마찬가지로 데이터를 확인만 할 뿐이지 가져가지는 않는다.
그리고, 이 박스를 실을 트럭이 한 대가 있다.
이 트럭은 큐에 가장 먼저 들어갔던 BOX 1을 실을 것이다. 이 작업이 get이다.
get에 의해서 BOX 1이 리스트에서 빠져나간 것을 우리는 확인 할 수 있다.
※ Python 큐의 구현방법
스택과 마찬가지로 직접 구현을 할 수 있는 방법이 있고, 큐를 활용할 수 있도록 내장된 클래스를 import 할 수 있고, 마지막으로 리스트를 직접 큐로 구현이 가능하다.
먼저 직접 구현부터 확인해보도록 한다.
Python 큐 직접 구현
class Queue(list): # 리스트를 갖고 있는 Queue 라는 클래스를 선언
put = list.append # 데이터를 넣을 수 있는 put 정의 :: put은 append와 같은 작업이므로 그대로 append를 put으로 정의
def peek(self):
return self[0] # 큐에서는 가장 앞에 있는 데이터를 보기위해 인덱스 값을 0을 사용한다.
def get(self):
return self.pop(0) # 스택에서 pop은 파라미터를 주지 않았다. 파라미터가 없었기 때문에 가장 마지막에 있는 데이터를 꺼냈다.
# pop에 파라미터 0을 주게되면 인덱스 값이 0번째인 데이터를 추출할 수 있다.
Python 큐 직접 구현 활용
get() 함수를 써서 데이터를 얻어본다.
get 함수에 의해서 1이 빠져나간 것을 확인할 수 있다.
다시 큐를 출력해보면 큐에는 더이상 1이 존재하지 않는 것을 알 수 있다.
그 다음 peek을 해보면 그럼 1 다음에 들어갔던 5가 있는 것을 확인할 수 있겠다. 하지만 peek은 데이터를 추출하지 않고, 확인만 할 뿐이다.
그렇기 때문에 다시 큐를 출력해본다 하더라도 5는 여전히 존재할 것이다.
Python 구현된 클래스 import (큐 클래스 import)
queue를 import하기만 하면 됨… 함수들도 이미 다 구현이 되어있다.
Python List를 큐로 활용
구현법이나 함수 이름에는 정해진 정답이 없기 때문에 개개인마다 다를 수 있다.
여기서는… put함수를 굳이 만들지 않고, 기존에 있던 append함수를 활용했다.
peek은 인덱스 값을 바로 불러오는 것으로, get은 get함수를 만들지 않고 pop 함수에 0을 파라미터로 주어서 get처럼 활용할 수 있도록 구현되었다.
※ 큐의 활용
프린터 인쇄 대기열
컴퓨터와 프린터가 있다.
컴퓨터가 문서1, 문서2, 문서3을 인쇄하도록 명령했다.
그럼 프린터는 절대 거꾸로 인쇄하지 않는다. 먼저 명령을 받은 것부터 실행시켜서 문서1, 문서2, 문서3 순서대로 출력을 할 것이다.
너비 우선 탐색(BFS)
자세한 내용은 다음 시간에…
Leave a comment