TIL - 2024/06/18

스택(Stack)

데이터를 순서대로 쌓아 올리는 구조 , FILO or LIFO 구조 , 나중에 추가된 데이터가 가장 먼저 제거된다는 뜻

스택의 주요 연산

1. Push: 데이터를 스택의 맨 위에 추가하는 연산
2. Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산
3. Peek/Top: 스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 연산
4. IsEmpty: 스택이 비어 있는지 확인하는 연산
5. Size: 스택에 있는 데이터의 개수를 반환하는 연산

ex) 스택이 빈 상태에서 1, 2, 3 순으로 데이터를 push하면 스택은 [1, 2, 3]이 된다.

이 상태에서 pop을 호출하면 3이 제거되고 반환되며, 스택은 [1, 2]가 된다.

 

스택의 활용 예시

스택은 다양한 알고리즘과 문제 해결에 활용된다. 몇 가지 대표적인 활용 예시는 다음과 같음

1. 함수 호출 관리: 함수 호출 시 스택 프레임을 사용하여 각 함수 호출의 상태를 관리
2. 수식 계산: 중위 표기식을 후위 표기식으로 변환하거나, 후위 표기식을 계산할 때 사용
3. 문자열 역순 변환: 문자열을 스택에 넣고 역순으로 출력하여 문자열을 뒤집을 수 있음
4. 괄호 검사: 수식의 괄호가 올바르게 열리고 닫혔는지 확인할 때 사용
5. 탐색 알고리즘: 깊이 우선 탐색(DFS)과 같은 알고리즘에서 사용

예시코드

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()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from empty stack")

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

# 스택 사용 예시
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 출력: 3
print(stack.peek()) # 출력: 2

 

 

큐(Queue)

선입선출(FIFO, First In First Out) 구조,데이터를 일렬로 나열하고, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조

일상생활에서 줄을 서는 것과 유사하다. 

대기열 관리, 작업 스케줄링, 너비 우선 탐색(BFS) 등 다양한 응용 분야에서 사용

 

큐의 종류

1. 일반 큐 (Queue):
   • 선입선출(FIFO) 구조를 따르는 가장 기본적인 큐.
2. 원형 큐 (Circular Queue):
   • 일반 큐와 비슷하지만, 마지막 위치가 처음 위치로 연결되어 원형 구조를 가집니다. 메모리 공간을 효율적으로 사용
3. 우선순위 큐 (Priority Queue):
   • 데이터에 우선순위를 부여하여, 우선순위가 높은 데이터가 먼저 처리됩니다. 최소 힙이나 최대 힙을 사용하여 구현
4. 덱 (Deque, Double-ended Queue):
   • 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다. 앞쪽과 뒤쪽 모두에서 enqueue와 dequeue 연산을 수행 가능

 

기술면접에 대해 정리 했다. 더욱 정리해서 올릴 예정이다.

https://kiseokkm.tistory.com/83

[CS] 개발자 면접 대비: 내 마음대로 기술 질문 정리 ①