[1주차 TIL] KnockOn Bootcamp - 스택 & 큐

📚 1. 스택과 큐 기본 정리

자료구조	작동 원리	주요 연산	비고
스택(Stack)	후입선출 (LIFO)	push(), pop()	함수 호출 스택, 버퍼 보호 등
큐(Queue)	선입선출 (FIFO)	enqueue(), dequeue()	작업 대기열, 패킷 처리 등

🧠 왜 리버싱에서 중요할까?

• 스택 : 함수 호출과 리턴 시 레지스터 및 복귀 주소가 저장되는 공간 → 리버서들은 항상 스택을 추적해야 함 (예: push ebp, call, pop)
• 큐 : 이벤트 처리, 시스템 메시지 전달, 패킷 송수신 등 → 게임 서버 구조 분석 시 자주 나옴

🛠 도전 과제 1 – 스택 구현

1-1. 배열 기반 스택 (Array Stack)

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

int isEmpty(Stack* s) {
    return s->top == -1;
}

int isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack* s, int value) {
    if (isFull(s)) return;
    s->data[++(s->top)] = value;
}

int pop(Stack* s) {
    if (isEmpty(s)) return -1;
    return s->data[(s->top)--];
}

1-2. 연결리스 기반 스택 ( Linked List Stack)

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

typedef struct {
    StackNode* top;
} LinkedStack;

void push(LinkedStack* s, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(LinkedStack* s) {
    if (!s->top) return -1;
    StackNode* temp = s->top;
    int result = temp->data;
    s->top = temp->next;
    free(temp);
    return result;
}

🛠 도전 과제 2 – 큐 구현

2-1. 배열 기반 큐 (Array Queue)

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

int isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}

int isQueueFull(Queue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

void enqueue(Queue* q, int value) {
    if (isQueueFull(q)) return;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = value;
}

int dequeue(Queue* q) {
    if (isQueueEmpty(q)) return -1;
    q->front = (q->front + 1) % MAX_SIZE;
    return q->data[q->front];
}

2-1. 연결 리스트 기반 큐(Linked List Queue)

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} LinkedQueue;

void enqueue(LinkedQueue* q, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = value;
    newNode->next = NULL;
    if (!q->rear) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeue(LinkedQueue* q) {
    if (!q->front) return -1;
    QueueNode* temp = q->front;
    int result = temp->data;
    q->front = temp->next;
    if (!q->front) q->rear = NULL;
    free(temp);
    return result;
}

🔐 실무/리버싱 적용 예시

상황	구조
함수 호출 시 스택프레임 구성	스택
메시지 큐 분석 (윈도우 메시지 루프 등)	큐
시스템 콜 트레이스	스택
오브젝트 이벤트 처리 큐	큐
BOF (버퍼 오버플로우) 공격 시 스택 조작	스택