선형 자료구조의 대표적인 예시로는 스택과 큐가 있다.
여기서 선형 구조란, 자료가 순서를 가지고 연속되어 있다는 것이다.
이번 자료구조4 에서는 스택과 큐에 대해 공부해보도록 하겠다.
수 많은 자료구조 중에서 스택과 큐를 중요하게 공부하는 이유는 무엇일까?
스택과 큐는 가장 기본적인 자료구조 중 하나이며, 컴퓨터 내에서 중요한 역할을 갖고 있기 때문이다.
<스택>
스택의 가장 큰 특징으로는 맨 마지막으로 집어넣은 값이 먼저 빠지는 후입선출이라는 것이다.
선입선출인 큐와 완전히 반대되는 개념이다.
파이썬의 리스트는 append, pop 등의 연산을 지원하므로 리스트를 이용하여 쉽게 스택을 구현 가능하다.
활용 예시)
콜 스택 - 컴퓨터 프로그램에서 현재 실행 중인 함수(서브루틴)을 저장하는 역할
or 재귀함수 등..
==> 즉, 스택은 의존관계가 있는 상태를 저장한다.
어떤 일보다 더 먼저 처리되어야 하는 일이 있다면, 스택에 저장할 수 있다.
따라서, 여러 작업들 사이에 의존관계가 있을 때 스택을 이용하여 표현할 수 있다.
스택 구현
class Stack:
def __init__(self):
self.myStack = []
def push(self, n):
self.myStack.append(n)
def pop(self):
if self.empty == 1:
return
else:
self.myStack.pop()
def size(self):
return len(self.myStack)
def empty(self):
if self.size == 0:
return 1
else:
return 0
def top(self): # 스택에서 맨 위에 있는 값 반환
if self.myStack.empty() == 1:
return -1
else:
return self.myStack[-1]
<큐>
큐는 선형 자료구조이기 때문에 배열을 이용하여 구현이 가능하긴하다.
하지만, 맨 앞의 데이터의 인덱스를 가리키는 head와
마지막 데이터의 바로 뒤 인덱스를 가리키는 rear이 범위 밖으로 밀려나갈 수 있는 문제가 존재한다.
==> 해결책 : 원형 큐
원형 큐: rear나 head가 큐의 끝에 도달하면 큐의 맨 앞으로 보내어 인덱스 에러가 발생하지 않는다.
활용예시)
스케줄링- 운영체제가 프로세스를 관리하는 기법으로 동시에 실행되는 여러 프로세스에 CPU 등의 자원 배정을 적절히 함으로써 성능을 개선할 수 있다.
운영체제의 알고리즘은 매우 다양하지만 대체로 큐를 기반으로 스케줄링을 관리하고 있다.
어떤 작업이 병렬적으로 이루어져도 괜찮을 때,
==> 즉, 작업들 사이에 의존관계가 없다면 큐에 저장하여 관리할 수 있다.
큐 구현 (리스트 이용)
class Queue:
def __init__(self):
self.myQueue = []
def put(self, n):
self.myQueue.append(n)
def pop(self):
if self.myQueue.empty() == 1:
return
else:
del self.myQueue[0] # 선입선출이므로 맨 앞에 있는 값을 지운다.
def size(self):
return len(self.myQueue)
def empty(self):
if self.size() == 0:
return 1
else:
return 0
def front(self):
if self.empty() == 1:
return -1
else:
return self.myQueue[0] # 맨 앞에 있는 값을 반환
def back(self):
if self.empty() == 1:
return -1
else:
return self.myQueue[-1] # 맨 뒤에 있는 값 반환
링크드 큐 - 연결 리스트로 구현한 큐
-삽입 & 삭제 제한X
- 크기의 제한 X
큐를 실제로 사용할 때에는 파이썬 기본 라이브러리에서 queue 모듈의 Queue 클래스를 사용하면 된다
기능으로는 put, get, empty(True, False 반환)..단, front와 back은 지원하지 않음
import queue
q=queue.Queue()
q.put("a") # 큐에 a를 집어넣음
q.put(1) # 큐에 1을 집어넣음
print(q.qsize()) # 큐의 현재 크기 2
print(q.get()) # 맨 앞에 있는 데이터인 a를 반환
print(q.qsize()) # 큐의 현재 크기 1
from queue import Queue
q=Queue()
이처럼 스택과 큐를 실제로 사용하고자 할 때에는
스택 => 파이썬 리스트
큐 => queue모듈의 Queue 클래스를 사용
스택 => 어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우 ==> 의존관계 O
큐 => 여러 작업들이 동시에(병렬적으로) 이루어져도 상관없는 경우 ==> 의존관계 X
'자료구조' 카테고리의 다른 글
자료구조6 - 트리의 순회와 구현 (0) | 2022.07.14 |
---|---|
자료구조5 - 트리 (0) | 2022.07.14 |
자료구조 문제풀이 - 주문처리 (큐) (0) | 2022.07.13 |
자료구조3 - 연결 리스트 예제 (0) | 2022.07.11 |
자료구조2 - 배열과 연결리스트 (0) | 2022.07.11 |