스택 & 큐

1. 스택과 큐란?

설명:

• 스택 (Stack):

  • 후입선출 (LIFO): 마지막에 추가된 요소가 가장 먼저 제거되는 자료구조입니다.
  • 사용 예: 브라우저의 뒤로 가기/앞으로 가기, 함수 호출 스택 등.

• 큐 (Queue):

  • 선입선출 (FIFO): 먼저 추가된 요소가 가장 먼저 제거되는 자료구조입니다.
  • 사용 예: 대기열 시스템, 프린터 작업 대기열, 네트워크 패킷 처리 등.

---

2. 벡터로 스택 구현하기

설명:

• 벡터(std::vector)는 기본적으로 동적 배열로 동작하며, 데이터가 추가될 때 항상 마지막에 삽입됩니다.
• 이러한 특성 덕분에 스택의 후입선출(LIFO) 동작을 벡터로 쉽게 구현할 수 있습니다.

---

추가 설명:

• 벡터는 어떻게 스택을 구현하는 데 적합한가?
  • 벡터는 다음과 같은 함수들을 제공합니다:
    • push_back(): 데이터를 벡터의 끝에 추가.
    • pop_back(): 마지막 요소를 제거.
    • back(): 마지막 요소를 반환(읽기 전용).
  • 이 함수들을 조합하면 스택의 push, pop, top 기능을 구현할 수 있습니다.

---

특징 및 동작 원리:

1. 데이터를 추가할 때 push_back()을 호출해 데이터를 삽입합니다.
2. 데이터를 제거할 때 pop_back()으로 마지막 요소를 제거합니다.
3. 최상단 요소를 확인할 때는 back()을 사용합니다.

---

3. 벡터로 큐 구현하기

설명:

• 벡터는 기본적으로 후입선출(LIFO)에 적합한 구조이므로, 선입선출(FIFO)을 구현하려면 추가적인 처리가 필요합니다.
• 선입선출을 구현할 때, 첫 번째 요소를 제거하기 위해 모든 데이터를 앞으로 이동시키는 방식은 비효율적입니다.
• 이를 해결하기 위해 front와 back이라는 인덱스를 사용해 원형 큐(Circular Queue) 방식으로 구현합니다.

---

원형 큐 동작 원리:

1. front 인덱스: 큐의 첫 번째 요소를 가리킵니다.
2. back 인덱스: 큐의 마지막 요소를 가리킵니다.
3. 순환 구조:
   • 데이터가 큐의 끝까지 채워지면, front와 back 인덱스는 다시 벡터의 시작으로 돌아갑니다.
   • 이를 "모듈로 연산 (%)"으로 구현합니다.

---

4. 스택 코드 설명

스택 구현 코드:

template<typename T>
class Stack {
public:
    void push(const T& value) { _container.push_back(value); }
    void pop() { _container.pop_back(); }
    T& top() { return _container.back(); }
    bool empty() { return _container.empty(); }
    int size() { return _container.size(); }
private:
    std::vector<T> _container;
};

코드 설명:

1. push:
   • 데이터를 스택에 추가하는 함수입니다. _container.push_back(value)를 호출해 데이터를 벡터의 끝에 삽입합니다.
2. pop:
   • 스택에서 가장 마지막에 추가된 데이터를 제거합니다. _container.pop_back()를 호출해 벡터의 마지막 요소를 제거합니다.
3. top:
   • 스택의 최상단 요소를 반환합니다. _container.back()를 호출해 벡터의 마지막 요소를 반환합니다.
4. empty:
   • 스택이 비어 있는지 확인합니다. _container.empty()를 호출해 벡터의 크기가 0인지 확인합니다.
5. size:
   • 스택에 저장된 데이터의 개수를 반환합니다. _container.size()를 호출해 벡터의 크기를 반환합니다.

---

5. 큐 코드 설명

큐 구현 코드:

template<typename T>
class Queue {
public:
    Queue() { _container.resize(100); }
    void push(const T& value) {
        if (_size == _container.size()) { /* 예외 처리 */ }
        _container[_back] = value;
        _back = (_back + 1) % _container.size();
        _size++;
    }
    void pop() {
        _front = (_front + 1) % _container.size();
        _size--;
    }
    T& front() { return _container[_front]; }
    bool empty() { return _size == 0; }
    int size() { return _size; }
private:
    std::vector<T> _container;
    int _front = 0, _back = 0, _size = 0;
};

코드 설명:

1. 생성자 (Queue()):

   • 큐의 초기 크기를 100으로 설정합니다. _container.resize(100)를 호출해 벡터의 크기를 초기화합니다.

2. push:

   • 데이터를 큐에 추가합니다.
   • _back 위치에 데이터를 삽입하고, _back 인덱스를 증가시킵니다.
   • _back이 벡터의 끝에 도달하면, 모듈로 연산 (% _container.size())을 통해 다시 처음으로 돌아갑니다.

3. pop:

   • 큐에서 첫 번째 요소를 제거합니다.
   • _front 인덱스를 증가시키고, 마찬가지로 모듈로 연산을 통해 순환 구조를 유지합니다.

4. front:

   • 큐의 첫 번째 요소를 반환합니다. _container[_front]를 호출해 벡터의 _front 위치에 저장된 데이터를 반환합니다.

5. empty:

   • 큐가 비어 있는지 확인합니다. _size == 0이면 비어 있는 상태입니다.

6. size:

   • 큐에 저장된 데이터의 개수를 반환합니다.

---

6. 실용적인 사용 예

• 스택:

  • 웹 브라우저의 "뒤로 가기" 기능, 호출 스택 관리 등.
  • LIFO 동작이 필요한 상황에서 유용.

• 큐:

  • 대기열, 작업 스케줄링, 네트워크 데이터 처리 등.
  • FIFO 동작이 필요한 상황에서 적합.

---