[자료구조] Week 3: 스택과 큐

Day 1: 스택의 기본 개념

• 강의 내용:
  • 스택의 정의와 특징
    • 스택의 개념과 용도
    • 후입선출(LIFO) 원리
  • 스택의 주요 연산
    • push, pop, peek, is_empty
• 실습:
  • 리스트를 이용한 스택 구현

# 리스트를 사용한 스택 구현
class Stack:
    def __init__(self):
        self.stack = []

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

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

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

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

    def display(self):
        print(self.stack)

# 스택 사용 예제
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # [1, 2, 3]
print("Pop:", stack.pop())  # Pop: 3
stack.display()  # [1, 2]
print("Peek:", stack.peek())  # Peek: 2

 

Day 2: 스택의 응용

• 강의 내용:
  • 스택의 응용 사례
    • 괄호 검사
    • 중위 표현식을 후위 표현식으로 변환
  • 스택을 사용한 알고리즘
• 실습:
  • 괄호 검사 알고리즘 구현

# 괄호 검사 알고리즘
def is_balanced(expression):
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    for char in expression:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    return stack.is_empty()

# 괄호 검사 예제
print(is_balanced("(){}[]"))  # True
print(is_balanced("({[)]"))   # False

 

Day 3: 큐의 기본 개념

• 강의 내용:
  • 큐의 정의와 특징
    • 큐의 개념과 용도
    • 선입선출(FIFO) 원리
  • 큐의 주요 연산
    • enqueue, dequeue, front, is_empty
• 실습:
  • 리스트를 이용한 큐 구현

# 리스트를 사용한 큐 구현
class Queue:
    def __init__(self):
        self.queue = []

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

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

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

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

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

    def display(self):
        print(self.queue)

# 큐 사용 예제
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()  # [1, 2, 3]
print("Dequeue:", queue.dequeue())  # Dequeue: 1
queue.display()  # [2, 3]
print("Front:", queue.front())  # Front: 2

 

Day 4: 큐의 응용

• 강의 내용:
  • 큐의 응용 사례
    • BFS(너비 우선 탐색)
    • 프린터 대기열 관리
  • 큐를 사용한 알고리즘
• 실습:
  • BFS 알고리즘 구현

# 그래프를 표현하는 클래스
class Graph:
    def __init__(self, vertices):
        self.graph = {i: [] for i in range(vertices)}

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, start):
        visited = [False] * len(self.graph)
        queue = Queue()
        queue.enqueue(start)
        visited[start] = True
        while not queue.is_empty():
            node = queue.dequeue()
            print(node, end=" ")
            for neighbor in self.graph[node]:
                if not visited[neighbor]:
                    queue.enqueue(neighbor)
                    visited[neighbor] = True

# BFS 사용 예제
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("BFS 시작점 2:")
g.bfs(2)  # 2 0 3 1

 

Day 5: 우선순위 큐

• 강의 내용:
  • 우선순위 큐의 개념
    • 우선순위 큐의 정의와 용도
    • 힙을 사용한 우선순위 큐 구현
  • 우선순위 큐의 주요 연산
    • insert, delete_min
• 실습:
  • 힙을 사용한 우선순위 큐 구현

import heapq

# 힙을 사용한 우선순위 큐 구현
class PriorityQueue:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        heapq.heappush(self.heap, item)

    def delete_min(self):
        if not self.is_empty():
            return heapq.heappop(self.heap)
        return None

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

    def display(self):
        print(self.heap)

# 우선순위 큐 사용 예제
pq = PriorityQueue()
pq.insert(3)
pq.insert(1)
pq.insert(2)
pq.display()  # [1, 3, 2]
print("Delete min:", pq.delete_min())  # Delete min: 1
pq.display()  # [2, 3]

 

Day 6: 스택과 큐의 비교 및 선택

• 강의 내용:
  • 스택과 큐의 비교
    • 자료 구조의 특성과 용도 비교
    • 스택과 큐의 시간 복잡도 분석
  • 상황에 따른 자료 구조 선택
• 실습:
  • 다양한 상황에서 스택과 큐를 선택하는 예제

# 스택과 큐 비교 예제
def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    reversed_str = ""
    while not stack.is_empty():
        reversed_str += stack.pop()
    return reversed_str

def process_tasks(task_list):
    queue = Queue()
    for task in task_list:
        queue.enqueue(task)
    while not queue.is_empty():
        task = queue.dequeue()
        print(f"Processing task: {task}")

# 예제 사용
print("Reversed string:", reverse_string("hello"))  # olleh
process_tasks(["task1", "task2", "task3"])  # Processing task: task1, task2, task3

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 스택과 큐를 사용한 종합 연습 문제 풀이
    • 다양한 스택과 큐 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 스택과 큐를 활용한 간단한 프로그램 구현
    • 예: 웹 브라우저의 뒤로 가기/앞으로 가기 기능
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 스택을 사용한 문자열 회문 검사
def is_palindrome(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    reversed_str = ""
    while not stack.is_empty():
        reversed_str += stack.pop()
    return s == reversed_str

print("Is 'radar' a palindrome?", is_palindrome("radar"))  # True
print("Is 'hello' a palindrome?", is_palindrome("hello"))  # False

# 미니 프로젝트 예제: 웹 브라우저의 뒤로 가기/앞으로 가기 기능
class Browser:
    def __init__(self):
        self.history = Stack()
        self.forward_stack = Stack()

    def visit(self, url):
        print(f"Visiting {url}")
        self.history.push(url)
        self.forward_stack = Stack()  # Reset forward stack

    def back(self):
        if not self.history.is_empty():
            url = self.history.pop()
            self.forward_stack.push(url)
            if not self.history.is_empty():
                print(f"Going back to {self.history.peek()}")
            else:
                print("No pages in history")

    def forward(self):
        if not self.forward_stack.is_empty():
            url = self.forward_stack.pop()
            self.history.push(url)
            print(f"Going forward to {url}")

# 웹 브라우저 사용 예제
browser = Browser()
browser.visit("google.com")
browser.visit("stackoverflow.com")
browser.visit("github.com")
browser.back()  # Going back to stackoverflow.com
browser.back()  # Going back to google.com
browser.forward()  # Going forward to stackoverflow.com

 

이 강의는 파이썬의 자료구조 중 스택과 큐를 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!