선형 자료구조 탐구: 스택, 큐, 덱으로 배우는 알고리즘 기초

스터디 2주차입니다.
이번에는 선형 자료구조가 무엇인지? 와 기본적인 선형 자료구조중 스택 & 큐 그리고 덱이 무엇인지 알아보겠습니다
그리고 문제도 풀어보면서 언제 사용하게 되는지 고민해보는 시간이 되었으면 좋겠네요. 😆

 

1. 선형 자료구조란?

선형 자료구조

선형 자료구조는 데이터가 일렬로 나열된 형태로 저장되는 구조를 말하는데, 이러한 구조는 앞의 요소와 뒤의 요소 간에 1 : 1의 선형적인 관계를 통해 순차적인 접근과 처리가 용이한 장점이 있습니다. 대표적으로 배열, 연결 리스트, 스택, 큐를 예로 들 수 있습니다.

선형 자료구조 중 꼭 알아야하는 스택, 큐 그리고 덱까지 알아보겠습니다.

 

2. 스택을 알아보자

스택 자료구조

 

스택은 LIFO(Last In, First Out) 원칙을 따르는 자료구조로, 가장 최근에 삽입된 데이터가 가장 먼저 삭제됩니다.

함수 호출, 실행 취소, 역순 문자열 처리, 괄호 검사 등 가장 최근에 넣은 원소를 알아야 하는 작업에 유용하게 사용할 수 있습니다.

 

2.1. 스택 사용 & 추상 데이터 타입(Abstract Data Type)

스택을 사용하기에 앞서 스택의 기능을 정의한 추상 데이터 타입을 먼저 알아보겠습니다.

 

추상 데이터 타입

 

• push(data) : 스택의 맨 위에 요소 x를 추가합니다.
• pop() : 스택의 맨 위 요소를 제거합니다.
• top() or peek() : 스택의 맨 위 요소를 반환합니다.
• isEmpty() : 스택이 비어 있는지 확인합니다.

스택 구현

#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;

template <typename T>
class Stack {
 private:
  // 스택은 동적배열(vector)로 구현 할 수 있음
  vector<T> elements;

 public:
  void push(const T& element) { elements.push_back(element); }

  void pop() {
    if (elements.empty()) {
      throw out_of_range("Stack<>::pop(): empty stack");
    }
    elements.pop_back();
  }

  T top() const {
    if (elements.empty()) {
      throw out_of_range("Stack<>::top(): empty stack");
    }
    return elements.back();
  }

  bool isEmpty() const { return elements.empty(); }
};

int main() {
  Stack<int> stack;
  stack.push(10);
  stack.push(20);
  stack.push(30);

  while (!stack.isEmpty()) {
    cout << stack.top() << " ";
    stack.pop();
  }

  return 0;
}

 

 

 

2.2. 코딩 테스트 문제 풀이 (c++ STL 스택 사용)

백준 10799번 쇠막대기 문제 링크 :

https://www.acmicpc.net/problem/10799

 

소스코드 공유 : 

http://boj.kr/46e7d0fecfe54be9971183b96008c0cb

 

3. 큐를 알아보자

큐 자료구조

 

큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.

작업 예약, 프린터 대기열, BFS(너비 우선 탐색) 등 들어온 순서대로 처리해야 할 때 유용하게 사용할 수 있습니다.

 

3.1. 큐 사용 & 추상 데이터 타입(Abstract Data Type)

큐을 사용하기에 앞서큐의 기능을 정의한 추상 데이터 타입을 먼저 알아보겠습니다.

 

추상 데이터 타입

 

• enqueue(data) : 큐의 끝에 요소(data)를 추가합니다.
• dequeue() : 큐의 앞 요소를 제거합니다.
• front() or peek() : 큐의 앞 요소를 반환합니다.
• isEmpty() : 큐가 비어 있는지 확인합니다.

 

큐 구현

#include <iostream>
#include <list>
#include <stdexcept>
using namespace std;

template <typename T>
class Queue {
 private:
  // STL list(링크드 리스트)를 활용해서 구현할 수 있음
  list<T> elements;

 public:
  void enqueue(const T& element) { elements.push_back(element); }

  void dequeue() {
    if (elements.empty()) {
      throw out_of_range("Queue<>::dequeue(): empty queue");
    }
    elements.pop_front();
  }

  T front() const {
    if (elements.empty()) {
      throw out_of_range("Queue<>::front(): empty queue");
    }
    return elements.front();
  }

  bool isEmpty() const { return elements.empty(); }
};

// 테스트
int main() {
  Queue<int> queue;
  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);

  // 앞(front)에서 부터 출력
  while (!queue.isEmpty()) {
    cout << queue.front() << " ";
    queue.dequeue();
  }

  return 0;
}

 

3.2. 코딩 테스트 문제 풀이 (c++ STL 큐 사용)

백준 1158번 요세푸스 문제 링크 :

https://www.acmicpc.net/problem/1158

 

소스코드 공유 : 

http://boj.kr/f855328cefd3439da462f33782a44c26

 

4. 덱을 알아보자

덱 자료구조

 

덱(Deque, Double-ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다.

앞뒤로 데이터를 자유롭게 추가하고 삭제해야 하는 작업, 예를 들어 슬라이딩 윈도우, 캐시 구현, 양방향 탐색 등에 유용하게 사용됩니다.

 

4.1. 덱 사용 & 추상 데이터 타입(Abstract Data Type)

덱을 사용하기에 앞서 덱의 기능을 정의한 추상 데이터 타입을 먼저 알아보겠습니다.

 

추상 데이터 타입

 

• pushFront(data) : 덱의 앞에 요소(data)를 추가합니다.
• pushBack(data) : 덱의 뒤에 요소(data)를 추가합니다.
• popFront() : 덱의 앞 요소를 제거합니다.
• popBack() : 덱의 뒤 요소를 제거합니다.
• front() : 덱의 앞 요소를 반환합니다.
• back() : 덱의 뒤 요소를 반환합니다.
• isEmpty() : 덱이 비어 있는지 확인합니다.

 

덱 구현

#include <iostream>
#include <list>
#include <stdexcept>
using namespace std;

template <typename T>
class Deque {
 private:
  // STL list(링크드 리스트)를 활용해서 구현할 수 있음
  list<T> elements;

 public:
  void pushFront(const T& element) { elements.push_front(element); }

  void pushBack(const T& element) { elements.push_back(element); }

  void popFront() {
    if (isEmpty()) {
      throw out_of_range("Deque<>::popFront(): empty deque");
    }
    elements.pop_front();
  }

  void popBack() {
    if (isEmpty()) {
      throw out_of_range("Deque<>::popBack(): empty deque");
    }
    elements.pop_back();
  }

  T front() const {
    if (isEmpty()) {
      throw out_of_range("Deque<>::front(): empty deque");
    }
    return elements.front();
  }

  T back() const {
    if (isEmpty()) {
      throw out_of_range("Deque<>::back(): empty deque");
    }
    return elements.back();
  }

  bool isEmpty() const { return elements.empty(); }

  size_t getSize() const { return elements.size(); }
};

// 테스트
int main() {
  Deque<int> deque;
  deque.pushFront(10);
  deque.pushBack(20);
  deque.pushFront(5);
  deque.pushBack(30);

  // 앞(front)에서 부터 출력
  while (!deque.isEmpty()) {
    cout << deque.front() << " ";
    deque.popFront();
  }

  return 0;
}

 

4.2. 코딩 테스트 문제 풀이 ((c++ STL 큐 사용)

백준 2346번 풍선 터뜨리기 문제 링크 :

https://www.acmicpc.net/problem/2346

 

소스코드 공유 :

http://boj.kr/4b327bd602e1417dae4dc2258892d156

 

5. 마치며...

코딩테스트 합격자되기 c++편 강와 스택&큐 그리고 덱 까지 자료를 찾아보면서 정리했습니다.
부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해주시면 감사하겠습니다. 🙏

 

하얀종이 개발자

Reference

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0 - 위키피디아 자료구조

https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 - 위키피디아 스택

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84 - 위키피디아 큐

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84 - 위키피디아 덱

https://learn.microsoft.com/ko-kr/cpp/standard-library/stack?view=msvc-170 - microsoft c++ STL(표준 라이브러리) 문서

https://www.acmicpc.net/problem/10799 - 백준 10799번 쇠막대기 문제

https://www.acmicpc.net/problem/1158 - 백준 1158번 요세푸스 문제

https://www.acmicpc.net/problem/2346 - 백준 2346번 풍선터뜨리기 문제
https://www.youtube.com/watch?v=-TGCT74wFeg&t=1538s - 코딩테스트 합격자되기 c++편 (스택 & 큐 유튜브 강의)