[자료구조/알고리즘] 스택(Stack) & 큐(Queue) & 이진탐색(Binary Search)

스택 (Stack)

LIFO: Last-In First-Out 후입선출

가장 마지막에 쌓은 데이터를 가장 먼저 꺼내 사용하는 방식

특징

• 제일 위의 데이터만 알 수 있다.
• 스택이 담을 수 있는 크기를 초과하여 자료를 Push 하면스택 오버플로우(Stack Overflow)가 발생한다.
• 스택이 비었을 때 Pop을 하면스택 언더플로우(Stack Underflow)가 발생한다.

구현코드

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

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

큐 (Queue)

FIFO: First-In First-Out 선입선출

가장 처음에 쌓은 데이터를 가장 먼저 꺼내 사용하는 방식

특징

• 스택과 반대로 입출력의 방향이 서로 다르게 되어 있어 두 곳으로 접근이 가능
• 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.

구현코드

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

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def peek(self):
        if not self.is_empty():
            return self.items[0]

    def size(self):
        return len(self.items)

이진탐색 (Binary Search)

오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘

과정

• 시간복잡도: O(logN)반복문과재귀 두 가지 방법을 사용할 수 있다.
• 자료를 오름차순으로 정렬한다.
• 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
• mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.
  • target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)
  • target이 mid 값 보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

구현코드