[C] Queue 배열로 구현 Queue는 스택과 반대로 먼저 들어온 데이터가 먼저나가는 FIFO(First In First Out) 구조이다. 큐를 배열로 구현할 때는, Overflow를 주의해야 한다.큐는 put과 get이 다른 통로로 구성되어 있기 때문에 배열에서 자료가 들어오는(put) rear 와 자료가 나가는(get) front의 포인터를 유지한다.하지만 put()과 get()이 발생하면서 front 와 rear 포인터는 계속적으로 증가하고 제한된 크기의 배열을 넘어가게 된다. 이러한 문제를 막기위해 배열의 마지막+1 은 0 으로 전환해주는 원형 큐를 사용하기도 한다.원형 큐를 사용할 때 주의할 점은, rear의 포인터는 마지막 자료가 아닌 put() 수행시 들어올 자료의 공간을 가리킨다. 이..

[C] 사칙연산 계산 (후위표기법) 우리는 흔히 연산을 표현할 때 중위 표기법을 사용한다.중위 표기법을 사용하여 우선순위를 판단하여 연산 순서를 정한다.하지만, 컴퓨터는 순차적으로 처리하기 때문에 중위 표기법으로는 정확한 순서로 연산에 어려움이 있다. 따라서, 컴퓨터가 연산할 때는 후위표기법을 사용한다.후위표기법으로 변환하고, 후위표기법을 연산하는데 스택을 사용한다. (1) 중위표기법 -> 후위표기법 1. '(' 를 만나면 스택에 푸시한다.2. ')' 를 만나면 스택에서 '('가 나올 때까지 팝하여 출력하고 '(' 는 팝하여 버린다.3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 푸시한다.4. 피연산자는 그냥 출력한다.5. 모든 입력이 끝나면 ..

[C] 후위표기법 1 Stack_LinkedList 링크드 리스트의 스택을 활용하여 중위표기법을 후위표기법으로 변경해보자 1. '(' 문자는 무시하고 넘어간다2. 피연산자는 그대로 출력한다.3. 연산자는 스택에 푸시한다.4. ')'를 만나면 스택에서 팝하여 출력한다. 아래 알고리즘의 단점은 연산자 우선 순위가 고려되지 않아 중위표기법에 괄호를 씌워야 한다. void postfix1(char *dst, char *src){ char c; init_stack(); while (*src){ if (*src == ')'){ *dst++ = pop(); *dst++ = ' '; src++; } else if(*src=='+' || *src=='-' || *src=='*' || *src=='/'){ push(*sr..

[C] 스택(Stack) LinkedList 스택은 리스트로 표현할 수도 있다.배열에서는 크기가 정해져 있기 때문에 크기 이상의 데이터가 push 되면 스택오버플로우가 발생하지만, 리스트를 사용할 경우 동적으로 할당할 수 있기 때문에 메모리가 고갈될 때까지 push를 할 수 있다. #include #include typedef struct _node{ int key; struct _node *next; } node; node *head, *tail; void init_stack(void){ head = (node*)malloc(sizeof(node)); tail = (node*)malloc(sizeof(node)); head->next = tail; tail->next = tail; } int push(..

[C] 스택(Stack) 배열형 스택은 LIFO(Last In First Out) 구조이다.스택은 배열로 나타낼 수 있으며, 동적 구현을 위해서 Linked List를 사용할 수도 있다. 배열로 구현할 경우, 제한된 배열 크기 안에서 스택을 사용할 수 있으며 Stack이 꽉찬 상태에서 push가 발생하면, Stack Overflow 처리를 그리고 스택이 비어있을 때 pop이 발생하면 Stack underflow 처리를 해줘야 한다. 스택에서는 현재 최상단의 위치를 가리키는 top 을 유지해야 한다. #include #define MAX 10 int stack[MAX]; // 스택의 긴 통 int top; // 스택의 상단 void init_stack(void){ top = -1; } int push(in..

[C] 이중 연결 리스트 (Doubly Linked List) #include #include typedef struct _dnode{ int key; struct _dnode *prev; struct _dnode *next; } dnode; dnode *head, *tail; void init_dlist(void){ head = (dnode*)malloc(sizeof(dnode)); tail = (dnode*)malloc(sizeof(dnode)); head->next = tail; head->prev = head; tail->next = tail; tail->prev = head; } dnode *find_dnode(int k){ dnode *s; s = head->next; while (s->key..

[C] 요셉의 문제 (환형 연결 리스트) 요셉의 문제 :A부터 J까지의 10명의 사람이 시계 방향으로 순서대로 원을 지어 앉아 있다고 하자. 이때 A부터 시작하여서 4명 간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될 것인가? 결과 : A, E, I, D, J, G, F, H, C, B 응용하여 1부터 n까지의 숫자를 순서대로 나열되어 있고, 1부터 시작하여 m 간격으로 숫자를 뽑아내는 순서를 구하는 문제를 환형 연결 리스트를 사용하여 풀어본다. #include #include typedef struct _node{ int key; struct _node *next; } node; node *head; // 1부터 k까지의 값을 가지는 환형 연결 리스트 구성 void insert_node..

[C] 연결리스트 (Linked List) #include #include typedef struct _node{ int key; struct _node *next; } node; node *head, *tail; void init_list(void){ head = (node*)malloc(sizeof(node)); // head 메모리 할당 tail = (node*)malloc(sizeof(node)); // tail 메모리 할당 head->next = tail; // head의 다음은 tail tail->next = tail; // tail의 다음은 tail } node *insert_after(int k, node* t){ node *s; s = (node*)malloc(sizeof(node)); ..

[C] Turbo C 의 clrscr 함수 Visual C에서 컴파일하기 Turbo C 에서 사용하는 clrscr() 함수는 콘솔의 내용을 지워주는 함수이다.하지만 VC에서는 clrscr 함수를 제공하지 않으며, 아래의 내용을 추가하여 컴파일할 수 있다. #include void clrscr(void) { COORD Cur = { 0, 0 }; unsigned long dwLen; FillConsoleOutputCharacter(GetStdHandle(STD_OUTPUT_HANDLE), ' ', 80 * 25, Cur, &dwLen); } 출처: https://hyeonstorage.tistory.com/341?category=622873 [개발이 하고 싶어요]

[C] Turbo C의 gotoxy 함수 Visual C 에서 컴파일하기 Trubo C 에서는 콘솔에서 특정 x, y 좌표로 이동시켜주는 gotoxy 라는 함수가 제공된다.하지만 Visual C 에서는 gotoxy가 제공되지 않아 컴파일 되지 않는다. 아래의 함수를 추가해주면 VC에서도 gotoxy()를 사용할 수 있다. #include gotoxy(int x, int y)//내가 원하는 위치로 커서 이동 { COORD pos = { x - 1, y - 1 };//커서가 X좌표에서 -1 한값. Y좌표에서 -1한 값으로 이동 SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);// WIN32API 함수입니다 } 출처: https://hyeonst..