큐와 스택

알고리즘을 짤 때 많이 쓰이는 큐와 스택

스택은 의미처럼 박스에 차곡차곡 쌓는다고 생각하면 된다. 열려있는 구멍은 위 뿐이라 뺄 때도 제일 나중에 들어간 값이 나오게 된다.

즉 LIFO(Last In First Out)

보통 맨 위의 위치를 TOP으로 설정하고, 꺼내는 함수를 Pop, 넣는 함수를 Push로 한다.

int stack[n];
int TOP = 0;

void Push(int data){
    if(TOP==n){
        printf("Stack is Full\n");
    }
    else{
        stack[TOP++] = data;
    }
}

int Pop(){
    if(TOP){ 
        printf("Stack is Empty\n");
        return -1;
    }
    else{
        return stack[--TOP];
    }
}

큐는 구멍이 위와 아래 두 곳이고, 넣는 곳은 위, 빼는 곳은 아래이다. 그래서 먼저 넣는 순서대로 밑에 저장되고, 가장 먼저 넣은 것이 가장 먼저 나오게 되는 구조이다. 즉 FIFO(First In First Out)

보통 아래쪽을 Front(Head), 위쪽을 Rear(Tail)로 설정하고 꺼내는 함수를 Dequeue, 넣는 함수를 Enqueue로 한다.

int queue[n];
int front = 0;
int rear = 0;

void enqueue(int data){
    if ((rear +1) % n == front){
        printf("Queue is Full\n");
    }
    else {
        queue[rear] = data;
        rear = (rear +1 ) % n;
    }
}

int dequeue(){
    int data;
    if (front == rear){
        printf("Queue is Empty\n");
        return -1;
    }
    else {
        data = queue[front];
        front = (front + 1) % n;
        return data;
    }
}

큐는 배열의 앞 값을 빼고, 뒤에 값을 추가 하기 때문에 rear 값이 배열의 크기인 n을 넘어 갈 수 있다. 따라서 % n 을 통해 배열의 앞과 뒤를 연결하는 선형 큐를 통상적으로 알고리즘에 사용한다.