Soyulia's Blog

[자료구조] 스택과 큐

Soyulia's photo
Soyulia
·

2 min read

목표 : 스택 , 큐 개념과 기본 구현 코드에 대해 알아보자.

✏️스택

  • 스택의 데이터 구조

    LIFO(Last In First Out) 원칙 : 스택 내부에 마지막에 들어간 요소가 먼저 제거됨.

  1. push : 스택 맨 위에 항목을 올리는 것
    pop : 스택의 맨 위에서 항목을 제거하는 것
    IsEmpty : 스택이 비어있는지 확인
    IsFull : 스택이 가득 찼는지 확인
    Peek : 최상위 요소를 제거하지 않고 값을 가져옴

  2. Top = -1 : 비어있는지 확인하기 위한 비교값

  • 구현 코드

# 스택 생성
def create_stack():
    stack = []
    return stack
# 빈 스택 
def check_empty(stack):
    return len(stack) == 0
# 스택에 항목 추가
def push(stack, item):
    stack.append(item)
    print("pushed item :" + item)
#스택에서 항목 제거
def pop(stack):
    if(check_empty(stack)):
        return "empty"
    return stack.pop()

stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("poped item:" + pop(stack))

  • 언제 사용할까?

  1. 브라우저에서 뒤로 가기 할 때 pop

  2. 문자 거꾸로 바꾸고 싶을 때

✏️큐

  • 큐의 대기열 데이터 구조

    FIFO(First In First Out) 원칙 : 먼저 들어간 항목이 먼저 나오게 됨.

  1. Enqueue : 큐의 끝 요소에 추가
    Dequeue : 큐의 맨 앞 요소를 제거
    IsEmpty : 대기열이 비어있는지 확인
    IsFull : 대기열이 가득 찼는지 확인
    Peek : 큐의 앞부분을 제거하지 않고 값 가져옴

  2. -1 : '비어 있다' 의미

  3. 값이 추가 될 수록 뒤를 의미하는 REAR가 점점 커짐

  4. 값이 빠질 수록 앞을 의미하는 FRONT가 점점 커짐

# 큐 생성
class Queue : 
    def __init__(self):
        self.queue = []
    # 큐에 항목 넣기
    def enqueue(self, item):
        self.queue.append(item)
    # 큐에 항목 제거
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)
    # 현재 큐 보여주기
    def display(self):
        print(self.queue)
    def size(self):
        return len(self.queue)
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.display()
q.dequeue()

print("After removing an element")
q.display()

  • 언제 사용할까?

  1. 콜센터 전화 시스템은 전화를 건 사람들을 순서대로 유지

  2. CPU 스케줄링

  3. 실시간 시스템 인터럽트 처리

stackqueue