Data Structure - 2

@Super_E끌림·2025년 6월 29일

C Deque queue stack 데이터 구조

스택 (Stack)

스택이란? 항목들이 쌓여 있는 구조로 LIFO(Last-In, First-Out) 원칙을 따른다.

주요 기능에는 push, pop이 있고 이 기능을 수행하기 위해서는 여러가지 요소가 필요하다.

push : 데이터를 삽입한다.
pop : 데이터를 삭제한다.
peek : 스택의 요소를 리턴한다.
top : 스택의 맨 위에 있는 자료를 가리키는 변수(비어있을 때 top = -1)
MAX : 스택의 최대 크기
isEmpty : 스택이 비어있는지 검사한다.
isFull : 스택이 꽉 차있는지 검사한다.

스택을 직접 구현 할때는 아래의 그림을 보고 구현하시면 됩니다.

배열 기반 스택 구현 - C

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

#define MAX 100  // 스택의 최대 크기

int stack[MAX];  // 스택 배열
int top = -1;    // top 인덱스 초기값

// 스택이 비었는지 확인
bool isEmpty() {
    return top == -1;
}

// 스택이 가득 찼는지 확인
bool isFull() {
    return top == MAX - 1;
}

// 요소를 스택에 삽입
void push(int data) {
    if (isFull()) {
        printf("Stack Overflow! 더 이상 삽입할 수 없습니다.\n");
        return;
    }
    stack[++top] = data;
    printf("Pushed: %d\n", data);
}

// 스택에서 요소 제거
int pop() {
    if (isEmpty()) {
        printf("Stack Underflow! 제거할 요소가 없습니다.\n");
        return -1;
    }
    return stack[top--];
}

// 스택의 최상단 요소를 반환 (제거 X)
int peek() {
    if (isEmpty()) {
        printf("Stack is empty! 조회할 요소가 없습니다.\n");
        return -1;
    }
    return stack[top];
}

// 직접 구현하기
int main() {

}

큐 (Queue)

일반 큐

일반 큐란? 선형 자료구조로 FIFO(First-In-First-Out) 원칙을 따른다.

큐는 상황에 따라 선형 외에도 원 형태로 된 큐도 존재합니다.

큐의 주요 기능은 스택과 마찬가지로 Enqueue(push()), Dequeue(pop())가 있고 이 기능들을 수행하기 위해서는 여러가지 요소가 필요하다.

Enqueue : 데이터를 삽입한다.
Dequeue : 데이터를 삭제한다.
rear : 가장 뒤에 있는 데이터의 index
isEmpty : 큐가 비어 있는지 검사한다.
isFull : 큐가 꽉 차있는지 검사한다.

일반 큐 구현 - C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

typedef struct {
    int items[SIZE];
    int rear;  // 요소 개수 및 다음 삽입 위치
} Queue;

// 큐 초기화
void initQueue(Queue *q) {
    q->rear = 0;
}

// 큐가 비었는지 확인
int isEmpty(Queue *q) {
    return q->rear == 0;
}

// 큐가 가득 찼는지 확인
int isFull(Queue *q) {
    return q->rear == SIZE;
}

// Enqueue: 큐에 요소 삽입
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is Full!\n");
        return;
    }
    q->items[q->rear++] = value;
    printf("Enqueued: %d\n", value);
}

// Dequeue: 요소 제거 (앞으로 이동)
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty!\n");
        return -1;
    }
    int value = q->items[0];  // 맨 앞 요소 추출

    // 모든 요소를 한 칸씩 앞으로 당김
    for (int i = 1; i < q->rear; i++) {
        q->items[i - 1] = q->items[i];
    }
    q->rear--;  // rear 한 칸 감소

    printf("Dequeued: %d\n", value);
    return value;
}

// 큐 상태 출력
void display(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty!\n");
        return;
    }

    printf("Queue: ");
    for (int i = 0; i < q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

// 직접 구현
int main() {
    
}

원형 큐

원형 큐란? 일반 큐의 단점을 보완한 원형 자료구조다.

일반 큐 즉, 선형 큐의 단점은 데이터를 삭제할 때마다 데이터를 한칸씩 당겨 front 없이도 가능하지만 이러면 불필요한 움직이 있어 효울적이지 못합니다.
그래서 이 문제를 해결하기 위해 이 원형 큐가 나왔습니다.
이렇게 되면 데이터를 움직이지 않아도 순환하는 특징을 이용해 데이터를 효율적이게 삭제할 수 있습니다.

Enqueue : 데이터를 삽입한다.
Dequeue : 데이터를 삭제한다.
front : 가장 앞에 있는 데이터의 index
rear : 가장 뒤에 있는 데이터의 index
isEmpty : 큐가 비어 있는지 검사한다.
isFull : 큐가 꽉 차있는지 검사한다.

원형 큐 구현 - C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5  // 사용할 실제 데이터 수는 4개 (하나는 빈칸으로 둬야 구분 가능)

typedef struct {
    int items[SIZE];
    int front;
    int rear;
} CircularQueue;

// 초기화
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 큐가 비었는지 확인
int isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

// 큐가 가득 찼는지 확인
int isFull(CircularQueue *q) {
    return (q->rear + 1) % SIZE == q->front;
}

// 삽입 (enqueue)
void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is Full!\n");
        return;
    }
    q->items[q->rear] = value;
    q->rear = (q->rear + 1) % SIZE;
    printf("Enqueued: %d\n", value);
}

// 제거 (dequeue)
int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty!\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front = (q->front + 1) % SIZE;
    printf("Dequeued: %d\n", value);
    return value;
}

// 상태 출력
void display(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty!\n");
        return;
    }

    printf("Queue: ");
    int i = q->front;
    while (i != q->rear) {
        printf("%d ", q->items[i]);
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

// 직접 구현
int main() {
    
}

덱 (Deque)

덱이란? 일반 큐, 원형 큐의 확장된 자료 구조다.

이전에 봤던 큐는 fornt에서만 데이터를 삽입 삭제 할 수 있었는데 덱(deque)에서는 뒤에서 삽입, 삭제가 가능하다.

Deque : 비어 있는 새로운 덱을 생성
isEmpty : 덱이 비어있으면 True를 아니면 False 반환
addFront : 덱의 맨 앞에 추가
deleteFront : 맨 앞의 항목을 꺼내서 반환
getFront : 맨 앞의 항목을 꺼내지 않고 반환
addRear : 덱의 맨 뒤에 추가
deleteRear : 맨 뒤의 항목을 꺼내서 반환
getRear : 맨 뒤의 항목을 꺼내지 않고 반환
isFull : 덱이 가득 차 있으면 True를 아니면 False 반환
size : 덱의 모든 항목들의 개수 반환
clear : 덱을 공백상태로 만듬

덱 구현 - C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 5  // 덱의 최대 크기 +1 (공간 하나는 비워둬야 full/empty 구분 가능)

typedef struct {
    int items[SIZE];
    int front;  // 실제 front는 (front + 1) % SIZE
    int rear;   // 실제 rear는 rear % SIZE
} Deque;

// 덱 초기화
void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

// 덱이 비었는지
bool isEmpty(Deque *dq) {
    return dq->front == dq->rear;
}

// 덱이 가득 찼는지
bool isFull(Deque *dq) {
    return (dq->rear + 1) % SIZE == dq->front;
}

// 덱의 크기
int size(Deque *dq) {
    return (dq->rear - dq->front + SIZE) % SIZE;
}

// 덱 비우기
void clear(Deque *dq) {
    dq->front = dq->rear = 0;
}

// 앞에 삽입
void addFront(Deque *dq, int value) {
    if (isFull(dq)) {
        printf("Deque is Full!\n");
        return;
    }
    dq->front = (dq->front - 1 + SIZE) % SIZE;
    dq->items[dq->front] = value;
    printf("addFront: %d\n", value);
}

// 뒤에 삽입
void addRear(Deque *dq, int value) {
    if (isFull(dq)) {
        printf("Deque is Full!\n");
        return;
    }
    dq->items[dq->rear] = value;
    dq->rear = (dq->rear + 1) % SIZE;
    printf("addRear: %d\n", value);
}

// 앞에서 삭제
int deleteFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is Empty!\n");
        return -1;
    }
    int value = dq->items[dq->front];
    dq->front = (dq->front + 1) % SIZE;
    printf("deleteFront: %d\n", value);
    return value;
}

// 뒤에서 삭제
int deleteRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is Empty!\n");
        return -1;
    }
    dq->rear = (dq->rear - 1 + SIZE) % SIZE;
    int value = dq->items[dq->rear];
    printf("deleteRear: %d\n", value);
    return value;
}

// 앞 항목 반환 (삭제 X)
int getFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is Empty!\n");
        return -1;
    }
    return dq->items[dq->front];
}

// 뒤 항목 반환 (삭제 X)
int getRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is Empty!\n");
        return -1;
    }
    return dq->items[(dq->rear - 1 + SIZE) % SIZE];
}

// 덱 출력
void display(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is Empty!\n");
        return;
    }

    printf("Deque: ");
    int i = dq->front;
    while (i != dq->rear) {
        printf("%d ", dq->items[i]);
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

// 직접 구현
int main() {
    
}

@Super_E끌림

SoC:) SoC:)

이전 포스트

Data Structure - 1

다음 포스트

Data Structure - 2

스택 (Stack)

큐 (Queue)

덱 (Deque)

Data Structure - 1

Data Structure - 3

0개의 댓글