Stack
LIFO (Last In First Out)
stack 은 선형(linear) 자료구조로서 data들이 한쪽방향으로만 저장되고 / 삭제되는 자료구조이다.
stack은 다음 2가지 주요 연산을 사용한다.
- push() : data를 추가한다.
- pop() : 가장 최근에 삽입된 data를 삭제한다.
stack의 사용
- 브라우저의 뒤로가기
- 실행취소
stack의 method (python)
| Method | Description | Big O |
|---|---|---|
| empty() | Returns whether the stack is empty | O(1) |
| size() | Returns the size of the stack | O(1) |
| top() / peek() | Returns a reference to the topmost element of the stack | O(1) |
| push(a) | Inserts the element ‘a’ at the top of the stack | O(1) |
| pop() | Deletes the topmost element of the stack | O(1) |
ex)
stack = []
stack.append(3) # stack = [3]
stack.append(5) # stack = [3, 5]
stack.append(7) # stack = [3, 5, 7]
print(stack[-1]) # 7 -> 최상단 원소(top) 출력
stack.pop() # stack = [3, 5]
stack.append('c') # stack = [3, 5, 'c']
print(stack[::-1]) # ['c', 5, 3] -> 최상단 원소부터 출력
print(stack) # [3, 5, 'c'] -> 최하단 원소부터 출력Queue
FIFO (First In First Out)
Queue 은 선형(linear) 자료구조로서, data가 한쪽 방향으로는 저장만 되고 다른 한쪽 방향으로는 삭제만 되는 자료구조 이다.
- 일반적으로 Queue는 효율성을 위해 collections 모듈의 deque 자료구조를 이용하여 구현한다.
Queue의 사용
- 프린터의 출력 처리
- 콜센터 고객 대기
ex)
from collections import deque
queue = deque()
queue.append(6) #deque([6])
queue.append(7) #deque([6, 7])
queue.append(3) #deque([6, 7, 3])
queue.popleft() #deque([7, 3])
queue.append(4) #deque([7, 3, 4])
queue.popleft() #deque([3, 4])
print(queue)
backend developer