20210201(월)

자료구조

 

스택(Stack)

일시적으로 저장하기 위해 사용되는 자료구조 중 하나.

 

후입 선출(LIFO, Last In First Out) 순서로 데이터를 입출력 한다.

입력에 push, 출력에 pop 이란 용어를 사용한다.

 

▼ 배열로 만든 간단한 스택

#include <cstdio>

const static int STACK_SIZE = 10;

static int stackBuffer[STACK_SIZE] = { 0 };
static int currentIndex = 0;

void Push(int value)
{
    if (currentIndex < STACK_SIZE)
    {
        currentIndex++;
    }
    else
    {
        printf("Stack Is Overwrited.\n");
        return;
    }

    stackBuffer[currentIndex - 1] = value;
}

void Pop()
{
    if (currentIndex == 0)
    {
        printf("Stack is Empty.\n");
        return;
    }

    stackBuffer[currentIndex - 1] = 0;
    currentIndex--;
}

void Print()
{
    printf("STACK ARRAY : { ");
    for (int i = 0; i < STACK_SIZE; i++)
    {
        printf("%d ", stackBuffer[i]);
    }
    printf("}\n");
    printf("CURRENT INDEX : %d\n", currentIndex);
}

int main()
{
    for (int i = 0; i < STACK_SIZE; i++)
    {
        Push(i);
    }

    Print();

    Push(10);

    Pop();
    Pop();

    Print();

    return (0);
}

물론 CPP 표준 라이브러리에 <stack>으로 구현되어있다.

 

▼ <stack>의 사용법은 위와 다르지 않다.

#include <stack>

int main()
{
    std::stack<int> stack;

    for (int i = 0; i < STACK_SIZE; i++)
    {
        stack.push(i);
    }

    for (int i = 0; i < STACK_SIZE; i++)
    {
        stack.pop();
    }

    if (stack.empty())
        printf("STACK is EMPTY.\n");

    return (0);
}

Shuffle

▼ 배열로 구현한 간단한 셔플

#include <cstdio>
#include <cstdlib>
#include <ctime>

const static int SHUFFLE_SIZE = 10;

void Swap(int& lhs, int& rhs)
{
    int temp = lhs;
    lhs = rhs;
    rhs = temp;
}

void Shuffle(int* arr)
{
    for (int i = 0; i < SHUFFLE_SIZE; i++)
    {
        int randomIndex = rand() % SHUFFLE_SIZE;
        Swap(arr[i], arr[randomIndex]);
    }
}

void Print(int* arr)
{
    printf("SHUFFLE ARRAY : { ");
    for (int i = 0; i < SHUFFLE_SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("}\n");
}

int main()
{
    srand(static_cast<unsigned int>(time(NULL)));

    int shuffleBuffer[10] = { 0 };

    // SET SHUFFLE ARRAY
    for (int i = 0; i < SHUFFLE_SIZE; i++)
    {
        shuffleBuffer[i] = rand() % SHUFFLE_SIZE + 1;
    }

    // PRINT BEFORE
    Print(shuffleBuffer);

    // SHUFFLE
    Shuffle(shuffleBuffer);

    // PRINT AFTER
    Print(shuffleBuffer);

    return (0);
}

간단한 카드 게임

▼ 코드

#include <cstdio>
#include <clocale>
#include <cstdlib>
#include <ctime>
#include <stack>

// CARD STRUCT(52)
// S : Spade(13)
// D : Diamond1(13)
// H : Heart(13)
// C : Clover(13)

const static int DECK_SIZE = 52;

static bool isGameRunning = false;

enum class CardType {
    SPADE = 0,
    DIAMOND,
    HEART,
    CLOVER,
    NONE
};

//typedef struct {
//    wchar_t suite;
//    int number;
//}stCard;

typedef struct {
    CardType suite;
    int number;
}stCard;

// CARD DECK
static stCard cardDeck[52];
// CARD STACK
static std::stack<stCard> cardStack;

// PLAYER CARD
static stCard playerCard;
// COMPUTER CARD
static stCard computerCard;

// PLAYER SCROE
static unsigned int playerScore = 0;
// CPU SCORE
static unsigned int computerScore = 0;


void SetCardDeck(stCard deck[])
{
    for (int i = 0; i < DECK_SIZE; i++)
    {
        CardType s = CardType::NONE;
        switch (i / 13)
        {
            case static_cast<int>(CardType::SPADE) :
            {
                //s = L'♠';
                s = CardType::SPADE;
            }
            break;
            case static_cast<int>(CardType::DIAMOND) :
            {
                //s = L'◆';
                s = CardType::DIAMOND;
            }
            break;
            case static_cast<int>(CardType::HEART) :
            {
                //s = L'♥';
                s = CardType::HEART;
            }
            break;
            case static_cast<int>(CardType::CLOVER) :
            {
                //s = L'♣';
                s = CardType::CLOVER;
            }
            break;
        }
        deck[i].suite = s;
        deck[i].number = i % 13 + 1;
    }
}

wchar_t GetSuite(CardType cardType)
{
    wchar_t c = 0;
    switch (cardType)
    {
    case CardType::SPADE:
    {
        c = L'♠';
    }
    break;
    case CardType::DIAMOND:
    {
        c = L'◆';
    }
    break;
    case CardType::HEART:
    {
        c = L'♥';
    }
    break;
    case CardType::CLOVER:
    {
        c = L'♣';
    }
    break;
    }
    return (c);
}

void PrintDeck(stCard deck[])
{
    wprintf(L"<카드 덱>\n");
    for (int i = 0; i < DECK_SIZE; i++)
    {
        if (i % 13 == 0 && i != 0)
            wprintf(L"\n");
        wprintf(L"(%c %d)", GetSuite(deck[i].suite), deck[i].number);
    }
    wprintf(L"\n");
}

void Swap(stCard& lhs, stCard& rhs)
{
    stCard temp = lhs;
    lhs = rhs;
    rhs = temp;
}

void Shuffle(stCard deck[])
{
    for (int i = 0; i < DECK_SIZE; i++)
    {
        int randomIndex = rand() % DECK_SIZE;
        Swap(deck[i], deck[randomIndex]);
    }
}

void DeckToStack()
{
    for (int i = 0; i < DECK_SIZE; i++)
    {
        cardStack.push(cardDeck[i]);
    }
}

void Init()
{
    // CARD DECK BUILD
    SetCardDeck(cardDeck);
    PrintDeck(cardDeck);

    // CARD DECK SHUFFLE
    Shuffle(cardDeck);
    PrintDeck(cardDeck);

    // CARD DECK TO STACK
    DeckToStack();

    playerCard = { CardType::NONE,0 };
    computerCard = { CardType::NONE,0 };

    isGameRunning = true;
}

void PrintCards()
{
    wprintf(L"┌────────┐     ┌────────┐\n");
    wprintf(L"  %c %d           %c %d \n", GetSuite(playerCard.suite), playerCard.number, GetSuite(computerCard.suite), computerCard.number);
    wprintf(L"\n");
    wprintf(L"            vs\n");
    wprintf(L"\n");
    wprintf(L"\n");
    wprintf(L"\n");
    wprintf(L"└────────┘     └────────┘\n");
}

void CompareCards()
{
    if (playerCard.number > computerCard.number)
    {
        playerScore++;
    }
    else if (playerCard.number < computerCard.number)
    {
        computerScore++;
    }
    else
    {
        if (playerCard.suite > computerCard.suite)
        {
            playerScore++;
        }
        else
        {
            computerScore++;
        }
    }
}

void DrawCards()
{
    if (cardStack.empty())
    {
        return;
    }

    playerCard = cardStack.top();
    cardStack.pop();
    computerCard = cardStack.top();
    cardStack.pop();
}

void PrintResult()
{
    wprintf(L"〓〓〓〓〓 결과 〓〓〓〓〓\n");
    if (playerScore > computerScore)
    {
        wprintf(L"플레이어가 승리했습니다.\n");
        wprintf(L"플레이어 : %d 컴퓨터 : %d\n", playerScore, computerScore);
    }
    else
    {
        wprintf(L"컴퓨터가 승리했습니다.\n");
        wprintf(L"플레이어 : %d 컴퓨터 : %d\n", playerScore, computerScore);
    }

}

int main()
{
    srand(static_cast<unsigned int>(time(NULL)));
    _wsetlocale(LC_ALL, L"Korean");

    Init();

    while (isGameRunning)
    {
        if (cardStack.empty())
        {
            isGameRunning = false;
        }

        DrawCards();
        CompareCards();
        PrintCards();
    }
    PrintResult();

    return (0);
}

 

큐(Queue)

큐는 스택과 반대다.

입력을 먼저 할 수록 먼저 출력된다.

 

▼ 배열로 구현한 Queue.

#include <iostream>

using namespace std;

const static unsigned int SIZE = 5;

int A[SIZE];
int front = -1;
int rear = -1;

//Function to check if queue is empty or not
bool isempty()
{
    if (front == -1 && rear == -1)
        return true;
    else
        return false;
}

//function to enter elements in queue
void enqueue(int value)
{
    //queue is full
    if ((rear + 1) % SIZE == front)
        cout << "Queue is full \n";
    else
    {
        //first element inserted
        if (front == -1)
            front = 0;
        //insert element at rear
        rear = (rear + 1) % SIZE;
        A[rear] = value;
    }
}

//function to delete/remove element from queue
void dequeue()
{
    if (isempty())
        cout << "Queue is empty\n";
    else
        //only one element
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % SIZE;
}

//function to show the element at front
void showfront()
{
    if (isempty())
        cout << "Queue is empty\n";
    else
        cout << "element at front is:" << A[front];
}

//function to display queue
void displayQueue()
{
    if (isempty())
        cout << "Queue is empty\n";
    else
    {
        int i;
        if (front <= rear)
        {
            for (i = front; i <= rear; i++)
                cout << A[i] << " ";
        }
        else
        {
            i = front;
            while (i < SIZE)
            {
                cout << A[i] << " ";
                i++;
            }
            i = 0;
            while (i <= rear)
            {
                cout << A[i] << " ";
                i++;
            }
        }
    }
}

//Main Function
int main()
{
    int choice, flag = 1, value;
    while (flag == 1)
    {
        cout << "\n1.enqueue 2.dequeue 3.showfront 4.displayQueue 5.exit\n";
        cin >> choice;
        switch (choice)
        {
        case 1: cout << "Enter Value:\n";
            cin >> value;
            enqueue(value);
            break;
        case 2: dequeue();
            break;
        case 3: showfront();
            break;
        case 4: displayQueue();
            break;
        case 5: flag = 0;
            break;
        }
    }

    return 0;
}

 

 

▼ <queue> 예시 코드

#include <iostream>
#include <queue>

const static unsigned int QUEUE_SIZE = 10;

int main()
{
    std::queue<int> q;
    for (int i = 0; i < QUEUE_SIZE; i++)
    {
        q.push(i+1);
    }

    std::cout << "front element: " << q.front() << "\n";
    std::cout << "front element: " << q.back() << "\n";

    q.pop();

    std::cout << "front element: " << q.front() << "\n";
    std::cout << "front element: " << q.back() << "\n";

    return (0);
}