[자료구조] Stack, Queue (feat. python)

Stack

---

선형 자료구조이며, 기본 개념은 LIFO(Last In First Out)이다.

구현할 메소드는 아래와 같다.

• __init__(self)
• __len__(self)
• push(self, val)
• pop(self)
• top(self)

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

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

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

    def pop(self):
        if len(self) == 0:
            return None
        return self.items.pop()


    def top(self):
        if len(self) == 0:
            return None
        return self.items[-1]

STACK이 활용될 수 있는 예시

1. 웹 브라우저 방문 기록(뒤로가기)
2. 실행 취소(가장 나중에 실행된 것)
3. JS CallStack(함수 호출 구조)

Queue

---

선형 자료구조이며, 기본 개념은 FIFO(First In First Out)이다.

공부하며 찾아보니 자료구조 Queue를 구현할 때, 맴버 변수의 선언 및 활용에 있어서 두 가지의 차이점이 있었다.

CASE_1 )

• self.items : 요소들을 담는 리스트
• self.front_index : 제일 앞의 위치를 저장하는 상수
  self.rear_index까지 선언하는 경우도 확인할 수 있었음

CASE_2 )

• self.items : 요소들을 담는 리스트

위와 같은 두 가지의 경우가 있었고, 코드는 아래와 같다.
구현할 메소드는 공통적으로 아래와 같다.

• __init__(self)
• __len__(self)
• is_empty(self)
• enqueue(self, item)
• dequeue(self)
• front(self)
• back(self)

# **CASE_1**
class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0

    def __len__(self):
        return len(self.items) - self.front_index

    def is_empty(self):
        return len(self) == self.front_index

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

    def dequeue(self):
        if self.is_empty():
            return None
        item = self.items[self.front_index]
        self.front_index += 1
        
        # 리스트의 절반 이상이 비었을 때 리스트를 정리
        if self.front_index > len(self.items) // 2:
            self.items = self.items[self.front_index:]
            self.front_index = 0

        return item

    def front(self):
        if self.is_empty():
            return None
        return self.items[self.front_index]

    def back(self):
        if self.is_empty():
            return None
        return self.items[-1]

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

    def __len__(self):
        return len(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)
        return None

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

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

QUEUE가 활용될 수 있는 예시

1. 예약 사이트 대기 번호(트래픽이 몰린 상황)
2. Cache