[자료구조] 스택(Stack)과 큐(Queue)

<스택이란?>

  스택(Stack)이란 쌓아올린다는 의미다.

  따라서 스택 자료구조라는 것은 접시를 쌓듯이, 자료를 차곡차곡 쌓아올린 형태의 구조를 말한다.

<스택의 구조>

  흔히 스택을 FILO라고 한다. First In, Last Out이기 때문이다.

  먼저 들어간 데이터가, 가장 늦게 나오는 것이 스택의 특징이다.

  ■ top : 현재 메모리의 위치와 데이터의 overflow · underflow 파악

  ■ Pop() : top을 통한 데이터의 삭제를 말함

  ■ Push() : top을 통한 데이터의 삽입를 말함

  

  Pop이든 Push든 top이든, 이름은 관용적인 약속이다.

  꼭 정해져있는 것은 아니지만, 이 규칙에 따라 프로그램을 작성하는 것이 좋다.

<스택의 기본예제>

  #include<stdio.h>
  #include<stdlib.h> // system("cls"); 화면 청소를 위한 헤더파일
  #include<conio.h> // getch(); 를 위한 헤더파일
  void init_stack(void); // top의 초기 값을 설정한다  void print_stack(void); // stack을 출력할 때 사용된다

  int top; // overflow와 underflow를 판단하는 기준이 된다  int push(int t); // 데이터를 입력한다, 혹은 쌓는다  int pop(void); // 데이터를 삭제한다, 혹은 꺼낸다

  #define MAX 5 // 메모리는 최대 5개로 제한  int stack[MAX];

  void main()
  {
    int i,t;
    init_stack();
    printf("Input Data : %d개\n",MAX);
    for(i=0;i<MAX;i++) // 예제를 위해 만든 소스라, 메인 부분은 다소 억지스런 부분이 있다
    {
      scanf("%d",&t);
      push(t);
    }
    getch(); // 어느 문자든 입력받을 때까지 대기한다. 입력 데이터 확인을 위해 한번 넣어주었다
    print_stack();
  } 

  void init_stack(void)
  {
    top = -1;
  }

  int push(int t)
  {
    if(top>=MAX-1) // 4를 넘게되면 overflow이므로, 입력할 때 조건검사를 하게 된다
    {
      printf("stack overflow\n");
      return -1;
    }
    stack[++top] = t;
    return t;
  }

  int pop(void)
  {
    if(top<0) // 0보다 작게되면 underlfow이므로, 역시 조건검사를 실행한다
    {
      printf("stack underflow\n");
      return -1;
    }
    return stack[top--];
  }

  void print_stack(void)
  {
    int i;
    system("cls");
    printf("stack contents:top->bottom\n");
    if(top==-1)
      printf("[stack empty]\n");
    for(i=top;i>=0;i--)
    {
      printf("%d",stack[i]);
    }
    printf("\n");
  }

<큐란 무엇인가?>

  큐(Queue)란 입구와 출구가 다른 자료구조로서, 선입선출(First In, First Out)이라 하여 FIFO라고도 불린다.

  말 그대로 먼저 온 사람이, 먼저 일을 마치고 나가는 것이다.

<큐의 구조>

  ■ front : 맨 앞을 나타내는 위치

  ■ rear : 맨 뒤를 나타내는 위치

  ■ enQueue : rear에서 이루어지는 삽입 연산을 나타냄

  ■ deQueue : front에서 이루어지는 삭제 연산을 나타냄

  

  스택과 큐에서의 연산을 비교하자면 이렇다.

<큐의 기본예제>

  #include <stdio.h>
  #include <stdlib.h>
  #include <conio.h>

  #define MAX 10

  const int front = -1; // front는 변하지 않는 값이므로, const로 값을 고정시켜 놓았다
  int rear;
  int queue[MAX];

  void init() // 초기 설정 부분, 위에서 초기화하지 않고 분리한 이유는 언제든 이 함수를 통해 초기화가 진행되도록 하기 위해서다
  {
    rear = -1;
  }

  void enQueue()
  {
    if(rear==9) // 최대 값을 넘기면, 조건 검사를 통해 Overflow를 출력해준다
    {
      printf("\nQueue is Overflow, You can't Input Data");
      getch();
    }
    else // 그렇지 않다면, 데이터를 입력한다
    {
      printf("\nInput Data : ");
      scanf("%d",&queue[++rear]);
    }
  }

  void deQueue()
  {
    if(rear==front) // rear와 front가 같아지면, 데이터가 없는 것이므로 조건 검사를 실행
    {
      printf("\nData Empty, Please Input Data");
      getch();
    }
    else // 아니면 rear의 위치를 감소시킨다
    {
      --rear;
    }
  }

  void print() // 출력부분, 원래는 따로 있으나, 원활한 확인을 위해 입력과 삭제 부분에도 출력이 되도록 하였다
  {
    int i;
    system("cls");
    for(i=front+1 ; i<=rear ; i++)
    {
      printf("%d\t",queue[i]);
    }
    printf("\n\nrear : %d\n",rear);
    printf("front : %d",front);
  }

  void main()
  {
    int sel;
    init();
    while(1)
    {
      printf("\n\n1.put  2.get  3.print \n\n");
      printf("Select Number : ");
      scanf("%d",&sel);
      switch(sel)
      {
        case 1:
          enQueue(); system("cls"); print(); break; // 원래는 print()가 없는 것이나
        case 2:
          deQueue(); system("cls"); print(); break; // 예제의 확인을 위해 넣어놓았다
        case 3:
          print(); break;
        default:
          system("cls");

          printf("Fail Your Number");
      }
    }
  }