[코딩 테스트 합격자 되기] C++ - stack,queue

 

해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다. 

 

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

 

 

 

💬키워드

스택 : 가장 마지막에 추가한 항목이 가장 먼저 제거되는, 데이터가 쌓이는 구조의 컨테이너

큐 : 가장 마지막에 추가한 항목이 가장 마지막에 제거되는, 선착순 형태의 컨테이너

 

 

🪄목차

 

https://www.youtube.com/watch?v=xc0HZiqh8Fs

 

1. 스택(Stack)

2. 큐(Queue)

 

📝내용

 

스택(Stack)

1. 정의

- 중복을 허용하는 순서가 있는 컨테이너 자료구조

- LIFO(Last In First Out), 최근에 들어온 원소가 먼저 삭제됨, 후입선출

- 삽입/삭제 : O(1)

- 탐색 및 임의 접근은 불가능하다.

 

출처 :  https://www.youtube.com/watch?v=agQQyKd0HBQ

 

 

 

 

2. 사용법

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################
#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;
    
    // 원소 삽입
    s.push(1);  // push: 스택의 맨 위에 원소를 추가합니다. 예를 들어, 1을 추가하면 스택의 상태는 [1]이 됩니다. 시간복잡도: O(1)
    s.push(2);  // push: 스택의 맨 위에 원소를 추가합니다. 예를 들어, 2를 추가하면 스택의 상태는 [1, 2]가 됩니다. 시간복잡도: O(1)
    s.push(3);  // push: 스택의 맨 위에 원소를 추가합니다. 예를 들어, 3을 추가하면 스택의 상태는 [1, 2, 3]이 됩니다. 시간복잡도: O(1)
    
    // 맨 위 원소 확인
    cout << "Top element: " << s.top() << endl; // 출력: 3
    // top: 스택의 맨 위 원소를 반환합니다. 스택이 비어 있으면 예외를 던집니다. 예를 들어, 현재 스택의 상태는 [1, 2, 3]이므로 top()은 3을 반환합니다. 시간복잡도: O(1)
    
    // 원소 삭제
    s.pop();  // pop: 스택의 맨 위 원소를 제거합니다. 스택이 비어 있으면 예외를 던집니다. 예를 들어, 현재 스택의 상태는 [1, 2, 3]이므로 pop()은 3을 제거하여 [1, 2]가 됩니다. 시간복잡도: O(1)
    cout << "Top element after pop: " << s.top() << endl; // 출력: 2
    // top: 스택의 맨 위 원소를 반환합니다. 스택이 비어 있으면 예외를 던집니다. 예를 들어, 현재 스택의 상태는 [1, 2]이므로 top()은 2를 반환합니다. 시간복잡도: O(1)
    
    // 스택이 비어있는지 확인
    if (!s.empty()) {
        cout << "Stack is not empty" << endl; // 출력: Stack is not empty
    }
    // empty: 스택이 비어 있는지 여부를 확인합니다. 비어 있으면 true, 아니면 false를 반환합니다. 예를 들어, 현재 스택의 상태는 [1, 2]이므로 empty()는 false를 반환합니다. 시간복잡도: O(1)
    
    // 스택의 크기 확인
    cout << "Stack size: " << s.size() << endl; // 출력: 2
    // size: 스택에 있는 원소의 개수를 반환합니다. 예를 들어, 현재 스택의 상태는 [1, 2]이므로 size()는 2를 반환합니다. 시간복잡도: O(1)

    // 스택에서 모든 원소를 pop하여 출력
    while (!s.empty()) {
        cout << "Popping element: " << s.top() << endl;
        s.pop();
    }
    // 반복문을 통해 모든 원소를 제거합니다. 예를 들어, 현재 스택의 상태는 [1, 2]이므로 pop()은 2와 1을 순서대로 제거합니다. 시간복잡도: O(1)

    // 스택이 비어있는지 확인
    if (s.empty()) {
        cout << "Stack is empty after popping all elements" << endl; // 출력: Stack is empty after popping all elements
    }
    // empty: 스택이 비어 있는지 여부를 확인합니다. 비어 있으면 true, 아니면 false를 반환합니다. 예를 들어, 현재 스택의 상태는 빈 상태이므로 empty()는 true를 반환합니다. 시간복잡도: O(1)

    return 0;
}

/*
* 각 메서드의 동작 및 시간복잡도:
* - push: 스택의 맨 위에 원소를 추가합니다. 삽입된 원소는 기존 원소 위에 쌓이게 됩니다.
*   예를 들어, push(3)를 호출하면 스택의 상태는 [1, 2, 3]이 됩니다. 시간복잡도: O(1)
* - pop: 스택의 맨 위 원소를 제거합니다. 가장 최근에 추가된 원소가 제거됩니다.
*   예를 들어, pop()을 호출하면 스택의 상태는 [1, 2]가 됩니다. 시간복잡도: O(1)
* - top: 스택의 맨 위 원소를 반환합니다. 스택이 비어 있으면 예외를 던집니다.
*   예를 들어, top()을 호출하면 현재 스택의 맨 위 원소 2가 반환됩니다. 시간복잡도: O(1)
* - empty: 스택이 비어 있는지 여부를 확인합니다. 스택이 비어 있으면 true, 아니면 false를 반환합니다.
*   예를 들어, 스택이 비어 있지 않으면 empty()는 false를 반환합니다. 시간복잡도: O(1)
* - size: 스택에 있는 원소의 개수를 반환합니다. 예를 들어, size()는 현재 스택에 2개의 원소가
*   있으므로 2를 반환합니다. 시간복잡도: O(1)
*/

/*
* 스택을 사용해야 하는 경우:
* - 함수 호출이나 재귀 호출의 관리를 위해 (콜 스택)
* - 괄호의 짝을 맞추거나 문자열의 역순 변환 등 LIFO 구조가 필요한 경우
* - Depth-First Search(DFS)와 같은 알고리즘 구현 시

* 스택을 사용하지 말아야 하는 경우:
* - 임의 접근이 필요한 경우 (스택은 특정 위치의 원소 접근이 불가능)
* - 중간 위치의 삽입/삭제가 빈번한 경우 (스택은 맨 위에서만 삽입/삭제 가능)
* - FIFO(First In First Out) 구조가 필요한 경우 (큐 사용 권장)
*/

 

---

 

큐(Queue)

1. 정의

- 중복을 허용하는 순서가 있는 선형 데이터 구조

- FIFO(First In First Out), 먼저 들어온 원소가 먼저 삭제됨(선착순)

- 삽입/삭제 : O(1)

- 탐색 및 임의 접근 불가능

 

출처 :  https://www.youtube.com/watch?v=agQQyKd0HBQ

2. 사용법

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################
#include <iostream>
#include <queue>

using namespace std;

// std::queue는 C++ STL에 포함된 컨테이너 어댑터입니다.
// - FIFO(First-In-First-Out) 원칙에 따라 동작하는 데이터 구조입니다.
// 좋은 사용 시기:
// - 데이터를 순서대로 처리해야 할 때, 예를 들면, 너비 우선 탐색(BFS) 알고리즘, 대기열 구현 등.
// 성능 이슈:
// - STL queue는 일반적으로 빠른 연산을 제공합니다. 하지만, 중간 요소에 직접 접근할 수 없습니다. 중간 요소를 검색하거나 수정하려면 다른 자료구조를 사용하는 것이 좋습니다.

int main() {

    queue<int> q;

    // push: 큐의 끝에 요소 추가, O(1)
    q.push(1);
    q.push(2);
    q.push(3);

    // front: 큐의 첫 번째 요소에 접근, O(1)
    cout << "Front element: " << q.front() << endl;  // 출력: Front element: 1

    // pop: 큐의 첫 번째 요소 제거, O(1)
    q.pop();
    cout << "Front element after pop: " << q.front() << endl;  // 출력: Front element after pop: 2

    // empty: 큐가 비어 있는지 확인, O(1)
    if (!q.empty()) {
        cout << "Queue is not empty" << endl;  // 출력: Queue is not empty
    }

    // size: 큐의 크기 확인, O(1)
    cout << "Queue size: " << q.size() << endl;  // 출력: Queue size: 2

    // 성능 저하 예제:
    // queue는 중간 요소에 직접 접근할 수 없으므로, 중간 요소를 검색하거나 수정하는 연산이 필요한 경우 
    // queue보다는 다른 자료 구조를 사용하는 것이 좋습니다.
   
    return 0;

}