[자료구조] 스택 / 큐

스택 (Stack)

0) 정의

-> 프로그래밍에서 목록 or 리스트에서 접근이 한 쪽에서만 가능하다.

나중에 들어온 애가 먼저 나가는 LIFO (Last In First Out) 형태 

1) 구조

Stack은 나중에 들어온 것이 먼저 나가는 LIFO 형태를 띄고 있다.

2) 구현

· 직접 구현

class Stack(list):
    # push = list.append()와 동일 
    # pop = list의 내장함수로 이미 존재 
    
    def peek(self):   # 가장 마지막에 있는 데이터를 보여줌 
        return self[-1]
        
# Stack 사용하기
s = Stack()
s.push(1)   # s = [1]
s.push(5)   # s = [1, 5] 
s.push(10)   # s = [1, 5, 10]
print('popped value is: ',s.pop())  # popped value is: 10, s = [1, 5]
print('peeked value is: ',s.peek())   # peeked value is: 5, s = [1, 5]

· 리스트를 활용한 스택 구현 

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

3) 스택의 활용 - 인터넷 페이지 (이전페이지, 다음페이지)

· 현재 페이지를 네이버라고 하자. 

· 네이버에서 구글로 넘어가면, 이전 페이지 스택에 네이버가 들어간다(push). 

· 구글에서 유튜브로 넘어가면, 이전 페이지 스택에 구글이 추가된다(push). 

· 이전 페이지를 눌러(pop) 구글로 돌아가면, 다음 페이지 스택에 유튜브가 추가된다(push). 

· 이전 페이지를 눌러(pop) 네이버로 돌아가면, 다음 페이지 스택에 구글이 추가된다(push). 

 

큐 (Queue)

0) 정의

-> 영어로 '일이 처리되기를 기다리는 리스트' 라는 의미로, 프로그래밍에서 목록 or 리스트에서 접근이 

    양쪽에서 가능한 구조를 가지고 있다. 먼저 들어온 애가 먼저 나가는 FIFO (First In First Out) 형태 .. 

1) 구조

Queue는 먼저 들어온 것이 먼저 나가는 FIFO 형태를 띄고 있다.

2) 구현

· 직접 구현

class Queue(list): 
    # put = list.append() 
    def peek(self):
        return self[0]  # 가장 앞에 있는 데이터를 보기 위해 인덱스 = 0 
    
    def get(self):
        return self.pop(0)   # pop() 함수에 인덱스를 줌으로써 인덱스에 위치한 데이터를 꺼냄 

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

· Queue 클래스 import를 통한 큐 구현

from queue import Queue 

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

· 리스트를 활용한 큐 구현

list_q = [] 
list_q.append(1)   # list_q = [1]
list_q.append(5)   # list_q = [1, 5]
list_q.append(10)   # list_q = [1, 5, 10] 
print('removed value is: ', list_q.pop(0))   # removed values is: 1, [5, 10]
print('peeked value is: ', list_q[0])   # peeked value is: 5, [5, 10]

3) 큐의 활용 - 프린트 인쇄 대기열

· 컴퓨터가 프린터에게 문서1, 문서2, 문서3을 인쇄하도록 명령

· 프린터는 명령 받은 순서인 문서1, 문서2, 문서3 순서대로 인쇄