04. 스택과 큐

1-1 스택이란?

 

스택 (stack) 

• 데이터를 일시적으로 저장하기 위한 자료구조 
• 후입선출 구조(LIFO Last In First Out, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.) > 호출한 함수의 역순으로 쌓여있다.
• C언어에서 함수를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다. 
• 푸시 push : 스택에 데이터를 넣는 작업
• 팝 pop : 스택에서 데이터를 꺼내는 작업 
• 푸시, 팝을 하는 위치 : 꼭대기 (top)
• 스택의 가장 밑부분 : 바닥 (bottom)

 

스택 만들기 > int형 

IntStack 멤버 

1. stk : 스택으로 사용할 배열을 가리키는 포인터로 배열의 메모리 공간 할당은 Initialize 함수로 생성된다.
2. max : 스택의 최종 용량을 나타내며 배열 stk의 요소 개수와 같다. 
3. ptr : 스택에 쌓여 있는 데이터의 개수를 나타내며 스택 포인터라고 한다. 스택이 비어 있으면 ptr 값은 0이 되고, 가득 차 있으면 max와 같다. 가장 먼저 푸시된 바닥의 데이터는 stk[0], 가장 먼저 푸시된 꼭대기 데이터는 stk[ptr-1]이다.

* ptr의 값 : 0 이상 max 이하 

//int형 스택
#ifndef ___IntStack
#define ___IntStack

//스택 구현하는 구조체
typedef struct {
     int max; //스택 용량
     int ptr; //스택 포인터
     int *stk; //스택의 첫 요소에 대한 포인터
} IntStack;

//스택 초기화
int Initialize(IntStack *s int max);

//스택에 데이터 푸시
int Push(IntStack *s, int x);

//스택에 데이터 팝
int Pop(IntStack *s, int *x);

//스택에서 데이터 피크
int Peek(const IntStack *s, int *x);

//스택 비우기
void Clear(IntStack *s);

//스택 최대 용량
int Capacity(const IntStack *s);

//스택의 데이터 개수
int Size(const IntStack *s);

//스택이 비어있는지
int IsEmpty(const IntStack *s);

//스택이 가득 찼는지
int IsFull(const IntStack *s);

//스택에서 검색
int Search(const IntStack *s, int x);

//모든 데이터 출력
void Print(const IntStack *s);

//스택 종료
void Terminate(IntStack *s);
#endif

 

//int 형 스택 
#include<stsdio.h>
#include <stdlib.h>
#include "IntStack.h"

//스택 초기화
int Initialize(IntStack *s, int max) {
     s->ptr = 0;
     if((s->stk = calloc(max, sizeof(int))) == NULL) {
         s->max = 0; //배열 생성 실패
         return -1;
     }
     s->max = max;
     return 0;
}

초기화함수 Initialize

• 스택의 메모리 공간(배열)을 확보하는 등 준비 작업을 수행하는 함수 
• 배열을 위한 메모리 공간을 만들 때는 스택이 비어있어야 한다. 
• 스택 포인터 ptr는 0이며 요소 개수는 max인 배열 stk를 생성한다.
• max로 받은 값을 스택 최대 용량을 나타내는 구조체 멤버 max에 저장한다. 
• 메모리 공간 확보에 실패하면 stk에 다른 함수의 접근을 막기 위해 max 값을 0으로 한다. 

//스택에 데이터 푸시
int Push(IntStack *s, int x) {
     if(s->ptr >= s->max) //스택이 가득 찼을 때
          return -1;
     s->stk[s->ptr++] = x;
     return 0;
}

//스택에서 데이터 팝
int Pop(IntStack *s, int *x) {
     if(s->ptr <= 0) //스택이 비어있음 
         return -1;
     *x = s->stk[--s->ptr];
     return 0;
}

//스택에서 데이터 피크
int Peek(const IntStack *s, int *x) {
     if(s->ptr <= 0) //스택이 비어있음 
         return -1;
     *x = s->stk[s->ptr - 1];
     return 0;
}

//스택 비우기
void Clear(IntStack *s) {
    s->ptr = 0;
}

푸시 함수 Push

• 스택에 데이터를 추가하는 함수 
• 스택이 가득 차서 푸시할 수 없는 경우에는 -1을 반환한다. 
• 스택이 가득 차지 않았다면 데이터(x)를 배열의 요소 stk[ptr]에 저장하고 스택 포인터 ptr을 증가시키고 푸시에 성공하면 0을 반환한다. 

팝 함수 Pop

• 스택의 꼭대기에서 데이터를 제거하는 함수 
• 팝에 성공할 경우 0을 반환하고 스택이 비어 있어 팝을 할 수 없는 경우에는 -1을 반환한다. 
• 팝 과정 : 스택 포인터 ptr 감소 > stk[ptr]에 저장한 값을 포인터 x가 가리키는 변수에 저장 

피크함수 Peek

• 스택 꼭대기의 데이터를 몰래 엿보는 함수 
• 피크에 성공하면 0을 반환하고 스택이 비어 있으면 -1을 반환한다. 
• 데이터의 입출력이 없으므로 스택 포인터는 변화하지 않는다. 
• 피크 과정 : 스택이 비어 있지 않으면 꼭대기 요소 stk[ptr -1]의 값을 포인터 x가 가리키는 변수에 저장한다. 

스택 모든 요소 삭제하는 함수 Clear

• 스택에 쌓여 있는 모든 데이터를 삭제한다.

//스택 용량
int Capacity(const IntStack *s) {
   return s->max;
}

//스택에 쌓여 있는 데이터 수
int Size(const IntStack *s) {
   return s->ptr;
}

//스택이 비어있는지
int IsEmpty(const IntStack *s) {
    return s->ptr <= 0;
}

//스택이 가득 찼는지
int IsFull(const IntStack *s) {
    return s->ptr >= s->max;
}

//스택에서 검색
int Search(const IntStack *s, int x) {
    for(int i=s->ptr-1; i>=0; i--)   //꼭대기 > 바닥으로 선형 검색 
        if(s->stk[i] == x)
           return i;   //검색 성공 
    return -1;         //검색 실패  
} 

//모든 데이터 출력
void Print(const IntStack *s) {
    for(int i=0; i<s->ptr; i++)     //바닥 > 꼭대기로 스캔 
        printf("%d  ", s->stk[i]);
    putchar(  '\n');
}

//스택 종료
void Terminate(IntStack *s) {
   if(s->stk != NULL)
      free(s->stk);      //배열 삭제 
   s->max = s->ptr = 0;
}

용량을 삭제하는 Capacity

• 스택의 용량(멤버 max의 값)을 반환하는 함수 

데이터 개수 확인하는 함수 Size

• 현재 스택에 쌓여있는 데이터의 개수(멤버 ptr의 값)을 반환하는 함수 

스택이 비어 있는지 검사하는 함수 IsEmpty

• 스택이 비어 있는지 검사한다. 
• 스택이 비어 있으면 1, 그렇지 않으면 0을 반환한다. 

스택이 가득 찼는지 검사하는 함수 IsFull

• 스택이 가득 찼는지 검사한다. 
• 스택이 가득 찼으면 1, 그렇지 않으면 0을 반환한다.

임의의 값을 검색하는 함수 Search

• 임의의 값의 데이터가 스택의 어느 위치에 쌓여 있는지 검사한다. 
• 꼭대기에서 바닥으로 선형 검색을 수행한다. > 같은 값이 있을 경우 나중에 들어온 값(인덱스가 큰 값)이 반환된다.
• 검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다. 

모든 데이터를 출력하는 함수 Print

• 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 순서대로 출력한다. 

종료함수 Terminate

• Initialize 함수로 확보한 스택을 해제하고 용량 max와 스택 포인터 ptr의 값을 0으로 한다. 

 

스택을 사용하는 프로그램

//int형 스택 IntStack 사용
#include <stdio.h>
#include "IntStack.h"

int main() {
   IntStack s;
   if(Initialize(&s, 64) == -1) {
      puts("스택 생성 실패");
      return 1;
    }
    
    while(1) {
        int menu, x;
        printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s));
        printf("1) 푸시 2) 팝 3) 피크 4) 출력 0) 종료 : ");
        scanf("%d", &menu);
        
        if(menu == 0) break;
        switch(menu) {
        case 1:
           printf("데이터 : ");
           scanf("%d", &x);
           if(Push(&s, x) == -1)
              puts("\a오류 : 푸시 실패 ");
           break;
           
        case 2:
           if(Pop(&s, &x) == -1)
              puts("\a오류 : 팝 실패 ");
           else
              printf("팝 데이터는 %d입니다.\n", x);
           break;
           
        case 3:
           if(Peek(&s, &x) == -1)
              puts("\a오류 : 피크 실패 ");
           else
              printf("피크 데이터는 %d입니다.\n", x);
           break;
           
        case 4:
           Print(&s);
           break;
       }
    }
    Terminate(&s);
    return 0;
}

 

2-1 큐란?

 

큐

• 가장 먼저 넣은 데이터를 먼저 꺼내는 선입선출 구조 (FIFO Fist In First Out)
• 인큐 (enqueue) : 큐에 데이터를 넣는 작업
• 디큐 (dequeue) : 데이터를 꺼내는 작업
• 프런트 (front) : 데이터를 꺼내는 쪽
• 리어 (rear) : 데이터를 넣는 쪽

 

배열로 큐 만들기

1) 인큐

• 리어의 데이터를 새로 들어온 데이터로 바꾼다. 
• 처리 복잡도 : O(1)

2) 디큐

• 맨 앞의 데이터를 꺼내고 두번째 이후의 요소를 한칸씩 앞으로 옮긴다. 
• 처리 복잡도 : O(n) > 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.

//큐를 관리하는 구조체 
typedef struct {
     int max; //큐 용량
     int num  //현재 데이터 수
     int *que; //큐 첫 요소에 대한 데이터
} ArrayIntQueue;

 

링 버퍼로 큐 만들기

•  링 버퍼 (Ring buffer) : 배열의 처음이 끝과 연결되어 있는 자료구조 
• 프런트 (front) : 맨 처음 요소의 인덱스
• 리어 (rear) : 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정한다.)
• 프런트와 리어 값을 업데이트하며 인큐/디큐를 수행하기 때문에 앞에서 발생한 요소 이동 문제를 해결할 수 있다. 
• 처리 복잡도 : O(1)

 

ex) 7개의 데이터를 저장할 때 

1. que[7], que[9]... q[11], que[0], que[1]에 저장한다. 
2. 프런트 값 : 7, 리어 값 : 2
3. 데이터를 하나 인큐 : que[2]에 저장하고 리어 값 1 증가 > 프런트 : 7, 리어 : 3
4. 데이터 하나 디큐 : que[7]이 값을 빼고 프런트 값 1 증가 > 프런트 : 8, 리어 : 3

//int형 큐 IntQueue(헤더)
#ifndef ___IntQueue
#define ___IntQueue

//큐 구조체
typedef struct {
     int max; //큐 최대 용량
     int num; //현재 요소 개수
     int front; //프런트
     int rear;  //리어
     int *que;  //큐의 맨 앞 요소에 대한 포인터
} IntQueue;

//큐 초기화 
int Initialize(IntQueue *q, int max);

//큐에 데이터 인큐
int Enque(IntQueue *q, int x);

//큐에 데이터 디큐
int Deque(IntQueue *q, int *x);

//큐에서 데이터 피크
int Peek(const IntQueue *q, int *x);

//모든 데이터 삭제
void Clear(IntQueue *q);

//큐 최대 용량
int Capacity(const IntQueue *q);

//큐에 저장된 데이터 개수
int Size(const IntQueue *q);

//큐가 비어 있는지
int IsEmpty(const IntQueue *q);

//큐가 가득 찼는지
int IsFull(const IntQueue *q);

//큐에서 검색
int Search(const IntQueue *q, int x);

//모든 데이터 출력
void Print(const IntQueue *q);

//큐 종료
void Terminate(IntQueue *q);
#endif

큐 구조체 IntQueue : 큐를 관리하는 구조체

1. que : 인큐할 데이터를 저장하기 위한 큐로, 사용할 배열의 첫 번째 요소에 대한 포인터이다.
2. max : 큐의 최대 용량을 저장하는 멤버로, 배열 que에 저장할 수 있는 최대 요소의 개수와 같다.
3. front : 인큐하는 데이터 가운데 가장 첫 번째 요소의 인덱스를 저장하는 멤버
4. rear : 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 멤버 
5. num : 큐에 쌓아 놓은 데이터 수를 나타내는 멤버로 front와 rear의 값이 같은 경우 큐가 비어 있는지, 가득 찼는지 구별할 수 없는 상황을 피하기 위해 필요하다. 큐가 비어있으면 0이고 가득 찼을 경우 max와 값이 같다. 

 

#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"

//큐 초기화
//배열 메모리 공간 확보 등 준비 작업을 하는 함수 
int Initialize(IntQueue *q, int max) {
   //큐 처음 만들 떄는 num, front, rear 모두 0으로 초기화한다. 
   q->num = q->front = q->rear = 0;
   if((q->que = calloc(max, sizeof(int))) == NULL) {
       q->max = 0;  //배열 생성 실패 
       return -1;
   }
   //매개변수 max로 받은 큐의 최대 용량을 max에 저장한다. 
   //저장할 수 있는 요소으 개수가 max인 배열 que의 메모리 공간 확보 
   q->max = max;
   return 0;
}

//큐에 데이터 인큐
//인큐에 성공하면 0을 반환하고 가득 큐가 가득차서 인큐할 수 없으면 (num >= max) -1을 반환한다. 
int Enque(IntQueue *q, int x) {
    if(q->num >= q->max) 
       return -1; //큐가 가득 참
    else {
       q->num++;
       q->que[q->rear++] = x;
       //인큐를 수행한 후 rear와 max 값이 같아지는 경우 실제 배열에는 없는 공간을 가리키게 되므로
       //rear를 배열의 처음인 0으로 변경한다. 
       if(q->rear == q->max) 
          q->rear = 0;
       return 0;
     }
}

//큐에서 데이터 디큐
//디큐에 성공하면 0을, 큐가 비어있어서 디큐할 수 없다면(num <= 0) -1을 반환한다. 
int Deque(IntQueue *q, int *x) {
   if(q->num <= 0)  //큐가 비어 있음
       return -1;
   else {
       q->num--;
       *x = q->que[q->front++];
       //디큐를 하고 front를 증가했는데 만약 max값과 같아진다면 배열 마지막 요소 인덱스를 초과하는 문제가 생긴다.
       //front값이 max와 같아지면 front 값을 배열의 처음인 0으로 변경한다. 
       if(q->front == q->max) 
          q->front = 0;
       return 0;
   }
}

//큐에서 데이터 피크
//que[front] 값을 출력한다. 
//피크에 실패하면 -1, 성공하면 0을 반환한다. 
int Peek(const IntQueue *q, int *x) {
   if(q->num <= 0) //큐가 비어 있음
      return -1;
   *x = q->que[q->front];
    return 0;
}

//모든 데이터 삭제 
void Clear(IntQueue *q) {
   q->num = q->front = q->reat = 0;
}

//큐 최대 용량 반환 
int Capacity(const IntQueue *q) {
   return q->max;
}

//큐에 쌓여 있는 데이터 수 
int Size(const IntQueue *q) {
    return q->num;
}

//큐가 비어 있는지 
//비어있으면 1, 그렇지 않으면 0을 반환한다. 
int IsEmpty(const IntQueue *q) {
   return q->num <= 0;
}

//큐가 가득 찼는지
//가득 찼으면 1, 그렇지 않ㅇ면 0을 반환한다. 
int IsFull(const IntQueue *q) {
    return q->num >= q->max;
}

//큐에서 검색 (선형검색)
//큐 배열에서 x와 같은 데이터가 저장되어 있는 인덱스를 반환하는 함수
//검색에 성공하면 찾은 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다. 
//현재 검색하는 위치의 인덱스를 구하는 식 : (i+q->front) % q->max
int Search(const IntQueue *q, int x) { 
   int i, idx;
   for(i = 0; i < q->num; i++) {
      if(q->que[idx = (i+q->front) % q->max] == x)
          return idx; //검색 성공
   }
   return -1; //검색 실패
}

//모든 데이터 출력
void Print(const IntQueue *q) { 
  int i;
  for(i=0; i<q->num; i++) {
     printf("%d ", q->que[(i+q->front) % q->max);
  putchar('\n');
}

//큐 종료
void Terminate(IntQueue *q) { 
  if(q->que != NULL)
     free(q->que);    //메모리 공간에 할당한 배열 해제 
  q->max = q->num = q->front = q->reat = 0;
}

 

큐 사용하는 프로그램

//int형 큐 IntQueue 사용
#include <stdio.h>
#include "IntQueue.h"

int main() {
   IntQueue que;
   if(Initialize(&que, 64) == -1) {
      puts("큐 생성 실패");
      return 1;
    }
    
    while(1) {
        int m, x;
        printf("현재 데이터 수 : %d / %d\n", Size(&que), Capacity(&que));
        printf("1) 인큐 2) 디큐 3) 피크 4) 출력 0) 종료 : ");
        scanf("%d", &m);
        
        if(m == 0) break;
        switch(menu) {
        case 1:
           printf("데이터 : ");
           scanf("%d", &x);
           if(Enque(&que, x) == -1)
              puts("\a오류 : 인큐 실패 ");
           break;
           
        case 2:
           if(Deque(&que, &x) == -1)
              puts("\a오류 : 디큐 실패 ");
           else
              printf("디큐한 데이터는 %d입니다.\n", x);
           break;
           
        case 3:
           if(Peek(&que, &x) == -1)
              puts("\a오류 : 피크 실패 ");
           else
              printf("피크한 데이터는 %d입니다.\n", x);
           break;
           
        case 4:
           Print(&que);
           break;
       }
    }
    Terminate(&que);
    return 0;
}

 

* 링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다. 

• ex) 요소 개수가 n이고 배열에 계속해서 데이터가 입력될 때, 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용한다. 
• 정수 입력(인큐)은 무한히 할 수 있지만 배열에 저장되는 데이터는 가장 최근데 입력한 10개의 데이터만 링 버퍼에 남아있다.

//원하는 개수만큼 데이터 입력하고 요소 개수가 n인 배열에는 최근에 입력한 n개만 저장하는 프로그램
#include <stdio.h>

define N 10 //저장하는 데이터 개수

int main() { 
    int i;
    int a[N]; //입력한 데이터 저장
    int cnt = 0;  //입력한 데이터 개수
    int retry; 
    puts("정수를 입력하세요 ");
    do {
       printf("%d번째 정수 : ", cnt + 1);
       scanf("%d", &a[cnt++ % N]);
       printf("계속할까요? (Yes ---1 / No ---0) : ");
       scanf("%d", &retyr);
    } while(retry == 1);
    i = cnt - N;
    if(i < 0) i = 0;
    for(; i < cnt; i++) 
       printf("%2d번째 정수 = %d\n", i + 1, a[i%N]);
       
    return 0;
}

• 입력한 값을 저장하는 위치의 인덱스 : cnt ++ % N > 나머지 연산자 사용 
• 프로그램에 임의의 값을 입력하면 입력된 값이 링 버퍼(배열)에 순환하며 저장된다. 
• 만약 입력한 값의 개수가 10 이하라면 a[0] ~ a[cnt-1] 순서대로 출력해도 된다. (출력할 값 : cnt개)
• 하지만 만약 10 이상이라면 a[2], a[3] ...a[9], a[0], a[1] 순서대로 출력해야 한다.