Stack/Queue - 스택과 큐, 스택의 종류

스택과 큐는 선형자료구조(Linear List)이다.

 

 

스택은 LIFO(Last In First Out)구조로 동작한다.

먼저 들어 온게 쌓이고 나중에 들어온게 위로가서 

나중에 데이터를 뽑을 때, 나중에 들어온 데이터가 먼저 나가는 형식으로

접시나 책을 쌓는다고 생각하면 이해하기 쉽다.

 

예시로는 아래와 같다.

 

C언어로 구현할 때,

스택의 종류에는 4가지가 있음을 고려해 볼 수 있다. 

 

종류를 나누는 기준은 2 가지가 있다.

1. SP(stack pointer)의 위치 - Data의 앞에 위치하느냐 (FULL), 빈 공간에 위치하느냐(Empty)

2. SP의 조작 - SP를 감소시키느냐 (Descending), 증가시키느냐 (Ascending)

이에 따라 스택은 FD stack, ED stack, FA stack, EA stack으로 나뉜다.

 

예를 들어 FD Stack을 C언어로 구현하면 다음과 같다.

#include <stdio.h>
 
#define MAX_STACK       10
#define STACK_EMPTY MAX_STACK
#define STACK_FULL      0
 
int a[MAX_STACK+1] = {1,2,3,4,5,6,7,8,9,10,11};
int Stack[MAX_STACK];
int Sptr = STACK_EMPTY;
 
 
int Print_Stack(void)
{
    int i;
 
    for(i = Sptr; i < MAX_STACK; i++)
    {
        printf("STACK[%d] = %d\n", i, Stack[i]);
    }
 
    return MAX_STACK - Sptr;
}
 
int Is_Full(void)
{
    return STACK_EMPTY - Sptr;
}
 
int Is_Empty(void)
{
    return Sptr - STACK_FULL;
}
 
int Push_Stack(int data)
{
    if (Sptr == STACK_FULL) return -1;
    Stack[--Sptr] = data;
    return 1;
}
 
int Pop_Stack(int *p)
{
    if (Sptr == STACK_EMPTY) return -1;
    *p = Stack[Sptr++];
    return 1;
}

 

 

큐는 FIFO(First In First Out)구조로 동작한다.

놀이공원에서 줄 서기와 같다고 보면된다.

먼저 서있는 사람이 먼저 놀이기구를 타는 것처럼.

 

데이터가 오고가는 예시를 보면 아래와 같다.

 

C언어로 구현하는 경우 쓰기 포인터와 읽기 포인터를 이용해서 동작하는데,

두 포인터의 위치가 같은 경우 비어있다고 생각한다.

 

 

큐 중에서 front와 back이 특별히 나누어지지 않고 합쳐져있는

원형큐를 생각해 볼 수도 있는데 이에 관한 C언어 코드는 다음과 같다.

#include <stdio.h>
 
#define MAX_Q       8
#define Q_MIN       0
#define Q_MAX       MAX_Q
 
int In_Queue(int data);
int Out_Queue(int *p);
int Print_Queue(void);
int Count_Full_Data_Queue(void);
int Count_Empty_Data_Queue(void);
 
int a[MAX_Q+1] = {1,2,3,4,5,6,7,8,9};
int Queue[MAX_Q];
int Wrptr = Q_MIN;
int Rdptr = Q_MIN;
 
int Print_Queue(void)
{
    int i;
    int rd = Rdptr;
    int n = Count_Full_Data_Queue();
 
    for(i=0; i<n; i++)
    {
        printf("Queue[%d] = %d\n", rd, Queue[rd++]);
        rd %= MAX_Q;
    }
 
    return n; 
}
 
int Is_Full(void)
{
    if(Rdptr > Wrptr) return MAX_Q - (Rdptr - Wrptr);
    return Wrptr - Rdptr;
}
 
int Is_Empty(void)
{
    return MAX_Q - Count_Full_Data_Queue() - 1;
}

int In_Queue(int data)
{
    if ((Wrptr + 1) % MAX_Q == Rdptr) return -1;
    Queue[Wrptr] = data;
    Wrptr = (Wrptr + 1) % MAX_Q;
    return 1;
}
 
int Out_Queue(int *p)
{
    if (Wrptr == Rdptr) return -1;
    *p = Queue[Rdptr];
    Rdptr = (Rdptr + 1) % MAX_Q;
    return 1;
}