[C/자료구조] 스택 2개로 큐 구현하기

C언어를 이용한 자료구조 실습입니다.

스택을 2개를 이용하여 큐를 구현합니다.

구현한 큐를 사용해 n번째 까지 피보나치 수열을 출력합니다.

---

 

I. 문제

정수를 포함하는 2개의 스택 stk1, stk2가 주어져 있을 때, 이 2개의 스택을 이용하여 큐를 구현하고자 한다. 다음 큐 연산에 대한 알고리즘을 작성하라.

 

- is_empty()

- is_full()

- enqueue(e) : 삽입 연산 (e는 삽입할 항목이다.)

-  dequeue() : 삭제 연산

 

사용자로부터 정수 n을 입력받고, n까지의 피보나치 수열을 출력하는 C 프로그램을 작성하고, 테스트하라. 단, 위에서 작성한 큐를 이용하라.

 

---

II. 구현

 

[구현 알고리즘]

 

1. 스택1과 스택2를 생성한다.   2. push가 발생하면 스택1에 넣는다.   3. pop이 발생하면,       3-1. 스택1에 push된 모든 요소를 스택2로 옮긴다.       3-2. 스택2의 값을 pop해 반환한다.   4. 스택2가 빌때까지 3-2를 실행한다.   5. 스택2가 비었다면 3-1부터 다시 반복한다.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100  // 스택 최대 용량
#define MAX_QUEUE_SIZE 100  // 큐 최대 용량

typedef struct {
	int data[MAX_STACK_SIZE];
	int top;
}Stacktype;

void init_stack(Stacktype* s) {
	s->top = -1;
}

int is_empty(Stacktype* s) {
	return s->top == -1;
}

int is_full(Stacktype* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}

void push(Stacktype* s, int item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	s->data[++(s->top)] = item;
}


int pop(Stacktype* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}

	else return s->data[s->top--];
}

int peek(Stacktype* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}


/*  스택 기본 골격  */


// 큐 구조체 선언
typedef struct {
	Stacktype stk1, stk2; // 스택타입을 이용
}Queuetype; 

// 초기화
void Queue_init(Queuetype* q) { 
	q->stk1.top = -1; q->stk2.top = -1;
}

// 공백
int is_queue_empty(Queuetype* q) { 
	if (q->stk1.top == -1 && q->stk2.top == -1) return 1;
	else return 0;
}

// 포화
int is_queue_full(Queuetype* q) { 
	// 둘의 top값이 MAX_QUEUE_SIZE-2거나 stk1이 포화일 때
	return (q->stk1.top + q->stk2.top == (MAX_QUEUE_SIZE - 2)) || (is_full(q->stk1.data));
}

// 삽입 
void enqueue(Queuetype* q, int e) {
	if (!is_queue_full(q))
		push(q->stk1.data, e); // stk1에 넣음
	else
		printf("큐가 포화상태입니다.\n"); // 아니라면 출력
}

// 삭제
int dequeue(Queuetype* q) {
	if (!is_queue_empty(q)) {
		if (is_empty(q->stk2.data)) { // stk2가 비어있다면
			while (!is_empty(q->stk1.data)) {  // stk1가 빌때까지 반복
				push(q->stk2.data, pop(q->stk1.data)); // stk2에 stk1 요소를 넣음
			}
		}
		return 	pop(q->stk2.data); // stk2스택 요소 반환
	}
	else {
		printf("큐가 공백상태입니다.\n"); // 아니라면 출력
		return -1;
	}
}

// 피보나치 수열을 출력
void fibo(int input_num) 
{
	Queuetype q;		// 큐 생성
	Queue_init(&q);		// 큐 초기화
	enqueue(&q, 0);		// fibo(0)값 입력
	enqueue(&q, 1);		// fibo(1)값 입력

	for (int i = 0; i <= input_num; i++){
		if (i == 0)
			printf("fibo(0) = 0\n");	// fibo(0)값 출력
		else if (i == 1)
			printf("fibo(1) = 1\n");	// fibo(1)값 출력

		else {
			int first = dequeue(&q);	// 요소 두개를 꺼내어
			int second = dequeue(&q);
			int val = first + second;	// 다음항 구하기
			
			printf("fibo(%d) = %d\n", i, val);

			enqueue(&q, second);		// 사용한 2번째 항 다시 넣기 -> 첫번째 요소가 됨
			enqueue(&q, val);			// 구한 다음항의 값넣기 -> 두번째 요소가 됨
		}
	}
}


int main(void) {

	int input_num = 0; // 사용자로부터 입력받음
	printf("n을 입력해주세요 : ");
	scanf_s("%d", &input_num, sizeof(input_num));

	fibo(input_num); // fibo함수 호출

	return 0;
}

 

III. 결과

 

감사합니다.

---

공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.