c언어로 stack, queue 구현

c언어에는 c++처럼 <stack>, <queue> STL이 없어서 직접 배열이나 리스트를 통해 구현해야한다.

1. stack 구현 

1) 배열

#include <stdio.h>
using namespace std;
#define MAX 100
 
int stack[MAX];
int top = -1;
 
//스택이 가득 찼는지 확인하는 함수
bool IsFull() {
    if (top >= MAX - 1) return true;
    return false;
}
//스택이 비어있는지 확인하는 함수
bool IsEmpty() {
    if (top < 0) return true;
    return false;
}
//스택의 top 원소를 가져옴
int pop() {
    if (IsEmpty()) return -999;
    return stack[top--];
}
//스택에 원소를 넣음
bool push(int a) {
    if (IsFull()) return false;
    stack[++top] = a;
}
//스택의 size 반환
int Size(){
    return top + 1;
}
 
int main() {
 
    push(1);
    push(2);
    push(3);
    printf("%d\n", Size());
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop()); 
 
    //출력결과
    //3
    //3 2 1
 
    return 0;
}

2) 연결리스트

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
 
typedef struct Node {
    int data;
    Node *next;
} Node;
 
typedef struct Stack
{
    Node *top;
}Stack;
void InitStack(Stack *st) {
    st->top = NULL;
}
bool IsEmpty(Stack *st) {
    if (st->top == NULL) return true;
    return false;
}
void push(Stack *st, int a) {
    Node *now = (Node*)malloc(sizeof(Node));
    now->data = a;
    now->next = st->top;//next 링크를 현재 top으로 설정
    st->top = now;
}
int pop(Stack *st) {
    if (IsEmpty(st)) return -999;
    Node *now;
    int re = 0;
    now = st->top;
 
    st->top = now->next;
    re = now->data;
 
    free(now);
 
    return re;
}
 
int main() {
 
    Stack st;
 
    InitStack(&st);
    push(st,1);
    push(st,2);
 
    printf("%d ", pop(&st));
    printf("%d ", pop(&st));
 
    return 0;
}

2. queue 구현 

1) 배열: 큐를 효율적으로 사용하기 위해 환형으로 만든다.

#include <stdio.h>
using namespace std;
#define MAX 100
 
int queue[MAX]; //원형큐라고 생각해서, 배열을 효율적으로 관리한다.
int front = 0, rear = 0; 
int s = 0;
//rear이 하나의 공간 차지. 왜? 모든 공간에 데이터를 삽입하면, 포화상태인지
//비어있는 상태인지 구분이 불가능하기때문이다
//따라서 queue에 넣을 수 있는 원소 수는 MAX개가 아니라 MAX-1개이다.
 
 
//큐가 가득 찼는지 확인하는 함수
bool IsFull() {
    if ((rear + 1) % MAX == front) return true;
    return false;
}
//큐가 비어있는지 확인하는 함수
bool IsEmpty() {
    if (front == rear) return true;
    return false;
}
//큐의 원소를 가져옴(맨처음 넣었던)
int Dequeue() {
    if (IsEmpty()) return -999;
 
    front = (front + 1) % MAX;
    s--;
 
    return queue[front];
}
//큐에 원소를 넣음(맨마지막에)
bool Enqueue(int a) {
    if (IsFull()) return false;
    
    rear = (rear + 1) % MAX;
    queue[rear] = a;
 
    s++;
 
    return true;
}
//큐의 사이즈를 return
int Size() {
    return s;
}
 
int main() {
 
    Enqueue(1);
    Enqueue(2);
    Enqueue(3);
    printf("%d", Dequeue());
    printf("%d", Dequeue());
    printf("%d", Dequeue());
 
    /* print queue 방법
    for(int i = front; i != rear; ++i % MAX){
        printf("%d ", queue[i]);
    }
    */
    return 0;
}

2) 연결리스트

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
 
typedef struct Node {
    int data;
    Node *next;
} Node;
 
typedef struct Queue {
    Node *rear;
    Node *front;
    int count;
} Queue;
 
void InitQueue(Queue *qu){
    qu->rear = NULL;
    qu->front = NULL;
    qu->count = 0;
}
bool IsEmpty(Queue *qu) {
    if (qu->front == NULL) return true;
    return false;
}
void Enqueue(Queue *qu, int a) {
    Node *now = (Node *)malloc(sizeof(Node));
    now->data = a;
    now->next = NULL;
 
    if (IsEmpty(qu)) {
        qu->front = now;
    }
    else {
        qu->rear->next = now;
    }
    qu->rear = now;
    qu->count++;
}
 
int Dequeue(Queue *qu) {
    if (IsEmpty(qu)) return -999;
    Node *now;
    int re = 0;
    
    now = qu->front;
    re = now->data;
    qu->front = now->next;
    
    free(now);
    qu->count--;
 
    return re;
}
 
int main() {
    Queue queue;
 
    InitQueue(&queue);
    Enqueue(&queue, 1);
    Enqueue(&queue, 2);
    printf("%d ", Dequeue(&queue));
    printf("%d ", Dequeue(&queue));
 
    return 0;
}