1. 스택 (Stack)
스택은 LIFO (Last In First Out) 구조를 따르는 자료구조로, 마지막에 들어간 데이터가 가장 먼저 나오는 구조입니다. 즉, 데이터를 쌓아 올린다고 생각할 수 있으며, 마지막에 추가한 데이터부터 꺼낼 수 있습니다. 쉽게 말해, 순서가 보존되는 선형 데이터 구조입니다.
• 주요 연산:
o Push: 데이터를 스택의 맨 위에 추가하는 작업.
o Pop: 스택의 맨 위에 있는 데이터를 제거하는 작업.
• 예시:
o 함수 호출 스택: 프로그램이 실행될 때 함수가 호출되면 스택에 쌓이고, 함수가 종료되면 맨 위에 쌓인 함수부터 제거됩니다. 예를 들어, 함수 A가 B를 호출하고, B가 C를 호출했다면, 함수 C가 먼저 실행을 마치고 제거되며, 그다음 B, 마지막으로 A가 제거됩니다.
o 뒤로 가기 기능: 웹 브라우저에서 방문 기록을 스택으로 관리합니다. 가장 최근 페이지부터 거꾸로 돌아갈 수 있습니다.
• 상세 설명:
o 스택의 특징: 스택은 가장 최근에 추가된 데이터만 접근할 수 있습니다. 즉, 중간에 있는 데이터를 직접 접근할 수 없고, 필요한 경우 모든 상위 데이터들을 Pop해서 제거해야 합니다.
o 장점: 특정 상황에서는 필요한 데이터만 바로 꺼낼 수 있어 효율적입니다.
o 단점: 데이터 접근에 제약이 있어, 중간의 데이터를 쉽게 활용하기 어렵습니다.
2. 큐 (Queue)
큐는 FIFO (First In First Out) 구조를 따르는 자료구조로, 먼저 들어간 데이터가 가장 먼저 나오는 구조입니다. 즉, 데이터를 순서대로 넣고 꺼내는 대기열과 비슷합니다.
• 주요 연산:
o Enqueue: 데이터를 큐의 뒤쪽에 추가하는 작업.
o Dequeue: 큐의 앞쪽에서 데이터를 제거하는 작업.
• 예시
o 대기열: 줄을 서서 기다리는 상황과 같습니다. 먼저 온 사람이 먼저 서비스를 받습니다.
o 프린터 작업 큐: 프린터는 작업이 요청된 순서대로 인쇄를 수행합니다. 첫 번째로 요청된 작업이 완료되면 그다음 작업이 인쇄됩니다.
• 상세 설명:
o 큐의 특징: 큐는 데이터를 넣고 빼는 위치가 고정되어 있어 먼저 들어온 데이터가 먼저 제거됩니다. 스택과 달리 데이터 접근이 양쪽(앞과 뒤)에서 이뤄지므로 대기열 관리에 적합합니다.
o 장점: 순차적으로 작업을 처리해야 할 때 적합합니다.
o 단점: 특정 위치의 데이터에 직접 접근하기 어렵고, 무조건 맨 앞의 데이터부터 제거해야 합니다.
우선순위 큐(Priority Queue)
✅ 일반적인 큐는 데이터를 선입선출(FIFO) 방식으로 처리하여, 먼저 들어온 데이터가 먼저 나가게 됩니다. 그러나 모든 상황에서 이러한 순서가 적합한 것은 아닙니다. 예를 들어 응급실에서 환자를 진료할 때는 도착 순서보다는 위급한 환자를 먼저 치료해야 합니다.
=> 이렇게 순서뿐만 아니라 각 데이터의 우선순위에 따라 처리 순서가 달라져야 하는 경우, 큐의 확장 개념인 우선순위 큐(Priority Queue)가 필요합니다.
우선순위 큐(Priority Queue)와 힙(Heap)은 데이터의 우선순위에 따라 작업을 처리해야 하는 상황에서 사용되는 자료구조입니다. 우선순위 큐는 주로 힙을 통해 구현됩니다
우선순위 큐는 각 요소에 우선순위를 부여하고, 우선순위가 높은 요소부터 처리하는 데이터 구조입니다.일반적인 큐와 달리, 우선순위 큐는 특정 요소를 꺼낼 때 항상 가장 높은 우선순위를 가진 요소를 꺼내도록 합니다.
• 우선순위 큐 구현 방법:
o 힙을 사용한 구현: 우선순위 큐는 주로 최대 힙 또는 최소 힙을 사용하여 구현됩니다. 최대 힙을 사용하면 높은 우선순위를 가진 데이터가 루트에 위치하게 되고, 최소 힙을 사용하면 낮은 우선순위를 가진 데이터가 루트에 위치하게 됩니다.
o 연결 리스트나 배열: 간단한 우선순위 큐는 정렬된 연결 리스트나 배열을 사용해 구현할 수 있지만, 삽입과 삭제의 성능이 좋지 않기 때문에 힙이 더 일반적으로 사용됩니다.
우선순위 큐의 주요 연산
1. 삽입(Insert): 새로운 요소를 우선순위 큐에 추가합니다.
o 힙의 성질을 유지하기 위해 요소를 추가한 후 힙ify(조정) 작업이 필요합니다.
2. 최대/최소 추출(Extract Max/Min): 현재 우선순위가 가장 높은 요소를 꺼내고, 힙을 재구성합니다.
o 루트 노드를 제거한 후, 마지막 노드를 루트에 위치시키고 다시 힙ify 작업을 통해 성질을 유지합니다.
3. 최대/최소 조회(Peek): 현재 우선순위가 가장 높은 요소를 반환하되, 제거하지는 않습니다.
o 루트 노드의 값을 반환합니다.
힙(Heap)의 개념
힙은 완전 이진 트리로 구성된 자료구조로, 각 노드의 값이 특정 조건을 만족하는 경우를 말합니다. 주로 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나누어집니다.
• 최대 힙 (Max Heap):
o 힙의 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다. 즉, 루트 노드가 가장 큰 값을 가집니다.
o 예를 들어, 다음과 같은 트리 구조는 최대 힙입니다
• 최소 힙 (Min Heap):
o 힙의 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 합니다. 즉, 루트 노드가 가장 작은 값을 가집니다.
o 예를 들어, 다음과 같은 트리 구조는 최소 힙입니다:
힙의 중요한 특징은 데이터가 추가되거나 제거될 때마다 힙의 성질이 유지되도록 조정된다는 점입니다. 이는 삽입(Insert) 및 삭제(Delete) 작업을 통해 이루어집니다.
큐(Queue)와 스택(Stack): 선입선출과 후입선출의 차이
큐(Queue)와 스택(Stack)은 데이터 처리 방식에서 중요한 차이를 가지고 있습니다.
큐는 선입선출(FIFO, First In First Out) 구조로, 먼저 들어온 데이터가 먼저 처리되는 특징이 있습니다. 이 때문에, 멀티스레딩의 작업 스케줄링이나 대기열 시스템(예: 프린터 대기열, 고객 서비스)과 같이 순서가 중요한 시스템에서 큐가 유용합니다.
반면, 스택(Stack)은 후입선출(LIFO, Last In First Out) 구조로, 마지막에 들어온 데이터가 먼저 처리됩니다. 스택은 최근 작업을 먼저 처리해야 하는 상황에서 적합합니다.
🔎 큐와 멀티스레딩에서의 스레드 관리
멀티스레딩 환경에서는 여러 개의 스레드가 동시에 작업을 수행하기 때문에 작업의 순서 관리와 스레드 간의 자원 접근을 효율적으로 관리하는 것이 중요합니다. 큐는 이러한 상황에서 스레드를 선착순(FIFO)으로 처리하는 데 유용합니다.
• 스레드 작업 스케줄링: 여러 스레드가 동시에 실행될 때, 큐에 작업을 순서대로 추가하고, 스레드를 하나씩 꺼내서 처리하는 방식으로 작업 순서를 보장합니다.
• 자원 접근 대기열 관리: 특정 자원을 여러 스레드가 동시에 접근하려고 할 때, 큐를 사용해 스레드들이 순차적으로 자원을 접근하도록 관리할 수 있습니다.
스택을 사용한다면, 가장 마지막에 들어온 스레드가 먼저 실행되기 때문에 스레드 간의 실행 순서가 뒤죽박죽될 수 있습니다. 스택의 LIFO 구조는 작업이 쌓이는 순서에 따라 실행되므로, 대기열과 같은 FIFO 구조에는 맞지 않습니다.
🔎 큐와 대기열 시스템의 관
대기열 시스템(Queueing System)은 고객이나 작업이 도착한 순서대로 처리되는 것을 보장해야 합니다. 예를 들어, 프린터 대기열이나 고객 서비스에서는 먼저 요청한 작업이 먼저 처리되는 것이 자연스럽습니다. 큐는 FIFO 구조를 통해 이러한 특성을 구현합니다.
• 우선순위 보장: 큐는 먼저 요청된 작업이 먼저 처리될 수 있도록 하여, 서비스의 공정성을 유지합니다.
• 대기열 순서 유지: 요청이 큐에 추가된 순서대로 처리하므로, 각 작업이 순차적으로 완료될 수 있습니다.
스택을 사용한다면, 가장 마지막에 들어온 요청이 먼저 처리되므로 대기열에서의 순서가 보장되지 않습니다. 이는 대기열 관리의 본질에 어긋나기 때문에, 대기열 관리 시스템에서는 큐가 선호됩니다.
Referance
https://bnzn2426.tistory.com/115
https://suyeon96.tistory.com/31
https://velog.io/@leejuhwan/%EC%8A%A4%ED%83%9DSTACK%EA%B3%BC-%ED%81%90QUEUE
