Say

🔵원형 연결리스트 마지막 노드가 첫 번째 노드를 가리킴 하나의 노드에서 다른 모든 노드로의 접근 가능 > 단순 연결리스트보다 삽입, 삭제 더 용이해짐 > 삽입,삭제 시 선행 노드를 항상 알아야함 헤드 포인터가 마지막 노드 가리킴 🟡 원형 연결리스트 코드 #include #include typedef int element; typedef struct { element data; struct ListNode* link; }ListNode; void print_list(ListNode* head) { ListNode* p; if (head == NULL) {// 마지막 노드인 경우 return; } p = head->link; do { printf("%d->", p->data);// 앞쪽 노드부터 출력 p =..

공백 상태 > front와 rear가 NULL값 🟡 연결리스트로 구현한 큐 코드 #include #include typedef int element; typedef struct { element data; struct StackNode* link; }QueueNode; typedef struct { QueueNode* front, *rear; } LinkedQueueType; void init(LinkedQueueType* s) { s->front = s->rear = 0; } int is_full(LinkedQueueType* s) { return 0; } int is_empty(LinkedQueueType* s) { return (s->front == NULL); } void push(LinkedQu..

연결리스트 장점 > 크기 제한X 🟡 연결리스트로 구현한 스택 코드 #include #include typedef int element; typedef struct { element data; struct StackNode* link; }StackNode; typedef struct { StackNode* top; } LinkedStackType; void init(LinkedStackType* s) { s->top = NULL; } int is_full(LinkedStackType* s) { return 0; } int is_empty(LinkedStackType* s) { return (s->top == NULL); } void push(LinkedStackType* s, element item) { ..

🔵 원형 덱 double-ended queue 원형 큐는 항상 하나의 자리를 비워둠 front, rear에서 모두 삽입, 삭제가 가능한 큐 front, rear 모두 0으로 초기화 공백 상태 > front == rear 포화 상태 > front = (rear + 1) % M큐크기 🟡 원형 덱 코드 add_rear 뒤로 이동 > 빈 공간에 삽입 get_front 뒤로 이동 > 해당 값 삭제 get_rear 삭제 > 앞으로 이동 add_front 삽입 > 앞으로 이동 #include #include #define MAX_SIZE 10 typedef int element; typedef struct { int front, rear; element data[MAX_SIZE]; } QueueType; void i..

🔵 원형 큐는 항상 하나의 자리를 비워둠 > 포화 상태 - front가 rear보다 하나 앞에 있는 경우 front == (rear + 1) % M큐크기 > 공백 상태 - front == rear 인 경우 🟡 원형 큐 코드 #include #include #define MAX_SIZE 10 typedef int element; typedef struct { int front, rear; element data[MAX_SIZE]; } QueueType; void init(QueueType* q) { q->front = -1; q->rear = -1; } int is_full(QueueType* q) { return q->front == (q->rear + 1) % MAX_SIZE;// 원형 큐의 경우 } ..

🔵선형 큐 front, rear 초기값은 -1 선입선출 FIFO 🟡 선형 큐 코드 #include #include #define MAX_SIZE 100 typedef int element; typedef struct { int front; int rear; element data[MAX_SIZE]; } QueueType; void init(QueueType* q) { q->front = -1; q->rear = -1; } int is_full(QueueType* q) { return q->rear == MAX_SIZE - 1; } int is_empty(QueueType* q) { return q->front == q->rear; } void enqueue(QueueType* q, int item) { ..

🔵 infix -> postfix 변환 조건 스택에 연산자만 push 괄호인 경우 왼쪽 괄호는 무조건 스택에 push 오른쪽 괄호인 경우 왼쪽괄호 삭제될 때까지 위에 쌓인 연산자 pop 괄호가 아닌 경우 (+, -, *, /) 연산자 우선순위 비교하기 스택에 들어있는 연산자 우선순위가 더 큰 경우 해당 연산자 pop 🟡 중위표기식 후위표기식으로 변환하는 코드 #include #include #include #define MAX_SIZE 100 typedef char element; typedef struct { int top; element data[MAX_SIZE]; } StackType; void init(StackType* s) { s->top = -1; } int is_full(StackType*..

🔵 괄호 검사 조건 오른쪽 괄호 만날 때까지 왼쪽 괄호 push 오른쪽 괄호 만났을 경우 스택에 들어있는 왼쪽 괄호 pop 💥오류인 경우 스택이 비어있을 때 괄호 종류가 맞지 않을 때 오른쪽 괄호 끝까지 스캔했을 경우 💥오류인 경우 스택이 비어있지 않았을 때 🟡 괄호 검사 코드 #include #include #define MAX_SIZE 100 typedef char element; typedef struct { int top; element data[MAX_SIZE]; } StackType; void init(StackType* s) { s->top = -1; } int is_full(StackType* s) { return s->top == MAX_SIZE - 1; } int is_empty(Sta..

🟡 동적 배열 스택 코드 시간 복잡도 O(1) #include #include typedef int element; typedef struct { element* data; int top; int capacity; // 현재 크기 } StackType; void init(StackType* s) { s->top = -1; s->capacity = 1; s->data = (element*)malloc(s->capacity * sizeof(element)); } int is_full(StackType *s) { if (s->top == s->capacity - 1) return 1; else return 0; } int is_empty(StackType *s) { if (s->top == -1) return..