2024. 2. 26. 08:28ㆍProgramming Language/C++
아래 링크 클릭 시 해당 본문으로 이동
STL (Standard Template Library, 표준 템플릿 라이브러리)
• Microsoft의 C++ 표준 라이브러리 구현이다.
STL에서 제공하는 헤더 파일을 C에서는 `.h` 확장자가 붙지만 C++에서는 확장자 없이 이름만으로 정의가 가능하다.
ex) `#include <iostream>`, `#include <vector>`, `#include <string>` 등
• 크게 4개의 라이브러리로 분류된다. ➜ 컨테이너, 알고리즘, 반복자, 함수 객체
| 구성 | 설명 | 종류 | 간단히 말하면.. |
| 컨테이너 (Container) |
• 데이터를 저장하고 정리한다. | vector, list, forwad_list, deque, array, map, multimap, multiset, set, stack, queue, priority_queue, unordered_map, unordered_set, unordered_multimap, unordered_multiset |
데이터를 저장하기 위한 상자 |
| 알고리즘 (Algorithm) |
• 데이터 정렬 및 검색 | find, binary_search, sort, partial_sort, reverse, replace, rotate, accumulate, inner_product, set_union, set_intersection |
데이터를 효율적으로 처리하는 도구 |
| 반복자 (Iterator) |
• 컨테이너의 데이터를 통해 이동한다. | begin, end, rbegin, rend, advance, distance |
데이터를 탐색하기 위한 포인터 |
| 함수 객체 (Functor) |
• 함수처럼 호출할 수 있는 클래스 객체 • 클래스 객체를 함수 포인터로 넘길 수 있다. |
plus<T>, minus<T> 사용자 정의 정렬, 필터링, 비교 규칙 |
추가 규칙을 정의하기 위한 특수 도구 |
자료구조(data structure)
• 어떤 데이터들을 관리함에 있어서 어떻게 효율적으로 관리할 것인가에 대한 이론적인 학문이다.
이 글에서는 자료구조 중에서도 스택과 큐에 대해 정리했다.
스택과 큐는 입출력에 제한을 갖는 자료구조이다.
스택 (Stack)
• 스택은 top으로 들어온 데이터가 아래에서 위로 쌓이는 형태의 자료구조이다.
ex) 뷔페에서 접시가 차곡차곡 쌓이는 경우, 연탄아궁이에서 연탄을 넣거나 빼는 경우
• top : 현재 스택의 가장 위에 있는 데이터 위치로, 유일하게 액세스(삽입/삭제)가 허용된 지점이다.
즉, 삽입과 삭제가 한 곳(top)에서만 이루어진다.
• top의 위치는 항상 가장 위에 있는 데이터(가장 마지막에 삽입된 데이터)이다.
스택에서 데이터를 삭제할 때도 top을 통해서만 할 수 있기 때문에 가장 위에 있는 데이터가 삭제된다.
가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 구조적 특징을 가지고 있으며, 이런 스택의 동작 구조를 후입선출이라고 한다.
• 후입선출(LIFO : Last In First Out) 구조 : 나중에 들어온 것이 먼저 나간다.
ex) 웹브라우저에서 뒤로 가기 누를 때
• push : top을 통한 삽입 연산
• pop : top을 통한 삭제 연산
스택 헤더 파일
• STL의 스택을 사용하려면 스택 헤더 파일을 불러와야 한다.
#include <stack> // 스택 라이브러리스택 기본 형식
std::stack<자료형> 변수명;`using namespace std;`를 선언하면 좀 더 간단하게 사용할 수 있다.
using namespace std;
stack<int> st;스택 선언
// stack<자료형> 변수명;
// 해당 자료형 변수들을 담는 스택을 선언한다.
stack<int> s;
stack<int> s1;
stack<int> s2;스택 기본 함수
1) `empty()` : 스택이 비어있는지 확인하는 함수
• 비어있으면 `true`, 비어있지 않으면 `false` 반환
// 스택이름.empty()
s.empty()
2) `push()` : 스택 맨 앞에 element(원소, 요소) 추가
• element(원소, 요소) : 각 인덱스에 존재하는 값
// 스택이름.push()
s.push()
3) `pop()`: 스택 맨 앞의 원소 삭제
// 스택이름.pop()
s.pop()
4) `size()` : 스택 원소의 개수 반환 (스택 사이즈 반환)
// 스택이름.size()
s.size()
5) `top()` : top(제일 위에 있는 원소) 반환
// 스택이름.top()
s.top()
6) `swap()` : 두 스택의 내용 변경
swap 예시
◦ 라인 스왑(swap) : 리그 오브 레전드(League of Legends)라는 게임에서 서로의 라인(포지션)을 바꾸는 것
// swap(스택1 이름, 스택2 이름)
swap(s1, s2)
▷ 예시 1
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s; // s는 int형 변수들을 담은 스택의 이름이다.
// push
for (int i = 0; i <= 3; ++i)
{
s.push(i); // 스택에 0부터 3까지 넣는다.
}
// pop
for (int i = 0; i <= 3; ++i)
{
cout << s.top() << "\n";
s.pop();
}
return 0;
}▽ 출력 결과
3
2
1
0
▷ 예시 2
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> s1;
stack<int> s2;
// 스택 원소 추가
s1.push(0);
s1.push(1);
s1.push(2);
s2.push(100);
s2.push(101);
s2.push(102);
// s1과 s2 스택 내용 변경
swap(s1, s2);
// 스택 s1이 비어있지 않다면 => true
// 스택 s1이 빈 상태가 되면 while문 종료
while (!s1.empty()) {
// top 출력
cout << st.top() << endl;
// 스택 원소 삭제
st.pop();
}
return 0;
}▽ 출력 결과
102
101
100swap으로 인해 `s1`의 내용은 `s2`로 변경되었다.
스택을 이용한 수식 표기법
• 수식 표기법 종류 : 전위 표기법, 중위 표기법, 후위 표기법
1) 전위 표기법 (Prefix Notation) : 연산자를 피연산자 앞에 표기하는 방법 (ex. +AB)
2) 중위 표기법 (InfixNotation) : 연산자를 피연산자의 가운데에 표기하는 방법 (ex. A + B)
3) 후위 표기법 (Postfix Notation) : 연산자를 피연산자 뒤에 표기하는 방법 (ex. AB+)
• 컴퓨터 내부에서 중위 표기법을 후위 표기법으로 바꾸는 법
① 왼쪽 괄호는 무시하고 다음 문자를 읽는다.
② 피연산자는 출력한다.
③ 연산자는 스택에 삽입한다.
④ 오른쪽 괄호를 만나면 스택을 pop하여 출력한다.
⑤ 수식이 끝나면 스택이 공백이 될 때까지 pop하여 출력한다.
• 스택을 사용하여 후위 표기법 수식을 계산하는 법
① 피연산자는 스택에 push한다.
② 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push한다.
③ 수식이 끝나면 마지막으로 스택을 pop하여 출력한다.
▷ 보통 우리가 사용하는 중위 표기법 수식 `A * B + C / D`을 전위, 후위 표기법으로 변환
1) 중위 표기법 → 전위 표기법
① 각 연산자의 우선순위에 따라 괄호로 묶어서 표현한다.
`((A * B) - (C / D))`
② 각 연산자를 해당 연산자에 대응하는 왼쪽 괄호 앞으로 이동시킨다.
`- ( * (A B) / (C D))`
③ 괄호를 제거한다.
`- * AB / C D`
2) 중위 표기법 → 후위 표기법
① 각 연산자의 우선순위에 따라 괄호로 묶어서 표현한다.
`((A * B) - (C / D))`
② 각 연산자를 해당 연산자에 대응하는 오른쪽 괄호 뒤로 이동시킨다.
`((A B) * (C D) / ) -`
③ 괄호를 제거한다.
`A B * C D/-`
▷ 스택을 이용하여 후위 표기법으로 변환하는 과정
큐 (Queue)
• 한쪽 끝은 머리(head, front), 다른 쪽 끝은 꼬리(tail, rear)이다.
• 머리(head, front) : 삭제 연산만 수행하며, 가장 먼저 삽입된 첫 번째 원소
• 꼬리(tail, rear) : 삽입 연산만 수행하며, 가장 마지막에 삽입된 원소
• 선입선출 (FIFO, First In First Out) : 먼저 삽입된 원소가 먼저 삭제된다.
ex) 놀이공원에 줄 서는 경우, 꼬리잡기 놀이
큐 헤더 파일
• STL의 큐를 사용하려면 큐 헤더 파일을 불러와야 한다.
#include <queue> // 큐 라이브러리큐 기본 형식
std::queue<자료형> 변수명;큐 선언
// queue<자료형> 이름;
queue<int> q;
queue<int> q1;
queue<int> q2;큐 기본 함수
1) `empty()` : 스택이 비어있는지 확인하는 함수
• 비어있으면 `true`, 비어있지 않으면 `false` 반환
// 큐이름.empty()
q.empty()
2) `push()` : 큐 맨 앞에 원소 추가
// 큐이름.push()
q.push()
3) `pop()` : 큐 맨 뒤 원소 삭제
// 큐이름.pop()
q.pop()
4) `size()` : 큐 원소의 개수 반환 (스택 사이즈 반환)
// 큐이름.size()
q.size()
5) `front()` : 큐의 맨 앞(제일 첫 번째) 원소에 대한 참조 반환
// 큐이름.front()
q.front()
6) `back()` : 큐의 맨 뒤 원소(가장 최근에 추가된 원소)에 대한 참조 반환
// 큐이름.back()
q.back()
7) `swap()` : 두 큐의 내용 변경
// swap(큐1 이름, 큐2 이름)
swap(q1, q2)
▷ 예시 1
#include <iostream>
#include <queue>
using namespace std;
int main() {
// queue<자료형> 변수명
// 해당 자료형 변수들을 담는 스택을 선언한다.
queue<int> q; // int형 변수들을 담는 큐 선언
// q는 int형 변수들을 담은 큐의 이름이다.
// push
for (int i = 0; i <= 3; ++i)
{
q.push(i); // 큐에 0부터 3까지 넣는다.
}
// pop
for (int i = 0; i <= 3; ++i)
{
cout << q.front() << "\n";
q.pop();
}
return 0;
}▽ 출력 결과
0
1
2
3
▷ 예시 2
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> q1;
queue<int> q2;
// 큐 원소 추가
q1.push(0);
q1.push(1);
q1.push(2);
q2.push(100);
q2.push(200);
q2.push(300);
// q1과 q2 큐 내용 변경
swap(q1, q2);
// 큐 q1이 비어있지 않다면 = true
// 큐 q1이 빈 상태가 되면 while문 종료
while (!q1.empty())
{
// front 출력 및 큐 원소 삭제
cout << q1.front() << endl; q1.pop();
}
return 0;
}▽ 출력 결과
100
200
300원형 큐 (Circular Queue)
더 이상 원소를 삽입할 수 없는 포화 상태를 해결하기 위해 원형 큐를 사용한다.
• 1차원 배열을 사용한다.
• 논리적으로 배열의 처음과 끝이 연결되어 있는 원형 구조로 가정하고 사용한다.
• 초기 공백 상태일 때 front와 rear의 값은 0이고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 항상 자리 하나를 비워 둔다.
공백 상태일 때 front와 rear의 위치는 같다.
• rear가 다음으로 이동하면서 원소를 삽입하고, front는 rear가 이동한 방향으로 따라가면서 원소를 삭제한다.
▷ 크기가 5인 원형 큐 연산
//#include <queue>
// 표준 queue를 사용하지 않는 이유
// 1. 순환을 제공하지 않는다.
// 2. 큐가 초기화될 때 원형 큐가 보유할 수 있는 최대 원소 수가 고정되어 있어서 동적으로 늘리거나 줄일 수 없다.
#include <iostream>
using namespace std;
class myCircularQueue {
private:
int arr[5]; // 크기가 5로 고정된 배열
int front = 0;
int rear = 0;
const int csize = 5;
public:
myCircularQueue() {
front = -1;
rear = -1;
}
// 큐가 비었는지 확인
bool isEmpty() {
return front == -1;
}
// 큐가 포화 상태인지(꽉 찼는지) 확인
bool isFull() {
return (rear + 1) % csize == front;
}
// push 연산
void push(int value) {
if (isFull()) {
cout << "큐가 꽉 찼음." << endl;
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % csize;
}
arr[rear] = value;
cout << value << endl;
}
// pop 연산
int pop() {
if (isEmpty()) {
cout << "큐가 비어있음." << endl;
return -1;
}
int value = arr[front];
if (front == rear) {
// 큐가 이제 비어 있음.
front = rear = -1;
} else {
front = (front + 1) % csize;
}
cout << value << endl;
return value;
}
// 큐의 원소 출력
void display() {
if (isEmpty()) {
cout << "큐가 비어있음." << endl;
return;
}
cout << "큐 원소 : ";
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear) break;
i = (i + 1) % csize;
}
cout << endl;
}
};
int main() {
myCircularQueue cq;
cout << "1. 큐에 원소 추가" << endl;
cq.push(10);
cq.push(20);
cq.push(30);
cq.push(40);
cq.push(50); // 큐가 꽉 참.
cq.push(60); // 큐가 꽉 찬 상태에서 추가
cq.display();
cout << "2. 원소 제거" << endl;
cq.pop();
cq.pop();
cq.display();
cout << "3. 큐에 원소 추가" << endl;
cq.push(60);
cq.push(70); // 큐가 다시 꽉 참.
cq.display();
return 0;
}▽ 출력 결과
1. 큐에 원소 추가
10 추가
20 추가
30 추가
40 추가
50 추가
큐가 꽉 찼음.
큐 : 10 20 30 40 50
2. 원소 제거
10 제거
20 제거
큐 : 30 40 50
3. 큐에 원소 추가
60 추가
70 추가
큐 : 30 40 50 60 70'Programming Language > C++' 카테고리의 다른 글
| [C++] 함수[main()], return, void (0) | 2024.03.03 |
|---|---|
| [C++] 메모리 영역, 변수 (0) | 2024.03.02 |
| [C++] 조건문(Conditional Statements), 삼항 연산자 (0) | 2024.02.29 |
| [C++] 연산자(Operators), 전처리기[#define], 연산자 우선순위 (0) | 2024.02.29 |
| [C++] 자료형(Data Type) - 정수형, 실수형 (0) | 2024.02.26 |