스택(Stack) 큐(Queue)에 대해서 알아보자

스택(Stack) 큐(Queue)에 대해서 알아보자

스택(Stack)이란?

📍 스택의 개념

스택이란 쌓아 올린다는 것을 의미한다. 따라서 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

📍 스택의 특징

• 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
• 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
• 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

📍 스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

📍 스택 구현 코드

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if self.top is None:
            return None
        topNode = self.top
        self.top = self.top.next
        return topNode.item

    def is_empty(self):
        return self.top is None

---

큐(Queue)이란?

📌 큐의 개념

Queue 의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것을 의미한다.
따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이
선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.

📌 큐의 특징

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여
각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

📌 큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

📍 큐 구현 코드

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        if not self.front:
            self.front = Node(value, None)
            return

        node = self.front
        while node and node.next:
            node = node.next
        node.next = Node(value, None)


    def pop(self):
        if self.front is None:
            return None
        frontNode = self.front
        self.front = self.front.next
        return frontNode.item

    def is_empty(self):
        return self.front is None

---

참고자료

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

https://jud00.tistory.com/entry/

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!