알고리즘 스터디 #스택과 큐

 

스택(Stack : 쌓다)이란?

프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조

LILO(Last-In, Last-Out)

 

push, peek, pop 세 개의 함수 사용

 

Book1, 2, 3 을 차례대로 스택에 넣으면 

BOOK3

BOOK2

BOOk1

이렇게 쌓여진다. 만약 이 스택에 BOOK4를 추가하면

BOOk4

BOOk3

BOOk2

BOOk1

book3 위로 올라간다.

 

위에서 내려다보면 가장 맨 위에 있는 책(가장 위에있는 데이터) 만 보인다. 

가장 위에 있는(가장 마지막에 들어가있는)게 무엇인지 확인하는 함수가 peek

 

pop은 제일 마지막에 들어간 데이터를 꺼내는 것, 가장 맨 위의 것을 가져가는 것이다.

 

BOOKS = [BOOK1, BOOK2, BOOK3, BOOK4]

였다가 pop을 하면 [BOOK1, BOOK2, BOOK3] 가 된다.

 

 

phthon 스택의 구현방법

1. 직접구현

2. 이미 구현된 클래스 import

3. list를 스택으로 구현

(2,3은 이미 내장되어있는 함수라서 따로 class 구현할 필요가 없다)

 

 

 

1. 직접구현

class Stack(list):
    push = list.append

    def peek(self):
        return self[-1]  # 가장 마지막에 있는 데이터. self.[len(self)-1] 사용도 ㄱㅊ

s = Stack()
s.push(1)
s.push(5)
s.push(10)


print("my stack is:", s)  # 스택에 1, 5, 10이 순서대로 쌓임
print("popped value is:", s.pop())  # 맨 위 데이터인 10이 뽑힘
print("my stack is:", s)  # [1, 5] 만 남음
print("peeked value is:", s.peek())  # 맨 위의 데이터만 보임
print("my stack is:", s)  # pop한건 아니기 때문에 데이터는 그대로

 

 

3. python 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)
print("peeked value is:", s[-1])    #인덱스로 픽
print("my stack is:", s)

 

 

 

 

큐(Queue: 일이 처리되기를 기다리는 리스트) 

 

프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조

FIFO(First-In, First-Out)

 

put / peek / get 함수가 존재

 

 

컨베이어 벨트가 있다. 이 벨트 위에 Box1,  Box2,  Box3을 순서대로 올리면

Box 3    Box2    Box1

이렇게 되어있을 것이다.

 

여기에 box4를 넣으면 put

box의 리스트가 [box1, box2, box3, box4] 가 된다. 

 

peek으로 가장 먼저 들어간 box1 확인

get으로 가장 먼저 들아간 box1을 트럭에 실어!

 

 

python 큐 구현

 

1,2,3 구현 모두 같은 output을 보인다.

 

 

1. 직접구현

class Queue(list):
    put = list.append

    def peek(self):
        return self[0]  # 가장 앞에 있는 데이터 확인

    def get(self):
        return self.pop(0)  # 인덱스가 0인 데이터 pop

q = Queue()
q.put(1)
q.put(5)
q.put(10)

print("my queue is:", q)  # [1, 5, 10]
print("removed value is:", q.get())  # 가장 먼저 들어간 애를 get!
print("my queue is:", q)  # [5, 10]
print("peeked value is:", q.peek())  # 가장 나중에 들어간 애 확인만
print("my queue is:", q)  # [5, 10]

 

 

 

2. 이미 구현된 클래스 import

from queue import Queue

q = Queue()
q.put(1)
q.put(5)
q.put(10)
print("my queue is:", q)    # [1,5,10]
print("removed value is:", q.get())    #get 정의 하지 않아도 내장되어있어서 사용가능
print("my queue is:", q)
print("peeked value is:", q.peek())    #peek도 자동 내장

 3. list를 큐로 구현

 

q = []

q.append(1)
q.append(5)
q.append(10)

print("my queue is:", q)
print("removed value is:", q.pop(0))   #get쓰면 안되나?
print("my queue is:", q)
print("peeked value is:", q[0])
print("my queue is:", q)