[C++] vector(리스트)의 사용법 (Stack, Queue 알고리즘 예제)

안녕하세요. 명월입니다.

이 글은 C++에서 사용되는 vector(리스트)의 사용법 (Stack, Queue 알고리즘 예제)에 대한 글입니다.

예전에 제가 배열의 사용법에 대해서 설명한 적이 있습니다.

링크 - [C++] 배열과 포인터(메모리 주소) 그리고 할당(new){stack과 heap에 대해서}

배열은 같은 타입의 데이터를 복수개 선언하여 하나의 변수로 다루는 방법을 이야기합니다. 그런데 이 배열은 사용하기 전에 몇개를 사용할 것인지 정해 놓은 다음 사용합니다.

즉, 10개의 int형이라고 하면 int a[10];식으로 사용되지만 만약 여기에서 10개가 넘어서게 된다면 변수를 재선언 해야 할 것입니다.

그러나 이러한 문제점을 해결한 알고리즘이 연결리스트인데 그것은 C++에서 vector 클래스로 사용됩니다.

#include <stdio.h>
#include <iostream>
// vector를 사용하기 위해서는 추가한다.
#include <vector>
using namespace std;
// 실행 함수
int main()
{
  // 문자열 형으로 vector를 선언한다.
  vector<const char*> data1;
  // vector에 데이터를 삽입한다.
  data1.push_back("Hello,");
  // vector에 데이터를 삽입한다.
  data1.push_back("world");
  // vector에 데이터를 삽입한다.
  data1.push_back("how are you?");
  // 콘솔 출력
  cout << "data1 result " << endl;
  // data1.size()는 vector에 삽입된 노드 개수
  // 개수만큼 반복하여 출력한다.
  for (int i = 0; i < data1.size(); i++)
  {
    // 콘솔 출력
    cout << data1[i] << " ";
  }
  // 콘솔 개행 출력
  cout << endl;
  // int 형 vector를 선언한다.
  // 배열 형식으로 입력 해도 삽입된다.
  vector<int> data2 = { 1,2,3,4,5,6,7 };
  // 콘솔 출력
  cout << "data2 result " << endl;
  // iterator형식으로 begin(), end()를 사용해서 포인터를 이용한다.
  for (vector<int>::iterator ptr = data2.begin(); ptr < data2.end(); ptr++)
  {
    // 콘솔에 포인터 값을 출력한다.
    cout << *ptr << " ";
  }
  // 콘솔 개행 출력
  cout << endl;
  // data2의 첫번째 값 출력
  cout << "first - " << data2.front() << endl;
  // data2의 마지막 값 출력
  cout << "last - " << data2.back() << endl;

  // 5번째에 10 배열을 추가한다.
  data2.insert(data2.begin() + 5, { 10 });
  // 콘솔 출력
  cout << "data2 result (insert) " << endl;
  // iterator형식으로 포인터를 이용한다.
  // cbegin(), cend()를 사용하면 const 타입으로 값을 수정할 수 없다.
  for (auto ptr = data2.cbegin(); ptr < data2.cend(); ptr++)
  {
    // 콘솔에 포인터 값을 출력한다.
    cout << *ptr << " ";
  }
  // 콘솔 개행 출력
  cout << endl;

  // int 형 vector를 선언한다.
  vector<int> data3 = { 1 };
  // data2와 data3의 바꿔치기!
  data3.swap(data2);
  // data3의 값 출력
  cout << "data3 result (swap) " << endl;
  // iterator형식으로 포인터를 이용한다.
  // rbegin(), rend()를 사용하면 역순으로 반복한다.
  for (auto ptr = data3.rbegin(); ptr < data3.rend(); ptr++)
  {
    // 콘솔에 포인터 값을 출력한다.
    cout << *ptr << " ";
  }
  // 콘솔 개행 출력
  cout << endl;
  // 데이터 삭제
  data3.erase(data3.begin() + 1);
  // 콘솔 개행 출력
  cout << "data3 result (erase) " << endl;
  // iterator형식으로 포인터를 이용한다.
  // crbegin(), crend()를 사용하면 역순 const 타입이다.
  for (auto ptr = data3.crbegin(); ptr < data3.crend(); ptr++)
  {
    // 콘솔에 포인터 값을 출력한다.
    cout << *ptr << " ";
  }
  // 콘솔 개행 출력
  cout << endl;
  // 백터 초기화
  data3.clear();
  // 콘솔 출력... data3 여부
  cout << "data 3 empty ? " << (data3.empty() ? "true" : "false") << endl;

  return 0;
}

vector는 처음에 선언을 초기 값 설정으로 배열로 넣을 수 있습니다. 그리고 erase로 지우거나 pop_back()을 이용하면 마지막 데이터를 삭제할 수 있습니다.(참고로 vector에서 데이터를 삭제하는 것이지 메모리 해제를 뜻하는 것은 아닙니다.)

그외에 begin, end 함수를 이용하면 iterator 형식으로 사용할 수 있습니다.

Java, C#에서 List와 사용 방법이 비슷합니다.

함수명	설명
at	데이터 n번째 취득, indexer로 취득하는 것과 같습니다.
begin cbegin	iterator를 사용하기 위한 첫번째 pointer
end cend	iterator를 사용하기 위한 마지막 pointer
rbegin crbegin	reverse(역방향) iterator를 사용하기 위한 첫번째 pointer
rend crend	reverse(역방향) iterator를 사용하기 위한 마지막 pointer
empty	vector의 데이터가 비어있는지 확인합니다.
size	vector의 데이터의 크기를 반환합니다.
clear	vector의 데이터를 비웁니다.
insert, emplace	vector의 데이터를 원하는 위치에 추가합니다. (insert는 배열 형식으로, emplace는 데이터 한개)
erase	vector의 데이터를 삭제합니다.(메모리 해제를 뜻하는 건 아닙니다.)
swap	vector의 데이터를 서로 바꿉니다.
push_back	데이터를 vector 끝에 삽입합니다.
pop_back	vector의 마지막 데이터를 삭제합니다.

참조 - http://www.cplusplus.com/reference/vector/vector/

vector를 이용해서 Stack과 Queue 알고리즘를 구현해 보겠습니다.

#include <stdio.h>
#include <iostream>
// vector를 사용하기 위해서는 추가한다.
#include <vector>
using namespace std;
// Stack 알고리즘은 FILO(First input Last output)의 성질을 가지고 있다.
// 즉, 가장 먼저 입력된 데이터가 가장 마지막에 나오는 자료구조이다.
template <typename T>
class Stack
{
private:
  // vector를 사용
  vector<T> v;
public:
  // 값을 넣기
  void push(T val)
  {
    v.push_back(val);
  }
  // 값을 빼기 (FILO 구조)
  T pop()
  {
    // 가장 마지막에 넣은 데이터를 취득
    T ret = v.back();
    // 가장 마지막 데이터를 삭제
    v.pop_back();
    // 결과 반환
    return ret;
  }
  // 데이터가 비어 있는 지 확인하는 함수
  bool empty()
  {
    return v.empty();
  }
};
// Queue 알고리즘은 FIFO(First input First output)의 성질을 가지고 있다.
// 즉, 가장 먼저 입력된 데이터가 가장 먼저 나오는 자료구조이다.
template <typename T>
class Queue 
{
private:
  // vector를 사용
  vector<T> v;
public:
  // 값을 넣기
  void push(T val)
  {
    v.push_back(val);
  }
  // 값을 빼기 (FIFO 구조)
  T pop()
  {
    // 가장 처음에 넣은 데이터를 취득
    T ret = v.front();
    // 맨 처음 데이터를 삭제
    v.erase(v.begin());
    // 결과 반환
    return ret;
  }
  // 데이터가 비어 있는 지 확인하는 함수
  bool empty()
  {
    return v.empty();
  }
};
// 실행 함수
int main()
{
  // Stack 알고리즘 선언
  Stack<const char*> stack;
  // 순서대로 입력..
  stack.push("Hello world");
  stack.push("good");
  // 콘솔 출력
  cout << "Stack Result " << endl;
  // stack이 전부 빌때까지 출력
  while (!stack.empty())
  {
    // 콘솔 출력... 입력된 반대로 순서로 출력
    cout << stack.pop() << endl;
  }
  // 개행 출력
  cout << endl;
  // Queue 알고리즘 선언
  Queue<const char*> queue;
  // 순서대로 입력..
  queue.push("Hello world");
  queue.push("good");
  // 콘솔 출력
  cout << "Queue Result " << endl;
  // stack이 전부 빌때까지 출력
  while (!queue.empty())
  {
    // 콘솔 출력... 입력된 순서로 출력
    cout << queue.pop() << endl;
  }
  // 개행 출력
  cout << endl;

  return 0;
}

※참고로 C++에는 list라는 객체가 있습니다. vector와 list의 차이는 java에서 ArrayList와 LinkedList의 차이입니다. ArrayList와 LinkedList의 사용 목적이 분명히 다른 두 리스트 타입입니다만, 보통은 ArrayList가 검색에서 빠르기 때문에 자주 사용합니다.

그 말은 C++에서도 list라는 객체가 있지만, 보통 list형식으로 사용한다고 하면 vector를 더 자주 사용합니다.

여기까지 C++에서 사용되는 vector(리스트)의 사용법 (Stack, Queue 알고리즘 예제)에 대한 글이었습니다.

궁금한 점이나 잘못된 점이 있으면 댓글 부탁드립니다.