3. Stack & Queue (1)

Stack & Queue

: 가장 기본적인 선형 구조(Linear Structure) 로, 데이터의 삽입과 삭제 순서를 다르게 처리하는 점이 특징

---

- Stack (스택)

: LIFO (Last In, First Out) 구조

 = 나중에 들어온 데이터가 먼저 나가는 구조

 

예를 들어,
[1, 2, 3] 상태에서 push(4) → [1, 2, 3, 4],
이후 pop() → 4가 제거됨.

 

- Stack ADT (Abstract Data Type)

push(x)	스택에 원소 x를 삽입
pop()	스택의 맨 위 원소를 삭제하고 반환
peek()	맨 위 원소를 확인
isEmpty()	스택이 비어 있는지 확인
isFull()	스택이 꽉 찼는지 확인

 

 

- Stack in C (배열 기반 구현)

배열을 사용해 간단히 스택을 구현할 수 있다.

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

void init(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 x) {
    if (isFull(s)) return;
    s->data[++(s->top)] = x;
}

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

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

• top은 스택의 가장 위 인덱스를 가리킴
• 배열이 꽉 차면 push 불가
• 비어 있으면 pop 불가

 

- Stack using Dynamic Array (동적 배열 기반)

고정된 크기 대신, 필요할 때마다 크기를 늘리는 방식이다.

typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

Stack* createStack(int cap) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (int *)malloc(cap * sizeof(int));
    s->top = -1;
    s->capacity = cap;
    return s;
}

void resize(Stack *s) {
    s->capacity *= 2;
    s->data = (int *)realloc(s->data, s->capacity * sizeof(int));
}

void push(Stack *s, int x) {
    if (s->top == s->capacity - 1) resize(s);
    s->data[++(s->top)] = x;
}

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

• malloc / realloc 을 이용해 동적 크기 조정
• 데이터 양이 유동적인 상황에 유리함
• 공간 복잡도는 O(n), push와 pop의 시간 복잡도는 평균 O(1)

---

- Queue (큐)

: FIFO (First In, First Out) 구조다.
즉, 먼저 들어온 데이터가 먼저 나가는 구조

 

예를 들어,
enqueue(1), enqueue(2), enqueue(3) → [1, 2, 3],
dequeue() → 1이 제거됨.

 

- Queue ADT

enqueue(x)	큐의 뒤(rear)에 데이터 삽입
dequeue()	큐의 앞(front)에서 데이터 삭제
peek()	맨 앞 데이터를 반환
isEmpty()	비었는지 확인
isFull()	꽉 찼는지 확인

 

- Queue in C (배열 기반 구현)

#define MAX_QUEUE_SIZE 100
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front, rear;
} Queue;

void init(Queue *q) {
    q->front = q->rear = -1;
}

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

int isFull(Queue *q) {
    return q->rear == MAX_QUEUE_SIZE - 1;
}

void enqueue(Queue *q, int x) {
    if (isFull(q)) return;
    q->data[++(q->rear)] = x;
}

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

• front는 삭제 위치, rear는 삽입 위치
• 한 번 dequeue되면 앞쪽 공간은 재사용 불가 → 비효율적

 

- Circular Queue (원형 큐)

배열을 원형 형태로 재사용하여 공간 낭비를 해결한 형태다.

#define MAX_QUEUE_SIZE 5
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front, rear;
} CircularQueue;

void init(CircularQueue *q) {
    q->front = q->rear = 0;
}

int isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

int isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(CircularQueue *q, int x) {
    if (isFull(q)) return;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = x;
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) return -1;
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

• % 연산을 통해 인덱스를 순환시킴
• 공간 낭비 없이 연속적인 삽입/삭제 가능
• 시간 복잡도: O(1)

---

정리하자면,

구조	특징	삽입 / 삭제	접근
Stack	LIFO (후입선출)	O(1) / O(1)	맨 위만 접근
Queue	FIFO (선입선출)	O(1) / O(1)	맨 앞만 접근
Circular Queue	공간 재활용 가능	O(1) / O(1)	인덱스 순환 구조