가장 기본적인 자료구조인 Queue를 linked list를 이용하여 구현한코드와
배열을 이용해서 구현한 코드를 보여드리고
과연 어떤게 가장빠른지 메모리를 효율적으로 사용할지 비교해보려고합니다.
우선 코드가 깔끔하니 이해하시기 편할겁니다.
사용법 또한 STL과 똑같이 만들었습니다. 사용하기도 편하실겁니다.
linked list를 이용한 코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
//By 콩순이 냉장고
#include <iostream> #include <cstdlib>
#include <string>
using namespace std;
template <typename T>
class Node{
public:
T data;
Node *next = NULL; //생성할때 미리 NULL을 가리키는것이 코드를 줄일수있음
};
template <typename T>
class Queue{
private:
Node<T> *head = NULL, *tail = NULL;
int cnt = 0;
public:
void push(T n){
cnt++;
if (head == NULL)//큐에 처음 데이터를 집어넣을때
{
head = new Node<T>;
head->data = n;
tail = head;
return;
}
//사이즈가 2이상일때
tail->next = new Node<T>;
tail = tail->next;
tail->data = n;
}
T pop(){
if (head == NULL)//아무것도 없을때 에러
{
printf("under flow\n");
exit(-1);//에러코드
return -1;
}
int t = head->data;
Node<T> * next = head->next;
delete head;//헤드는 삭제해줘야함
head =next; //이게 핵심 설령 모든것을 pop시켜도 마지막의 가리키고 있는 next는 null값이니 아무것도 없을때도 head는 결국null을 가리킨다는것을 알아야함
cnt--;
return t;
}
int empty(){
if (head == NULL)//head가 가리키는것이 없다면 비어있음
return 1;
return 0;
}
T front()
{
return head->data;
}
T back()
{
return tail->data;
}
int size()
{
return cnt;
}
};
|
cs |
배열을 이용한 코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
// By 콩순이 냉장고
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
#define MAXSIZE 2000000
template <typename T>
class Queue{
private:
int head = -1;
int tail = -1;
int cnt = 0;
T data[MAXSIZE];
public:
void push(T n){
if (cnt >= MAXSIZE)
{
cout << "over flow\n";
exit(-1);
return;
}
tail = (tail + 1) % MAXSIZE;//메모리를 다시사용할수있게 배열을 원형큐 라고생각하면됨
if (cnt == 0)
{
cnt++;
data[tail] = n;
head = tail;//사이즈가 1이될때 head와 tail은 같은곳을 가리켜야함
return;
}
data[tail] = n;
cnt++;
}
T pop(){
if (cnt == 0)//아무것도 없을때 에러
{
printf("under flow\n");
exit(-1);//에러코드
return -1;
}
head = (head + 1) % MAXSIZE;
T t = data[head];
cnt--;
return t;
}
int empty(){
if (cnt == 0)
return 1;
return 0;
}
T front()
{
return data[head];
}
T back()
{
return data[tail];
}
int size()
{
return cnt;
}
};
|
cs |
배열을 이용하면 MAXSIZE는 원하는 만큼 지정해줄수있지만 오버플로우를 걱정하면서 사용하기때문에 불편하지요
근데 linked list는 그럴 생각할 필요가 없습니다. 정확히 사용할 만큼 동적으로 메모리를 할당해주기때문에 편리하지요
그런데 어떤게 빠를지 한번 궁금하지 않나요? 그래서 비교해봤습니다.
문제 URL : https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
단순히 큐를 사용하는 문제이고 해답은 올리지 않을게요 단순히 큐를 사용하는 문제니까
한번 3가지를 비교해봤습니다. library를 이용한 코드랑 제가만든 코드가 어떤게 더빠를까? 물론 제코드가 느리게 나올거라 생각했는데 배열로 이용한코드가 더 빠르게 나와서 대만족이었습니다. ㅎㅎㅎ
linked list를 이용한 코드는 조금 더느리고 메모리도 왜저렇게 많이 사용하는지?
느린건 이해할수있는게 하나하나 데이터를 생성할때마다 내부적으로 메모리를 동적으로 할당하게되니 느린건 당연하다고 보지만 메모리가 너무 크게 차이가나서 좀 난해했습니다.
소멸자 까지 사용해서 큐에 남아있는 모든것을 다지우는 코드도 작성해봤었는데 시간은 더느려지고 메모리사용량은 그대로라서 소멸자는 그냥 안넣었습니다.
그리고 STL보다 빠르지만 메모리는 아마 최적하게 사용된 코드로 작성되어있을거라 생각되는데 과연 어떻게 작성했을지 궁금하기도 하네요
제 코드는 얼마든지 이용해도 괜찮습니다.
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 hash (0) | 2022.04.22 |
|---|---|
| [CS 면접] 자료구조 정렬의 종류, 정렬의 차이 (0) | 2022.03.24 |
| [CS 자료구조] 그래프와 트리의 차이 (0) | 2022.03.07 |
| [자료구조] CS 공부 스택 vs 큐 (스택으로 큐구현 , 큐로 스택구현) (0) | 2022.02.24 |
| [자료구조] List → ArrayList vs LinkedList (0) | 2022.01.20 |
