큐, 스택 직접 구현

<Dynamic Stack 구현>

스택은 -1로 초기화

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
 
typedef struct {
    int* data;
    int capacity;
    int top;
} StackType;
 
void init_stack(StackType* s)
{
    // -1로 초기화
    s->top = -1;
    s->capacity = 1;
    s->data = (int*)malloc(s->capacity * sizeof(int));
}
 
int is_empty(StackType* s)
{
    return (s->top == -1);
}
 
int is_full(StackType* s)
{
    return (s->top == (s->capacity - 1));
}
void push(StackType* s, int item)
{
    if (is_full(s)) {
        s->capacity *= 2;
        s->data =
            (int*)realloc(s->data, s->capacity * sizeof(int));
    }
    s->data[++(s->top)] = item;
}
 
int pop(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "Stack is Empty\n");
        exit(1);
    }
    // s->top 값 주고 --
    else return s->data[(s->top)--];
}

 

스택 배열 구현

 

 

큐는 front, rear 0으로 초기화

큐 배열 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int Queue[2000004];
int Front, Rear;
 
void push(int x) {
    Queue[Rear++] = x;
}
 
int pop() {
    if (Rear - Front  >= 1)
        return Queue[Front++];
    else
        return -1;
}
 
int back() {
    if (Rear - Front >= 1)
        return Queue[Rear - 1];
    else
        return -1;
}
 
int front() {
    if (Rear - Front >= 1)
        return Queue[Front];
    else
        return -1;
}
 
int size() {
    return Rear - Front;
}
 
int empty() {
    if (Rear - Front <= 0)
        return 1;
    else
        return 0;
}

 

 

<deque 직접 구현>

q->front = q->rear = 0; 로 init

add_rear는

q->rear = (q->rear + 1) % MAX_QUEUE_SIZE

q->data[q->rear] = v;

 

add_front는

q->data[q->front] = v;

q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
int MAX_QUEUE_SIZE;
 
typedef struct {
    int* data;
    int  front, rear;
} DequeType;
 
 
void init_deque(DequeType* q)
{
    q->data = (int*)malloc(MAX_QUEUE_SIZE * sizeof(int));
    // front, rear 0으로 설정
    q->front = q->rear = 0;
}
 
int is_empty(DequeType* q)
{
    // front, rear 같으면 is_empty
    return (q->front == q->rear);
}
 
int is_full(DequeType* q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
 
void add_rear(DequeType* q, int item)
{
    // rear 한 칸 뒤로 보내고 넣는다
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}
 
int delete_front(DequeType* q)
{
    // front 한 칸 뒤로 보내고 출력
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}
 
int get_front(DequeType* q)
{
    // front에는 값이 없다 front + 1에 값이 있다
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
 
void add_front(DequeType* q, int val)
{
    // front에 넣고 한 칸 앞으로 보낸다
    q->data[q->front] = val;
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
 
int delete_rear(DequeType* q)
{
    int prev = q->rear;
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}
 
int get_rear(DequeType* q)
{
    return q->data[q->rear];
}
 
int get_size(DequeType* q)
{
    // 덱의 크기 계산 (rear와 front의 차이로 계산)
    return (q->rear - q->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}