스택

스택(Stack)은 자료를 쌓아놓은 것이다.

한쪽에서만 데이터를 삽입/삭제 할 수 있는 자료구조이다. 후입선출(Last In First Out, LIFO) 원칙에 따라 자료를 관리한다.

스택의 성질

1. 원소의 추가/삭제의 시간복잡도 O(1)
2. 제일 상단의 원소 확인 O(1)
3. 제일 상단을 제외한 원소의 확인/변경은 원칙적으로 불가

스택의 활용 예

• DFS(Depth First Searh, 깊이 우선 탐색)
• 재귀함수
• 브라우저의 뒤로가기 기능
• 괄호 정합성 판단

파이썬에서의 스택

Java에서는 라이브러리로 Stack을 사용할 수 있지만, 파이썬에서는 List가 Stack의 역할을 대신 하므로 별도의 구현 없이 사용 할 수 있다.

자바에서의 스택 메서드

1. push() : 최상단에 원소를 추가하는 메서드
2. pop() : 최상단의 원소를 반환하고 제거하는 메소드
3. peek() : 최상단의 원소의 값을 반환만 하는 메소드
4. isEmpty() : 스택이 비었는지 확인하는 메소드

파이썬에서는 List의 append로 push를 대신하고, pop은 그대로 사용 할 수 있다. peek은 List의 마지막 index를 의미하는 list[-1]을 사용하면 된다.

큐

Queue는 대기 행렬(줄)이다.

Queue는 사전적으로 "줄을 서다"를 의미합니다.
줄을 서서 기다리는 것처럼 먼저 들어오면 데이터가 먼저 나가는 형식입니다.
일명 FIFO(First In First Out) 방식입니다. 큐에서 원소가 추가되는 쪽을 rear, 원소가 출력되고 삭제되는 쪽을 front라고 합니다.

큐의 성질

1. 원소의 추가/삭제에 걸리는 시간복잡도 O(1)
2. 자료구조의 제일 앞/뒤의 원소 확인에 걸리는 시간이 O(1)
3. 원칙적으로 제일 앞/뒤의 원소말고는 확인/변경이 불가

큐의 활용 예

• BFS(Breadth-First Search): 그래프 탐색 알고리즘에서 큐를 사용하여 노드를 방문하는 순서를 관리합니다.
• 스트리밍: 데이터를 순차적으로 처리하는 경우, 큐를 사용하여 데이터 흐름을 관리할 수 있습니다.
• 프로세스 스케줄링: 운영 체제에서 프로세스를 순서대로 실행하기 위해 큐를 사용합니다.

파이썬에서의 큐

스택과 마찬가지로 list로 queue를 구현 할 수 있지만, list의 경우 pop(0)으로 front의 원소를 출력/삭제 한다면 O(n)의 시간이 걸려서 성능상으로 좋지 않습니다.

Queue

queue모듈의 Queue 클래스를 활용해서 큐를 사용 할 수 있습니다. put() 메소드로 원소추가 , get() 메소드로 원소를 삭제 할 수 있습니다.

from queue import Queue

a = Queue()
a.put(1)
a.put(2)
a.put(3)
a.put(4)

print(a.queue) # 큐의 전체 원소확인
print(a.queue[0]) # 큐의 front 값 확인
print(a.queue[-1]) # 큐의 rear 값 확인
print(a.qsize()) # 큐의 size 확인
print(a.empty()) # 큐 비었는지 확인
print(a.get()) # front 원소 삭제
print(a.empty()) # rear에 값 추가
print('===============')
>>> 출력결과
deque([1, 2, 3, 4])
1
4
4
False
1
False
===============

직접 구현

class Queue:
    def __init__(self, mx=10000):
        self.dat = [0] * mx
        self.head = 0
        self.tail = 0

    def push(self, num): # 큐 원소 추가
        self.dat[self.tail] = num
        self.tail += 1

    def pop(self): # 큐의 맨 앞원소 삭제 및 값 반환 , 여기서는 큐가 비었을시 None으로 예외처리함
        if self.head == self.tail:
            return None
        self.head += 1
        return self.dat[self.head - 1]

    def isEmpty(self): # 큐가 비었는지 확인
        return self.tail - self.head == 0

    def size(self): # 큐의 사이즈 확인
        return self.tail - self.head

    def front(self): # 맨 앞 원소 확인 , 여기서는 큐가 비었을시 None으로 예외처리함
        if self.head == self.tail: return None
        return self.dat[self.head]

    def rear(self): # 맨 뒤 원소 확인 , 여기서는 큐가 비었을시 None으로 예외처리함
        if self.head == self.tail: return None
        return self.dat[self.tail - 1]