[큐/스택] 기본 개념부터 문제 유형까지

1.  스택 (Stack)

(1) 정의와 성질

 스택은 기본적으로 후입선출(LIFO, Last-In-First-Out) 방식을 따르는 자료구조이다. 즉, 프링글스 통처럼 한 쪽에서만 데이터를 넣는 구조로 가장 마지막에 추가된 원소가 가장 먼저 제거된다! 이러한 특성 때문에 스택은 데이터를 일시적으로 저장하며 저장된 역순으로 접근해야할 때 유용하게 사용된다. 

출처 : geeksforgeeks

(2) 관련 메서드 및 구현 

• 관련 메서드 (C++ 기준) 
  • void push(const T& value);
    • 스택 최상단에 원소를 추가한다.
    • 시간복잡도 : O(1)
  • void pop();
    • 스택 최상단 원소를 제거한다. 
    • 시간복잡도 : O(1)
  • T& top();
    • 스택 최상단 원소를 조회한다.
    • 시간복잡도 : O(1)
  • bool empty();
    • 스택이 비어 있는지 확인한다.
    • 시간복잡도 : O(1)
  • size_t size() : 
    • 스택에 포함된 원소의 수를 나타낸다.
    • 시간복잡도 : O(1)
• 실제로 구현해보기 

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) {
    dat[pos++] = x;
}

void pop() {
    if (pos > 0) pos--;
}

int top() {
    if (pos > 0) return dat[pos - 1];
    return -1; 
}

bool empty() {
    return pos == 0;
}

int size() {
    return pos;
}

---

2.  큐 (Queue)

(1) 정의와 성질 

 큐는 기본적으로 선입선출(FIFO, First-In-First-Out) 방식을 따르는 자료구조이다. 먼저 들어온 요소가 먼저 제거되는 구조이기에 순차적인 데이터 처리를 해야할 때 유용하게 사용된다. 

출처 : geeksforgeeks

(2) 관련 메서드 및 구현

• 관련 메서드 (C++ 기준) 
  • void push(const T& value);
    • 큐의 끝에 원소를 추가한다.
    • 시간복잡도 : O(1)
  • void pop();
    • 큐의 front에 해당하는 원소를 제거한다.
    • 시간복잡도 : O(1)
  • T& front();
    • 큐의 가장 앞에 있는 원소를 조회한다.
    • 시간복잡도 : O(1)
  • bool empty();
    • 큐가 비었는지 확인한다.
    • 시간복잡도 : O(1)
  • size_t size();
    • 큐에 포함된 원소의 수를 나타낸다. 
    • 시간복잡도 : O(1)
• 실제로 구현해보기 

const int MX = 1000005;
int dat[MX];
int head = 0;
int tail = 0;

void push(int x) {
    dat[tail++] = x;
}

void pop() {
    if (head != tail) {  
        head++;
    }
}

int front() {
    if (head != tail) {  
        return dat[head];
    }
    return -1; 
}

bool empty() {
    return head == tail;  
}

int size() {
    return tail - head;  
}

---

3. 문제 유형 

(1) 스택

 문제에서 많이 사용되지만 단독으로 사용되는 경우는 적다. 후입선출의 단서가 주어졌을 때 주로 활용되는데, 관련 문제를 풀어보며 감을 잡아보자-! 특히 직전에 넣은 값과 새로 입력 받은 값을 비교하여 작업해야 하는 경우가 많이 활용된다.

 

• [백준] 2493 탑 C++ (골드 5)
  • 문제 풀이 바로가기
• [백준] 옥상 정원 꾸미기 (골드 5)
  • 문제 풀이 바로가기

• [프로그래머스] 주식 가격 (Lv. 2)
  • 문제 풀이 바로가기 

(2) 큐 

 스택과 마찬가지로 단독으로 사용되는 경우가 선입선출의 단서가 주어졌을 때 주로 활용된다! 특히 집단적으로 구분할 때 많이 활용된다.

• [프로그래머스] 기능개발 (Lv. 2)
  • 문제 풀이 바로가기