[1주차] 스택 / 큐

- 스택 : 접근이 한 쪽에서만 가능한 구조, LIFO(Last-In, First-Out)이 기본원리

- 함수

   - push : 데이터를 삽입하는 함수

   - peek : 리스트의 마지막 값이 무엇인지 알려주는 함수

   - pop : 리스트의 마지막 값을 빼내는 함수

- 스택 구현 방법

1) 스택 직접 구현

- pop()은 내장 함수 사용

class Stack(arr):
	push = list.append
    
    def peek(self):
    	return self[-1]
        
        
s = Stack()
s.push(1)
s.push(5)
s.push(10)
                        # 출력
print(s)                ----> [1, 5, 10]
print(s.pop())          ----> 10
print(s)                ----> [1, 5]
print(s.peek())         ----> 5
print(s)                ----> [1, 5]

 

2) list를 스택으로 활용

s = []

s.append(1)
s.append(5)
s.append(10)

                               # 출력
print(s)                       -----> [1, 5, 10]
print(s.pop())                 -----> 10
print(s)                       -----> [1, 5]
print(s[-1]) # peek함수 역할    -----> 5
print(s)                       -----> [1, 5]

- 스택의 활용

   - 웹 브라우저에서 이전 페이지, 다음 페이지 이동 

   - 깊이 우선 탐색(DFS)

 

 

- 큐 : 접근이 양쪽에서 가능한 구조, FIFO(First-In, First-Out)이 기본 원리

- 함수

  - put : 데이터를 삽입하는 함수

  - peek : 리스트의 첫번째 값이 무엇인지 알려주는 함수

  - get : 리스트의 첫번째 값 빼내는 함수 

- 큐 구현 방법

1) 큐 직접 구현

class Queue(arr):
	put = list.append
    
    def peek(self):
    	return self[0]
        
    def get(self):
    	return self.pop(0)
        
        
q = Queue()
q.put(1)
q.put(5)
q.put(10)
                      # 출력
print(q)              -----> [1, 5, 10]
print(q.get())        -----> 1
print(q)              -----> [5, 10]
print(q.peek())       -----> 5
print(q)              -----> [5, 10]

 

2) 구현된 클래스 import

from queue import Queue

q = Queue()

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

print(q)               -----> [1, 5, 10]
print(q.get())         -----> 1
print(q)               -----> [5, 10]
print(q.peek())        -----> 5
print(q)               -----> [5, 10]

 

3) List를 큐로 활용

q = []

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

print(q)             -----> [1, 5, 10]
print(q.pop())       -----> 1
print(q)             -----> [5, 10]
print(q[0])          -----> 5
print(q)             -----> [5, 10]

- 큐의 활용 

   - 프린터 인쇄 대기열

   - 너비 우선 탐색(BFS)