프로그래밍노리터

스택은 데이터의 순서를 뒤집어야 하는 경우에 유용하게 쓰인다. 스택을 임시 메모리로 사용하면 코드가 간결해진다. (1) 문자열 뒤집기 문자열의 글자 순서를 뒤집는 문제는 스택을 이용하여 다음과 같이 해결할 수 있다. (널문자는 그대로 있음) void reverse(char* word) { stack_t stack; int i; for (i = 0; i < strlen(word); i++) push(&stack, word[i]); i = 0; while (!is_empty(&stack)) word[i++] = pop(&stack); } (2) 2진수로 바꾸기 2진수로 바꾸는 문제는 2로 나눈 나머지를 거꾸로 이어 붙여서 2진수를 만들 수 있다. 이 문제도 스택을 이용해서 다음과 같이 간단하게 바꿀 수 있다..

큐에서 디큐한 후에 남는 공간을 비워두지 않기 위해 원형 큐를 사용할 수 있는데, 스택으로 큐를 구현하는 방법도 있다. 여기서는 스택 두 개를 이용해서 큐를 구현하는 방법을 살펴본다. 먼저 큐 구조체의 정의를 살펴보자. (요소의 타입(typedef ... element)은 스택에서 정의된다.) typedef struct queue_t { // 큐 타입 stack_t instack; stack_t outstack; } queue_t; 그러면 큐의 연산들은 다음과 같이 정의된다. init_queue: 두 개의 스택을 초기화한다. transfer: instack의 것을 pop하여 모두 outstack으로 옮겨 push한다. enqueue: 요소를 instack에 넣는다. instack이 꽉차있으면 ERROR...

트리 정보를 입력하여 생성하는 것은 쉽지 않은 일이다. 일반적으로 많이 사용되는 이진 트리 형태로 데이터를 읽어 구축하는 프로그램을 생각해 보자. 먼저 후위표기식 형태의 이진연산자로 구성된 수식을 읽어들여 트리를 구축할 수 있다. 다음과 같은 후위표기식을 입력으로 받아 이진 트리를 구축하는 문제를 생각해 보자. 94-385%+*435+2*++ 이 수식에 대한 이진트리는 다음과 같은 형태로 나타낼 수 있다. 이것은 트리의 출력기능을 통해 출력한 결과다. 트리의 노드는 연산자인 경우 넌터미널로 자식을 가진 노드가 되고 숫자는 터미널 노드여서 자식을 갖지 않는다. 그리고 숫자의 경우는 그 숫자를 노드의 데이터로 가진다. 다음 코드는 스택을 이용해 후위표기식의 계산과 같은 방식으로 숫자는 푸시하고 연산자가 나오..