덱이란? 일반적인 큐, 원형큐에서는 rear에서 삽입, front에서 삭제가 가능했다. Deque은 double edged queue의 줄임말로, 큐의 front, rear에서 삽입, 삭제가 모두 가능한 큐를 말한다. 큐, 스택과 마찬가지로 중간에서 삽입과 삭제는 일어나지 않는다. 덱을 구현하기 위해 필요한 것 1. 덱 생성 2. 덱 초기화 3. 공백상태인지 포화상태인지 검사 4. add_front(앞에 추가) / add_rear(뒤에 추가) 5. delete_front(앞에서 삭제) / delete_rear(뒤에서 삭제) 6. get_front(뒤에서 요소반환) / get_rear(뒤에서 요소반환) 7. 덱 출력 1. 덱 생성 #include #define MAX_DEQUE 5 typedef int e..
앞에서는 선형큐를 구현해보았다. 선형큐는 이해하기 쉽고 간편하지만, 문제점이 있다. front와 rear가 계속 증가만 하기 때문에 한정적인 배열에서 결국 끝에 도달하게 되고, 큐의 앞부분이 비어있더라도 사용하지 못한다. 따라서 요소들을 왼쪽으로 매번 이동시켜야한다. (코딩 복잡도 상승, 속도 느림) 이런 문제점들을 해결하기 위해서 나온 방법이 원형큐 이다. 원형큐의 구조와 간단한 원리 원리는 이렇다. 만약 MAX_QUEUE_SIZE가 6이라고 가정해보자. front과 rear의 값이 계속 증가할 때, MAX_QUEUE_SIZE - 1에 도달하면 다음으로 증가되는 값을 0이 되도록 하면된다. 실제로 원형으로 생성되는 것이 아니라, 개념상 원형으로 구현이 된다고 생각하면 된다. 원형큐의 데이터 삽입 과정 ..
큐(Queue) 스택은 나중에 들어온 데이터가 먼저 나가는 후입선출(last in, first out)구조였다. 큐는 먼저들어온 데이터가 먼저 나가는 선입선출(first in, first out)구조다. 뒤(rear)에서 데이터가 들어오고, 앞(front)에서 데이터가 하나씩 삭제된다. 큐를 구현해보자 일단 큐를 구현하기전에 필요한 것을 나열해보면, 1. 큐 구조체 정의, 생성 2. full인지 empty인지 확인하는 함수 3. 데이터를 삽입하는 함수 4. 데이터를 삭제하면서 반환하는 함수 5. 큐를 출력하는 함수 1. 큐 구조체 정의 생성 #include #define MAX_QUEUE 5 typedef int element; typedef struct { int front; int rear; elem..
앞에서는 스택의 크기를 고정시켜놓고 컴파일을 하는 1차원 배열 스택을 구현했다. 이번에는 필요에따라 메모리 공간을 할당하는 동적메모리를 활용한 스택을 구현해보자. #include #include typedef int element; typedef struct { int top; int capacity; element *data; } StackType; 일반적인 스택구현과 다른점은 element *data이다. 동적메모리를 할당할 malloc함수는 리턴값이 포인터이기 때문에, 그 포인터를 받을 포인터변수 data를 선언한다. 1.스택초기화, 동적메모리 free void init_stack(StackType *s) { s->top = -1; s->capacity = 1; s->data = (element *..
스택 일단 stack의 구조는 이렇다. 데이터를 넣을땐 위에서 넣고, 데이터를 빼낼때 또한 위에서 뺀다. 아래에서 데이터를 넣고, 뺄 수 없다. 항상 위에서만! 후입선출(last in, first out)을 구조를 가진다. 스택의 예시 1)함수의 호출 2)웹 브라우저에서 뒤로가기 등등.. 예를들어, 재귀함수를 호출한다고 가정해보자. 함수는 실행이 끝나면 자신을 호출한 함수로 되돌아가야한다. 만약 factorial(3)이라는 함수를 호출한다면 factorial(2)가 실행되고, factorial(2)함수가 끝나면 factorial(3)함수로 돌아간다는 뜻이다. 스택은 복귀할 주소를 기억하는데 사용된다. 스택에서 입출력이 이루어 지는 가장 윗부분을 stack top이라고 한다. 가장 밑 스택은 bottom ..
순환 순환이란 어떤 알고리듬이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 방법이다. 순환적인 문제를 해결하는데 적합하고, '반복'을 사용하는 것 보다 간결하고 이해가 쉬울 때도 있다. 하지만, 함수를 호출하고 기억장소를 할당해야 하기때문에 반복에 비해서 비효율적이고 속도가 느릴 수 있다. 순환의 예 순환은 순환적인 문제를 해결하는데 적합하다고 했다. 예를 들어, 팩토리얼(factorial)계산은 순환적이다. 팩토리얼의 정의를 살펴보면, n!을 계산하기 위해 n에 (n-1)!을 곱한다. 즉, n!을 정의하기 위해서 다시 (n-1)!을 사용한다는 것이다. 이러한 것을 '순환적'이다 라고 한다. 이것을 재귀함수를 이용해서 풀어보자. int factorial(int n) { if(n
