자료구조4- 스택&큐

선형 자료구조의 대표적인 예시로는 스택과 큐가 있다.

여기서 선형 구조란, 자료가 순서를 가지고 연속되어 있다는 것이다.

이번 자료구조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