본문 바로가기
Computer Science/자료구조

[자료구조] ep6+) 두 개의 큐로 스택 설계

by 클레어몬트 2024. 6. 9.

문제) 두 개의 큐로 스택을 설계하라

프로그램 요구사항

S : S에 대해 isEmpty() 호출 (isEmpty)
t : S에 대해 top() 호출 (top)
p n1 n2 n3 ... : S에 대해 push(n1), push(n2), push(n3) ... 를 차례로 호출 (push)
P : S에 대해 push(n)을 100만번 호출 - 여기서 n은 10~99 사이의 정수 난수 (pushMillion)

o : S에 대해 pop() 호출 (pop)

q : 수행 종료 (quit)

 

test case

 

  1. 실행예에서 괄호 속의 수는 해당 명령 수행직후의 스택 S 사이즈를 나타낸다.
  2. cputime X.XXXXXXXX는 측정된 cputime in milliseconds이다. 이 실행시간은 각 부함수에 대한 호출과 반환 사이에 소요된 cputime을 표시해야 한다. 이 경우, 상수 시간을 나타내는 cputime은 거의 0초 혹은 아예 0초로 표시되더라도 무방하다.
  3. 위 실행 예에서 ??는 임의의 난수 정수를 나타낸다. 즉, 물음표 두 개가 아닌, S가 실제 반환한 10~99 사이의 두 자릿수 정수 난수를 말한다.
  4. 위 실행 예 수행에서, 자신의 PC 성능 문제(너무 느림)로 인해 불가피하다면 100만 대신 10만을 사용해서 작성해도 좋다.

 

주의

1)  S를 만들기 위한 부품으로 사용되는 큐들은 배열 또는 연결리스트 가운데 어느 것을 사용하여 구현하더라도 무방하며, 만약 배열로 할 경우 각 큐의 할당 크기는 위 실행 예를 구현하기에 충분한 크기로 설정하여 크기 부족으로 인한 예외상황이 발생하지 않도록 하라.

2)  S의 각 메쏘드가 최선의 점근시간 성능에 미치지 않으면 안 된다.

3)  부품 큐들은 size 메쏘드를 지원하지 않는다. 이 메쏘드(또는 이름만 다를 뿐 큐의 원소 수를 반환하는 유사 메쏘드)를 구현하여 사용하는 것은 허용되지 않는다. 참고로 스택 S가 size 메쏘드를 지원하는 것은 금지하지 않는다.

4)  상수시간 작업의 cputime이 0초 또는 거의 0초로 나타나는 것은 허용함.

5)  모듈화 설계할 것. 특히, 명령 에코, 괄호 속의 현재 스택 원소 수, cputime 등에 대한 계산 및 출력은 모두 (각 부함수가 아닌) 주함수에서 수행해야 함.

6)  주어진 큐 두 개만 이용해서 S를 구현해야 한다. 다시 말해, S 내에 주어진 두 개의 큐 이외의 다른 데이터구조를 포함할 수 없으며, 각각의 큐 내에도 큐 이외의 다른 데이터구조를 당연히 포함할 수 없다.

 

 

 

 

 

 

[전략] 메인큐 원소가 하나 남을 때까지 임시큐에 다 넣고, 마지막 원소는 다른 곳에 저장한다.

그다음 임시큐에 있는 모든 요소를 다시 메인큐에 넣고, 마지막 원소를 반환한다.

메인큐(Q1): push 작업 / 임시큐(Q2): pop 작업

 

 

 

 

 

 

 

 

(전체코드) - Windows에서만 실행 가능

// 두 개의 큐를 이용한 스택설계

// 메인큐와 임시큐가 있다
// 메인큐가 비어있으면 비어있는 스택이다
// 메인큐 원소가 하나 남을 때까지 임시큐에 다 넣고, 마지막 원소는 다른 곳에 따로 저장
// 임시큐에 있는 모든 요소를 다시 메인큐에 넣고, 마지막 원소를 반환 
// 계속해 반복

// cputime은 ms단위
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <time.h>
#pragma warning (disable:4996)

#define MAX_INPUT_SIZE 1000

// 큐 노드 구조체
typedef struct NODE { 
    int e;
    struct NODE* next;
} NODE;

// 큐 구조체
typedef struct QUEUE { 
    NODE* front;
    NODE* rear;
} QUEUE;

// 두 개의 큐를 사용하는 스택 구조체
typedef struct STACK { 
    QUEUE* mainQueue;
    QUEUE* subQueue;
} STACK;

int g_N = 0; // 스택의 크기
int g_isError = 0; // Empty Stack Exception!!

NODE* newNode(int e);
QUEUE* createQueue();
void enqueue(QUEUE* queue, int e);
int dequeue(QUEUE* queue);
int isQueueEmpty(QUEUE* queue); // 메인큐가 비어있으면 비어있는 스택이다

STACK* createStack();
void push(STACK* S, int e);
void pushMillion(STACK* S);
int pop(STACK* S);
int top(STACK* S);
int isEmpty(STACK* S); // 스택이 비어있는지
void quit(STACK* S);

int main() {
    STACK* S = createStack();
    char cmd[MAX_INPUT_SIZE] = { 0 };
    int n;
    int f;
    LARGE_INTEGER ticksPerSec;
    LARGE_INTEGER start, end, diff;
    srand(time(NULL));

    while (1) {
        gets(cmd);
        if (cmd[0] == 'S') { // isEmpty
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            f = isEmpty(S);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            if (f == 1) { // Empty case
                printf("Empty (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
            }
            else if (f == 0) { // Nonempty case
                printf("Nonempty (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
            }
        }
        else if (cmd[0] == 't') { // top
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            n = top(S);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            if (n == -1 && g_isError == 1) {
                printf("Empty Stack Exception!! (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
                g_isError = 0;
            }
            else {
                printf("%d (%d), cputime = %.10f\n", n, g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
            }
        }
        else if (cmd[0] == 'p') { // push
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            char* token = strtok(cmd + 1, " ");
            while (token != NULL) {
                n = atoi(token);
                push(S, n);
                token = strtok(NULL, " ");
                g_N++;
            }
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("OK (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd[0] == 'P') { // pushMillion
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            pushMillion(S);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            g_N += 1000000;
            printf("OK (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd[0] == 'o') { // pop
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            n = pop(S);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            if (n == -1 && g_isError == 1) {
                printf("Empty Stack Exception!! (%d), cputime = %.10f\n", g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
                g_isError = 0;
            }
            else {
                printf("%d (%d), cputime = %.10f\n", n, --g_N, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
            }
        }
        else if (cmd[0] == 'q') { // quit
            quit(S);
            return;
        }
    }
    return 0;
}

NODE* newNode(int e) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->e = e;
    newNode->next = NULL;
    return newNode;
}

QUEUE* createQueue() {
    QUEUE* queue = (QUEUE*)malloc(1 * sizeof(QUEUE));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(QUEUE* queue, int e) {
    NODE* temp = newNode(e);
    if (queue->rear == NULL) { // 노드가 하나도 없을 경우
        queue->front = temp;
        queue->rear = temp;
        return;
    }
    queue->rear->next = temp; // 새 노드를 마지막 노드로 큐 끝에 연결
    queue->rear = temp; // rear가 새 노드(마지막 노드)를 가리키게 설정
}

int dequeue(QUEUE* queue) {
    if (queue->front == NULL) { // 큐가 비어있는 경우
        return -1;
    }
    NODE* temp = queue->front;
    int e = temp->e;
    queue->front = queue->front->next;
    if (queue->front == NULL) { // 큐 노드가 하나만 있는 경우
        queue->rear = NULL;
    }
    free(temp);
    return e;
}

int isQueueEmpty(QUEUE* queue) {
    return (queue->front == NULL);
}

// 두 개의 메인큐와 보조큐를 사용하는 스택
STACK* createStack() { 
    STACK* S = (STACK*)malloc(1 * sizeof(STACK));
    S->mainQueue = createQueue();
    S->subQueue = createQueue();
    return S;
}

// push: 메인큐에 enqueue
void push(STACK* S, int e) { 
    enqueue(S->mainQueue, e);
}

void pushMillion(STACK* S) {
    for (int i = 0; i < 1000000; i++) {
        enqueue(S->mainQueue, rand() % 90 + 10);
    }
}

// 메인큐 원소가 하나 남을 때까지 임시큐에 다 넣고, 마지막 원소는 다른 곳에 따로 저장
// 임시큐에 있는 모든 요소를 다시 메인큐에 넣고, 마지막 원소를 반환 
int pop(STACK* S) { 
    // 메인큐가 비어있으면 비어있는 스택이다
    if (isQueueEmpty(S->mainQueue)) { 
        g_isError = 1;
        return -1;
    }
    // 메인큐 원소가 하나 남을 때까지 임시큐에 다 넣고
    while (S->mainQueue->front->next != NULL) {
        enqueue(S->subQueue, dequeue(S->mainQueue));
    }
    // 마지막 원소는 다른 곳에 따로 저장
    int e = dequeue(S->mainQueue);
    // 임시큐에 있는 모든 요소를 다시 메인큐에 넣는다
    // 이 뜻은 메인큐와 보조큐를 스왑하는 것과 같다
    QUEUE* temp = S->mainQueue;
    S->mainQueue = S->subQueue;
    S->subQueue = temp;
    // 마지막 원소를 반환
    return e;
}

// pop 함수의 과정과 비슷하지만
// 다른 점은 마지막 원소가 mainQueue에서 제거된 후 다시 subQueue에 추가된다
int top(STACK* S) {
    // 메인큐가 비어있으면 비어있는 스택이다
    if (isQueueEmpty(S->mainQueue)) {
        g_isError = 1;
        return -1;
    }
    // 메인큐 원소가 하나 남을 때까지 임시큐에 다 넣고
    while (S->mainQueue->front->next != NULL) {
        enqueue(S->subQueue, dequeue(S->mainQueue));
    }
    // 마지막 원소는 다른 곳에 따로 저장한 후
    int e = dequeue(S->mainQueue);
    // 다시 보조큐에 마지막 원소를 추가
    enqueue(S->subQueue, e);
    // 임시큐에 있는 모든 요소를 다시 메인큐에 넣는다
    // 이 뜻은 메인큐와 보조큐를 스왑하는 것과 같다
    QUEUE* temp = S->mainQueue;
    S->mainQueue = S->subQueue;
    S->subQueue = temp;
    // 마지막 원소를 반환
    return e;
}

// 메인큐가 비어있으면 비어있는 스택이다
int isEmpty(STACK* S) {
    return isQueueEmpty(S->mainQueue);
}

void quit(STACK* S) {
    free(S);
}

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)

저작자표시 비영리 변경금지

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] ep7-2) 트리 순회  (0) 2024.06.10
[자료구조] ep7-1) 트리(Tree)  (1) 2024.06.09
[자료구조] ep6-3) 데크(Deque)  (0) 2024.06.09
[자료구조] ep6-2) 원형 큐(Circular Queue)  (0) 2024.06.08
[자료구조] ep6-1) 큐(Queue)  (0) 2024.06.08

관련글

티스토리툴바