자료구조/알고리즘 2023-03-30

스택 큐

스택

한쪽 끝이 막혀 있는 통과 같은 자료구조

스택에 저장하는 개념을 push라고 한다.

저장 된걸 빼는 걸 pop 이라고 한다. 한쪽이 막혀있는 구조기 때문에 abc순으로 집어넣으면 c를 먼저 뺀다

나중에 삽입된 데이터가 먼저 나오는 자료 구조

후입선출(last-in-first-out, LIFO)

큐

양쪽 끝이 뚫려 있는 통과 같은 자료구조

자료를 저장하는것을 enqueue 라고 한다.

자료를 빼는것을 dequeue 라고 한다.

abc 순으로 집어 넣었으면 a가 먼저 나간다.

먼저 삽입된 데이터가 먼저 나오는 자료 구조

선입선출(first-in-first-out, FIFO)

스택의 활용

데이터를 임시 저장하고 싶을 때

• 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때
• 쌍을 맞추어 데이터를 임시 저장하고 싶을 때
• 뒤로 가기 기능을 만들고 싶을 때

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

    def is_empty(self):
        return self.items == []

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

    def pop(self):
        return self.items.pop()

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

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

큐의 활용

데이터를 임시 저장하고 싶을 떄

• 큐를 버퍼로 활용
• 임시 저장된 데이터를 차례차례 내보내야/꺼내와야 할 때

정렬

데이터를 정해진 기준에 따라 재배치 하는 것

다양한 정렬 알고리즘이 존재

• 버블 정렬(O(n^2))
• 선택 정렬(O(n^2))
• 삽입 정렬(O(n^2))
• 퀵 정렬(O nlogn)