[기초] 자료구조 / 큐(queue)와 덱(deque), 문자열

 

큐(queue)

한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조

 

먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 합니다.

 

출처 : 위키피디아

 

- push : 큐에 자료를 넣는 연산

- pop : 큐에서 자료를 빼는 연산

- front : 큐의 가장 앞에 있는 자료를 보는 연산

- back : 큐의 가장 뒤에 있는 자료를 보는 연산

- empty : 큐가 비어있는지 아닌지를 알아보는 연산

- size : 큐에 저장되어있는 자료의 개수를 알아보는 연산

 

 

그림에서 빨간색 1번이 front로 가장 앞에 있는 자료이고 빨간색 3번이 back으로 가장 뒤에 있는 자료입니다.

 

 

 

큐도 스택과 같이  이미 구현된 라이브러리를 사용할 수있습니다.

 

C++의 경우 STL의 queue

JAVA의 경우 java.util.Queue

 

 

직접 구현할 경우 배열에 시작하는 변수와 끝 변수를 설정하여

push 하면 큐에서 끝 변수 인덱스에 값을 추가해주고 +1 해줍니다.

pop 하면 큐에서 시작하는 변수 인덱스에 값을 0으로 만들고  시작하는 변수에 +1 해줍니다.

size는 끝 변수 - 시작하는 변수이고 empty는 그 두 변수가 같은지 판단하면 됩니다.

 

 

---

 

덱(deque)

 

 

양쪽 끝에서만 자료를 넣고 양쪽 끝에서만 뺄 수 있는 자료구조

 

스택과 큐를 합친 형태로 double-ended queue 의 약자입니다.

 

출처 : https://propercoding.tistory.com/19

 

 

- push_front : 덱의 앞에 자료를 넣는 연산

- push_back : 덱의 뒤에 자료를 넣는 연산

- pop_front : 덱의 앞에서 자료를 빼는 연산

- pop_back : 덱의 뒤에서 자료를 빼는 연산

- front : 덱의 가장 앞에 있는 자료를 보는 연산

- back : 덱의 가장 뒤에 있는 자료를 보는 연산

 

 

---

 

문자열(String)

 

 

문자열은 연속된 문자들의 모임으로 아스키코드를 이용하여 저장합니다.

 

저장은 숫자로 되어 있는데 출력만 글자로 해주는 것으로 이해하면 됩니다.

 

큰 따옴표, 작은 따옴표 안에 문자가 있는 형태입니다.

 

 

 

백준 단어 길이 재기 문제입니다.

 

단어를 입력받고 길이를 재는 문제인데 strlen 이나 String의 length나  size를 이용하면 풀 수 있습니다.

 

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

2743번: 단어 길이 재기

 

위 함수를 사용할 수 없다면 다음 방법으로 길이를 잴 수 있습니다.

 

 

 

c언어 문자열의 마지막에는 NULL문자열이 들어갑니다.

 

그래서 문자열의 단어의 길이를 보면 문자열값이 NULL을 가질 때 까지의 길이를 구하면 됩니다.

 

#include<iostream>

using namespace std;

int main(){
    string s;
    int len = 0;
    cin >> s;
    for(int i = 0; s[i]; i++){
    	len += 1;
    }
    cout << len << endl;
  	return 0;
}

 

 

여기서 주의 할 점은 strlen 함수의 시간 복잡도는 O(N)이고

 

for문 안에서 strlen 함수를 사용하여 반복하여 매번 호출하기 때문에 시간 복잡도가 O(N^2)가 됩니다. 

 

// strlen 함수의 시간 복잡도는 O(N)이기 때문에, 다음과 같이 작성하면 O(N^2) 코드이다.

for (int i = 0; i < strlen(s); i++){
	//Do something
}


// 아래와 같이 작성하는 것이 올바르다. -> O(N)

int len = strlen(s);
for (int i = 0; i < len; i++){
	//Do something
}

 

---

C++에서 문자열을 정수로 또는 정수를 문자열으로 바꾸려면 아래 함수를 사용하면 됩니다.

 

#include<String>

 

 문자열 -> 정수 

 

- stoi : string -> int

- stol : string -> long

- stoll : string -> long long

- stof : string -> float

- stod : string -> double

- stold : string -> long double

- stoul : string -> unsigned long

- stoull : string -> unsigned long lomg

 

 

정수 -> 문자열

 

C++에서 정수를 문자열로 바꾸는 함수

각각의 자료형 형태로 정의되어 있어서 실수도 문자열로 바꿀 수 있습니다.

 

 

to_string()

 

 

---

 

 

 

큐를 이용한 백준 조세퍼스 문제입니다.

 

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성합니다.

 

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

1158번: 요세푸스 문제

 

 

queue 자료구조를 사용합니다.

 

 

 

- 풀이내용 -

 

1~N번까지의 사람이 원을 이루며 앉아있고, 계속해서 K번째 사람을 지워나가면 됩니다.

 

문제에서 출력해야하는 값은 지워지는 사람의 순서입니다.

 

 

1부터 n까지 있는 큐를 만들어 주고, k-1번째 까지 사람을 pop()으로 큐에서 뺀 뒤,

다시 뒤에 push()하면 k번째 사람이 큐의 맨 앞 front()에 오게됩니다.

 

이 front()를 출력한 뒤 pop()하고 위에 두줄을 반복하면 됩니다.