- 데이터를 집합으로 구성하고 원소들을 추가/삭제하는 데이터 관리 방법
- 자료구조가 바뀌면 알고리즘이 바뀌고 그 반대도 마찬가지
- 가장 기초적인 자료구조 (stack and queue)
- stack: 쌓아올리는 개념, 새로운 데이터는 위에 쌓임
- queue: 줄 서는 개념 (FIFO)
stack 자료 구조
1: PUSH ,2: POP
1
PUSH VALUE? 100
100
1: PUSH ,2: POP
1
PUSH VALUE? 25
25
100
1: PUSH ,2: POP
2
25 POP!
100
queue 자료 구조
1: PUSH ,2: POP
1
PUSH VALUE? 100
100
1: PUSH ,2: POP
1
PUSH VALUE? 25
100 25
1: PUSH ,2: POP
2
100 POP!
25
stack & queue 코딩해보기
#include <iostream>
const int size{ 10 };
struct Stacks
{
int container[size]{};
int top=-1;
//마지막 저장 지점 : 접시를 쌓는 것과 같은 개념임으로
//0보다 밑에 있다는 것은 stack이 비었다는 뜻
//그걸 위해서 -1로 씀
};
enum Command
{
push = 1,
pop = 2,
};
void PrintInfo();
void ProcessUserInput(Stacks& stack);
//데이터가 안에서 바껴야 함으로 참조형으로
void Push(Stacks& stack, int value);
void Pop(Stacks& stack);
void PrintStack(Stacks& stack);
int main()
{
Stacks myStack;
while (true)//무한 반복
{
//명령어 출력
PrintInfo();
//입력 받고
ProcessUserInput(myStack);
//push pop을 포함함
//입력에 따라 2가지 push or pop
//PushStack();
//PopStack();
//스택에 내용 출력
PrintStack(myStack);
}
}
//구조체로 배열과 관리를 위한 정보를 묶어서 구조체로 만들어 보기
void PrintInfo()
{
std::cout << "1:push,2:pop" << std::endl;
std::cout << "-----------------" << std::endl;
}
void ProcessUserInput(Stacks& stack)
{
int command;//사용자에게 숫자 입력
std::cin >> command;
switch (command)
{
case push:
{
int value;
std::cout << " push value?";
std::cin >> value;
//푸쉬 일때만 한번 더 입력받아야함 : 값을 입력하기 위해서
//
//그냥 int value는 complie안됨 : 변수는 중괄호 블록으로 관리됨 케이스 레이블만에 변수를 만들고 싶음
//중괄호를 한 번 더 쓰기
Push(stack, value);
break;
}
case pop:
Pop(stack);
break;
default:
std::cout << "invalid command" << std::endl;
break;
}
}
void Push(Stacks& stack, int value)
{
//배열이 넘치는 것을 막아줌
if (stack.top>=size-1)
{
std::cout << "stack is full" << std::endl;
return;
}
//증가한 다음 + 값을 넣어줌
stack.container[++stack.top] = value;
}
void Pop(Stacks& stack)
{
if (stack.top<0) {
std::cout << "stack is empty" << std::endl;
return;
}
//탑이 내려오면됨
std::cout << stack.container[stack.top--] << "is pop" << std::endl;
//출력한다음 빼기 (후위연산자)
//인덱스 사용 계산식이 있으므로 안전한지 체크
}
void PrintStack(Stacks& stack)
{
if (stack.top < 0) {
std::cout << "stack is empty!" << std::endl;
return;
}
for (int i = stack.top; i >= 0; --i)
{
std::cout << stack.container[i] << std::endl;
}
std::cout << "----stack----" << std::endl;
}
queue구조
--
+ 환형 큐
0 5 10 >> 0 %5 (나머지)
1 6 11 >> 1 %5 (나머지)
2 7 12 >> 2 %5 (나머지)
```cpp
#include <iostream>
const int size = 10;
struct Queue
{
int container[size]{};
int head = 0;//앞에서나가고
int tail = 0;//뒤에서 들어옴
//왜 0이냐? head==tail is empty상태
//stack은 -1이 빈 상태
};
enum CommandQueue {
enQueue = 1,
deQueue = 2
};
void PrintInfoQueue();
void ProcessInputQueue(Queue& queue);
void PrintQueue(Queue& queue);
void PushQueue(Queue& queue, int value);
void PopQueue(Queue& queue);
int main()
//메인은 한 프로젝트당 한 개여야 함
{
Queue myQueue;
while (true)
{
PrintInfoQueue();
ProcessInputQueue(myQueue);
PrintQueue(myQueue);
}
}
void PrintInfoQueue()
{
std::cout << "1:enQueue,2:deQueue" << std::endl;
std::cout << "----------------------" << std::endl;
}
void ProcessInputQueue(Queue& queue)
{
int command;
std::cin >> command;
switch (command)
{
case enQueue:
{
int value;
std::cout << " value?" << std::endl;
std::cin >> value;
PushQueue(queue, value);
break;
}
case deQueue:
PopQueue(queue);
break;
default:
std::cout << "invalid command" << std::endl;
break;
}
}
//front==end같을 때
//i= front to end
void PrintQueue(Queue& queue)
{
std::cout << "----queue----" << std::endl;
int i = queue.head;
if (queue.head == queue.tail) {
std::cout << "empty" << std::endl;
return;
//head와 테일이 같으면 비어있는것 위치가 어디이든 상관없음
}
while (i!=queue.tail)
{
i++;
i = i % size;
//i=(i+1)%size;
std::cout << queue.container[i] << "\t";
}
std::cout << std::endl;
std::cout << "----" << std::endl;
}
//넣기 :꼬리에 붙음
void PushQueue(Queue& queue, int value)
{
//찬 상황
if ((queue.head-1+size)%size==queue.tail) {
//나머지 -1 ==4가 아니기 때문이다
//음수 처리 대비
//(queue.head+1)%size==queue.tail
std::cout << "Queue is full" << std::endl;
return;
}
queue.tail = (queue.tail + 1) % size;
queue.container[queue.tail] = value;
//집어넣을때 tail을 증가시킨 다음에 삽입함 그래서
//원소 하나가 추가되면 tail이 그다음에 와있음
//head는 첫번째 원소 하나에 있다는 것
}
//꺼내기 : 머리부터 시작
void PopQueue(Queue& queue)
{
if (queue.head == queue.tail) {
return;
}
queue.head = (queue.head + 1) % size;
//실제로 첫번째 원소는 head옆에 있음
//이미 빠져나간것
//head를 증가시키면 head == tail이 됨
//그래서 이미 빠져나간것과 같음
//empty의 조건을 편하게 코딩하기 위해서 이런 방식으로 만든 것
std::cout << queue.container[queue.head] << "is queue" << std::endl;
}이렇게 하면 head==tail이 empty 인 동시에 full이기도함
queue.tail +1 이기 때문
그래서 마지막 1개는 사용 불가능함
어떻게 하면 가득차도록 만들 수 있을지 고민해보기?
동적 자료구조
- 동적 메모리 할당 -> 동적 자료구조
(원하는 만큼 원소를 추가하거나 제거할 수 있는 기능) - 아직 정하지 않은 데이터량을 조절할 수 있어야함
Single Linked List(단일 연결 목록)
- 단방향으로 연결되어 있는 자료 구조
- 메모리 용량을 줄일 수 있음
- data + overhead(기능 이외에 추가적으로 발생하는 비용 >> 서버 비용)
- stack 구조라면 삭제는 top부분에서만
- queue 구조라면 삭제는 tail에서 추가는 head에서 일어나게 됨
- 단점 : 앞으로 못감
Double Linked List(이중 연결 목록)
- 양방향으로 연결되어 있는 자료 구조
traverse algorithm
- 처음부터 끝까지 빠짐없이
- 대부분의 자료구조는 이 구조가 많음
visual studio
solution과 project구조
- solution은 여러개의 프로젝트를 관리하는 환경
- project는 앱 하나
- lol이라는 솔루션에서 outgame project , ingame project, crash report project등으로 나뉨
- 중복되는 것이나 선언 상수 등은 헤더파일로 (헤더파일은 컴파일이 안됨, 프로젝트는 분리되어있더라도 헤더는 하나로 만들 수 있음)
- 헤더용 폴더를 만들어서 관리하는 방법도 있음(#include"../Common/Declaration.h" //..)
- 헤더 파일은 같은 프로젝트에 없어도 사용 가능함 (헤더 파일은 컴파일 되지 않기 때문)
- 소스 파일은 같은 프로젝트에 있어야지 쓸 수 있음
공부 기록용