자료구조 | 스택, 큐(python 구현)

Jihun Kim·2021년 8월 4일
python스택자료구조큐
0

자료구조

목록 보기
2/2

📒 스택 & 큐

  • 스택, 큐 모두 '선형' 자료구조이다.
  • 추가적으로, 대표적 비선형 자료구조에는 '트리', '그래프'가 있다.

스택과 큐

먼저, 스택을 알아보도록 한다.

🍒 스택

  1. "후입선출" 구조로, 가장 나중에 추가된 자료가 가장 먼저 제거된다.
    -> 즉, 한쪽 끝에서만 자료를 넣거나 뺄 수 있다.
  2. 제한적으로 접근 가능한 자료구조이다.
  3. 스택은 의존관계가 있는 상태를 처리한다.
  4. 만약 어떤 일보다 더 먼저 처리되어야 하는 일이 있다면 스택에 저장할 수 있다.

스택이 활용되는 예시

👩‍💻 콜스택

  • 콜스택이란?
    컴퓨터 프로그램에서 현재 실행중인 함수(서브루틴)를 저장하는 역할을 한다.
    👉 실행 중인 서브루틴은 호출되어 그 실행이 아직 완료되지는 않았지만, 완료후에는 호출된 지점으로 제어를 넘겨야 한다

👩‍💻 재귀함수

  • 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣고, 재귀함수를 빠져나와 퇴각 검색을 할 경우 스택에 넣어 두었던 임시 데이터를 뺀다.
    👉 스택은 이러한 재귀 알고리즘을 반복적 형태로 구현할 수 있도록 만들어 준다.

스택이 지원하는 연산 목록

  • push : 스택에 값을 넣는 연산
  • pop : 스택에서 자료를 빼는 연산
  • top : 스택의 가장 위에 있는 자료를 반환하는 연산
  • empty : 스택이 비어있는지의 여부를 반환하는 연산

👉 파이썬의 append, pop 연산으로 리스트를 통해 구현할 수 있다.

스택 구현하기

👀 스택은 아래의 두 가지 방법으로 구현이 가능하다.

  • 배열을 이용해 구현하기
    👉 배열은 데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리하다 (데이터 접근이 쉽기 때문!).
  • 연결리스트를 이용해 구현하기
    👉 연결리스트는 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리

1. 배열로 구현 

class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        if len(self.stack) == 0:
            return True
        else:
            return False

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        else:
            return self.stack.pop()

    def top(self):
        if self.isEmpty():
            return "Stack is empty"
        else:
            return self.stack[-1]

2. 연결리스트로 구현(Singly Linked List)

# Singly Linked Stack

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class SinglyLinkedStack:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        if self.head is None:
            return True
        else:
            return False

    def pop(self):
        if self.isEmpty():
            return "Stack is Empty"
        else:
            popped = self.head.data
            self.head = self.head.next
            return popped

    def push(self, data):
        new_node = Node(data)
        # push된 데이터는 head를 가리킨다.
        new_node.next = self.head
        # head는 top 데이터가 된다.
        self.head = new_node

    def top(self):
        if self.isEmpty():
            return "Stack is Empty"
        else:
            return self.head.data

이제 큐를 알아보자!

🍒 큐(Queue)

  1. "선입선출" 구조로, 가장 처음에 추가된 자료가 가장 먼저 제거된다.
  2. 입구와 출구가 각각 반대쪽 끝에 존재하는 자료구조이다.

큐가 활용되는 예시

👩‍💻 스케줄링

  • 스케줄링이란?
    운영체제가 프로세스를 관리하는 기법을 의미한다.
    👉 동시에 실행되는 여러 프로세스에 CPU 등의 자원 배정을 적절히 해 성능을 개선하는 기법이다.
  • 여러 프로세스를 동시에 수행할 수 있게 하기 위한 기법인 시분할 시스템을 비롯해 스케줄링 알고리즘은 매우 다양하지만, 대체로 '큐'를 기반으로 스케줄링을 관리한다.
    👉 만약 어떤 작업이 병렬적으로 이루어져도 괜찮을 때, 작업들 사이에 의존관계가 없다면 큐에 저장해서 관리한다.

큐가 지원하는 연산 목록

  • push : 큐에 값을 넣는 연산
  • pop : 큐에서 자료를 빼는 연산
  • front : 큐의 가장 앞에 있는 자료를 반환하는 연산
  • back : 큐의 가장 뒤에 있는 자료를 반환하는 연산
  • empty : 큐가 비어있는지의 여부를 반환하는 연산

🐥 큐의 연산 더 알아보기!!

  1. 큐의 포인터
  • head : 큐의 첫 번째 원소를 가리키는 포인터
  • rear : 큐의 마지막 원소를 가리키는 포인터
  1. 큐에 삽입, 삭제하기
  • push : rear 위치에 자료를 추가하고 rear를 1 증가시킴
  • pop : head 위치의 자료를 제거하고 head를 1 증가시킴

👉 만약 rear가 가리키는 인덱스가 배열의 크기를 초과하게 되면 문제가 생기는데, 이를 해결하기 위한 것이 '원형 큐'와 '링크드 큐'이다

🙊 큐의 종류

원형 큐

  • 원형 큐의 경우, rear나 head가 큐의 끝에 도달하면 이를 큐의 맨 앞으로 보내 문제를 해결한다.

링크드 큐

  • 연결리스트로 구현한 큐를 의미한다.
  • 삽입과 삭제가 제한되지 않으며 크기의 제한이 없다.

큐 구현하기

👀 아래의 세 가지 메소드를 활용해 큐를 구현한다.

enqueue/dequeue/peek

  • enqueue : 데이터를 삽입하는 과정을 의미함
  • dequeue : 데이터를 꺼내는 과정을 의미함
  • peek : front에 있는 값을 꺼내지 않고 어떤 값인 지만 return함

👉 스택에서와 마찬가지로, 배열과 연결 리스트를 이용해 구현할 수 있다.

1. 배열로 구현

class Queue:
    def __init__(self):
        self.queue = []

    def isEmpty(self):
        if not self.queue:
            return True
        else:
            return False

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            dequeued = self.queue[0]
            # 꺼낸 뒤 나머지 재정비
            self.queue = self.queue[1:]
            return dequeued

    # front가 무엇인지만 보여준다.
    def peek(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            peeked = self.queue[0]
            return peeked

2. 연결리스트로 구현

# Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        if self.front is None:
            return True
        else:
            return False

    def enqueue(self, data):
        new_node = Node(data)

        if self.isEmpty():
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            dequeued = self.front
            self.front = self.front.next

        # front가 None이 되면 큐가 비었다는 뜻이므로 rear도 None
        if self.front is None:
            self.rear = None
        return dequeued

    def peek(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            return self.front.data
profile
Jihun Kim
쿄쿄
이전 포스트

자료구조 | 연결리스트(python 구현)

0개의 댓글