[CS50 코칭스터디] CS50 코칭스터디2기_6주차

6주차_자료구조

 

자료구조

 

자료구조, 데이터 구조란 컴퓨터에 자료를 효율적으로 저장하는 방식을 말하며 올바른 자료구조를 사용하는 것은 결국 메모리를 절약하고 수행시간을 절약하는 데 도움을 줄 수 있게 됩니다.

 

 

큐

큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조입니다.

값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’라는 방식을 따르게 됩니다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이죠.

은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일합니다.

배열이나 연결 리스트를 통해 구현 가능합니다.

 

 

스택

반면 스택은 역시 메모리 구조에서 살펴봤듯이 값이 위로 쌓이는 구조입니다.

따라서 값을 넣고 뺄 때 ‘후입 선출’ 또는 ‘LIFO’라는 방식을 따르게 됩니다. 가장 나중에 들어온 값이 가장 먼저 나가는 것이죠.

뷔페에서 접시를 쌓아 뒀을 때 사람들이 가장 위에 있는(즉, 가장 나중에 쌓인) 접시를 가장 먼저 들고 가는 것과 동일합니다.

역시 배열이나 연결 리스트를 통해 구현 가능합니다.

 

 

딕셔너리

딕셔너리는 ‘키’와 ‘값’이라는 요소로 이루어져 있습니다.

‘키’에 해당하는 ‘값’을 저장하고 읽어오는 것이죠. 마치 대학교에서 ‘학번’에 따라서 ‘학생’이 결정되는 것과 동일합니다.

일반적인 의미에서 ‘해시 테이블’과 동일한 개념이라고도 볼 수 있습니다.

역시 ‘키’를 어떻게 정의할 것인지가 중요합니다.

 

---

6주차 팀미션 

연결리스트로 Stack 만들기

 

#include <stdio.h>
#include <stdlib.h>

typedef struct stackNode {
    int data;
    struct stackNode* next;
} StackNode;

//Stack 구조체 : node 생성
StackNode* createStackNode(int data) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data; // 입력받은 int를 data type에 넣는다
    node->next = NULL; // node에는 NULL을 넣는다
    return node; // 새롭게 생성된 node 반환
}

int isEmpty(StackNode* root) {
    return !root;
}

void push(StackNode** root, int data) {
   if ((!root)) return;
 
    StackNode* item = (StackNode*)malloc(sizeof(StackNode)); //item이라는 새로운 node 생성
    item -> data = data; // 새로운 node data 저장
    item -> next = (*root); // 이때 포인터는 root의 첫번째 node를 가리킨다. 
    (*root) = item; // item node는 새로운 root가 됨
    printf("%d pushed to stack\n", data);
}

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999; //데이터가 없을 경우 -9999를 리턴
  
    StackNode* temp = *root; // temp를 선언해 맨 위 노드의 주소값 저장
    int popped = temp -> data; // popped 변수에 맨 위 노드의 데이터 저장
    *root = temp -> next; // root 노드를 두번째 노드로 옮김
    free(temp); // 맨 위 노드 제거
    return popped; // 데이터 반환
}

int peek(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    return (*root)->data;
}

int main() {
    StackNode* root = NULL;

    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    push(&root, 40);

    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));

    push(&root, 50);
    printf("%d peeked from stack\n", peek(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    return 0;
}