IT 지식/CS 기초
선형 자료구조 Stack과 Queue
Security Engineer
2024. 8. 16. 00:12
Stack(스택)
- 1차원 선형 구조 → I/O 지점이 1개 뿐인 자료구조 → Stack
- Last In First Out 구조 (LIFO) → 후입선출, 김치냉장고
- 처음 넣은 것은 맨 아래 바닥에 깔린다.
- 두 번째부터는 처음 넣은 것 위에 쌓인다.
- 바닥에 있는 것을 꺼내려면 위에 쌓인 것들을 모두 치우는 수 밖에 없다.
- 생각해볼 문제: 이런 구조는 왜 필요할까? → 뒤집기(순서 바꾸기), 되돌아가기(Ctrl + Z)
- Stack → Ctrl + Z
Queue(큐)
- I/O 지점이 양 끝단으로 나뉘어져 있다. → Queue
- First In First Out 구조 → 선입선출
- 버스를 타기 위해 줄을 서는 것과 같다.
- 은행에서 번호표 뽑은 순서로 기다리는 것과 같다.
- Enqueue → 큐에 뭔가를 집어넣는다.
- Dequeue → 큐에 뭔가를 뺀다.
- 멀티태스킹, 멀티스레딩 환경에서 Queue 자료구조 사용 → 동기화
- 생각해볼 문제: 비슷해 보이지만 버스를 타려고 줄을 선 것과 은행에서 기다리는 것은 차이가 있다. 무엇이 같고 무엇이 다를까?
- Queue → 은행에서 번호표 뽑은 순서로 처리하기
파이썬 코드로 Stack 구현하기
- 파이썬의 list(리스트)로 구현 가능
- push → append (추가)
- pop → pop (제일 끝의 요소가 삭제됨)
- push(값 삽입)은 append로, pop(값 빼기)는 pop을 사용한다.
< 입력 >
stack = [] # stack 변수에 빈 리스트 대입
stack.append(1) # 1을 push
stack.append(2) # 2를 push
stack.append(3) # 3을 push
stack.append(4) # 4를 push
stack.append(5) # 5를 push
stack.append(6) # 6을 push
print(stack) # stack 변수 출력
print(stack.pop()) # stack 변수에서 pop으로 값 빼기
print(stack) # stack 변수 출력
print(stack.pop()) # stack 변수에서 pop으로 값 빼기
print(stack) # stack 변수 출력
< 출력 >
[1, 2, 3, 4, 5, 6]
6
[1, 2, 3, 4, 5]
5
[1, 2, 3, 4]
파이썬 코드로 Queue 구현하기
- 파이썬에서 제공하는 deque 라이브러리를 사용하여 구현 가능
- Enqueue → append (추가)
- Dequeue → popleft (제일 앞의 요소가 삭제됨)
< 입력 >
from collections import deque # deque 불러오기
queue = [1,2,3,4,5,6] # queue 변수에 값 대입
result = deque(queue) # result에 queue 리스트를 deque로 변경 후 대입
print(result) # result 출력
result.append(7) # result에 7 추가
print(result.popleft()) # result에서 popleft로 값 빼기
print(result) # result 출력
print(result.popleft()) # result에서 popleft로 값 빼기
print(result) # result 출력
<출력>
deque([1, 2, 3, 4, 5, 6])
1
deque([2, 3, 4, 5, 6, 7])
2
deque([3, 4, 5, 6, 7])
참고