<img src="http://blogimgs.naver.com/nblog/ico_scrap01.gif" class="i_scrap" width="50" height="15" alt="본문스크랩" /> (데이터구조) 스택과 큐

       스택(Stack)

   • 삽입과 삭제가 한쪽 끝에서만 발생하는 선형 리스트

   • top(stack pointer) 포인터 : 자료의 삽입과 삭제가 발행하는 부분

      → top 포인터는 항상 제일 위에 있는 자료를 가리킴

   • BOTTOM(밑바닥) 포인터 : 막혀있는 다른 한쪽 끝

   • PUSH :자료를 삽입하는 연산, POP : 자료를 삭제하는 연산,  

       TOP 연산 : 현재top 포인터가 가리키는 자료의 내용을 조사하는 연산

   • 자료의 삽입: top 포인터가 가리키는 위치보다 1이 증가한 위치에

             →  top = top + 1

   • 자료의 삭제: top 포인터가 가리키는 위치의 자료가

             →    top = top - 1

   •  top의 초기치는 -1이다

 

스택의 구조

  • 입출력 정책(policy): 후입 선출 방식인 LIFO(Last In First Out) 구조

  • 예 - 동전통(택시)

  • 스택을 사용하는 분야: ① 산술 연산  ②서브루틴의 복귀 주소를 저장

                           ③ 인터럽트 처리시 복귀 주소를 저장

  자료의 삽입

  • top 포인터를 1만큼 증가시킨 후 → top이 가리키는 위치(top+1)에 자료 삽입 

  • 삽입 알고리즘

void PUSH (stack, n, top, item)

{

/* 크기가 n인 STACK에 item을 삽입하는 알고리즘

STACK : 최대 크기가 n인 배열

n : 스택의 크기

top : 스택 포인터로 스택이 선언될 때는 초기치가 -1이다. */

   if(top >= (n-1)) then /* top 포인터가 (n-1)과 같거나 크면 */

        {

          printf("stack overflow"); /* 여분의 기억 장소 없음 */

          exit(0); /* 종료 */

        }

        else              

        {

          top++; /* top 포인터 1 증가시킴 */

          STACK[top] = item ; /* top 포인터가 가리키는 곳에 자료 삽입 */

        }

}

  

• 예) 삽입순서 : C, D, E, F (단, 스택의 크기는 3이다.)

   자료의 삭제

  • 현재 top 포인터가 가리키는 위치의 자료를 삭제 → top 포인터를 1만큼 감소시킴

  • 삭제 알고리즘

char POP( )

{

/* 크기가 n인 STACK에서 자료를 삭제하는 알고리즘

item : 삭제된 자료를 저장할 변수

top : 스택 포인터 */

char item;

   if(top < 0) then /*top 포인터가 0보다 작으면 */

           {

          printf("stack underflow"); /* 스택이 비었음 */

          exit(0); /* 종료 */

           }

           else

           {

           item = STACK[top];  /* top 포인터가 가리키는 곳의 자료를 삭제하여 item에 저장한다.*/

           top--; /* top 포인터 1 감소시킴 */

           }

}

• 예) 스택에서 자료를 모두 제거(단, 스택의 크기는 3이다.)

  스택의 TOP 내용 조사

   •  TOP 연산은 현재 스택에서 제일 위에 있는 자료를 알려준다.

char TOP( )

{

/* 현재 스택의 제일 위에 있는 자료를 반환하는 알고리즘

STACK : 크기가 n인 배열

top : 스택 포인터 */

if(top < 0) then /* top 포인터가 0보다 작으면 */

           {

          printf("stack empty"); /* 스택이 비었음 */

          exit(0); /* 종료 */

          }

          else

           return(STACK[top]); /* top 포인터가 가리키는 곳의 자료를 되돌려 준다*/

}

  큐(Queue)

   •  한 쪽 끝에서는 자료가 삽입되고 다른 한 쪽 끝에서는 자료가 삭제되는  선형 리스트이다.

   • rear(tail) 포인터 : 삽입이 발생하는 부분

                          제일 마지막에 있는 자료를 가리킴

   • front(head) 포인터 : 삭제가 발생하는 부분

                           제일 앞에 있는 자료 보다 1작은 위치를 가리킴

   • 연산자 : 특별한 연산자 없음

   • 삽입 : rear 포인터가 가리키는 위치보다 1증가한 위치(rear+1)에 

   • 삭제 : front 포인터가 가리키는 위치보다 1증가한 위치(front+1)에

   • front와 rear의 초기치는 -1이다.

큐의 구조

 

• 입출력 정책(policy): 선입 선출 방식인 FIFO(First In First Out) 구조

• 사용하는 분야 : 운영체제에서 수행할 작업들을 스케쥴링(scheduling)할 때

 

   자료의 삽입

   • rear 포인터를 1만큼 증가시킨 후 → rear가 가리키는 곳(rear+1)에 자료를 삽입

   • 삽입 알고리즘

void insert_queue(item)

{

/* 크기가 n인 Queue에 item을 삽입하는 알고리즘

Queue : 최대 크기가 n인 배열

n : 큐의 크기

rear : 큐에 마지막으로 삽입된 원소의 위치를 가리킨다.

item : 큐에 삽입할 자료 */

   if(rear==(n-1)) then

          {

           printf("Queue full"); /* 여분의 기억 장소 없음 */

          exit(0); /* 종료 */

          }

           else

          {

      rear++; /* rear 포인터 1 증가시킴 */

      Queue[rear] = item; /* rear 포인터가 가리키는 곳에 자료 삽입 */

   }

}

• 예) 삽입순서 : C, D, E, F (단, 큐의 크기는 3이다.)

   자료의 삭제

   • 현재 front 포인터에 1증가시킨 위치에 있는 자료를 삭제

   • 먼저 front 포인터를 1증가시킨 후 →  front 포인터가 가리키는 자료를  삭제

   • 삭제 알고리즘

void delete_queue( )

{

/* 크기가 n인 Queue에서 item을 삭제하는 알고리즘

Queue : 최대 크기가 n인 배열

n : 큐의 크기

front : 큐에서 자료를 삭제할 위치보다 1작은 위치를 지정한다.

item : 큐에서 자료를 삭제하여 저장할 변수 */

   if(front==rear) then

           {

           printf("Queue empty");

           exit(0); /* 종료 */

           }

           else

           {

           front++; /* front 포인터 1 증가시킴 */

           item = Queue[front]; /* front 포인터가 가리키는 곳의 자료를  삭제하여 item에 저장한다. */

}

   • 예) 큐에서 자료를 모두 제거

원형 큐(Circular Queue)

   • 큐를 원형으로 표현한 것

   • 큐의 첫 번째 원소와 마지막 원소가 서로 연결되어 있는 형태

                  → Cqueue[n-1]의 다음 요소는 Cqueue[0]이다

                  → 삽입이나 삭제되는 원형 큐의 위치를 찾기 위해서는

                      %(나머지) 연산자를 사용

   • 큐에 새로운 자료를 추가할 때 rear 포인터가 큐의 끝을 가리킨다 해도  큐가 자료들로 모두 차 있는 게 아니므로

   • 큐의 뒷 자료들을 큐의 앞 빈 공간으로 이동시키는 낭비를 해결하는 방법으로 고안된  큐

        

원형 큐의 구조

  • rear 포인터 : 삽입이 발생하는 부분을 가리킴

                    제일 앞에 있는 자료보다 반 시계 방향으로 1 작은 위치를 가리킴

   • front 포인터 : 삭제가 발생하는 부분을 가리킴

                     제일 마지막에 있는 자료를 가리킴

   • 자료의 삽입 : rear 포인터가 가리키는 위치보다 1증가한 위치((rear+1)  % n)에서 이루어짐

   • 자료의 삭제 : front 포인터가 가리키는 위치보다 1증가한 위치

                      ((front+1) % n)에서 이루어짐

   • front와 rear의 초기치 : 0

  

   자료의 삽입

   • rear 포인터를 1만큼 증가시킨 후 rear가 가리키는 위치((rear+1) % n)에 자료를 삽입하면 된다.

   • 삽입 알고리즘

void insert_cqueue(item)

{

/* 크기가 n인 원형 큐에 item을 삽입하는 알고리즘

Cqueue : 최대 크기가 n인 배열

n : 원형 큐의 크기

rear : 원형 큐에 마지막으로 삽입된 원소를 가리킨다.

item : 원형 큐에 삽입할 자료 */

   char item;

   rear = (rear+1) % n; /* 삽입될 위치 계산 */

   if(front==rear) then

           {

           printf("circular queue full"); /* 여분의 공간 없음 */

           exit(0);

           }

           else

           Cqueue[rear] = item; /* rear 포인터가 가리키는 곳에 자료 삽입 */  

 }

 

  자료의 삭제

  • front 포인터를 1만큼 증가시킨 후 front가 가리키는 위치

     ((front+1) % n)에 있는 자료를 삭제

  • 삭제 알고리즘

void delete_cqueue( )

{

/* 크기가 n인 원형 큐에서 자료를 삭제하는 알고리즘

Cqueue : 최대 크기가 n인 배열

n : 원형 큐의 크기

front : 원형 큐에서 제일 앞에 있는 자료보다 반시계 방향으로 1작은 위치를  가리킨다.

item : 원형 큐에서 삭제할 자료를 저장할 변수 */

   char item;

   if(front==rear) then

           {

           printf("circular queue empty"); /* 원형 큐가 비었음 */

           exit(0);

           }

           else

           {

           front = (front+1) % n; /* 삽입될 위치 계산 */

           item = Cqueue[front]; /* front 포인터가 가리키는 곳의 자료를  삭제하여 item에 저장한다. */

           }

}

  데크(Deque)

• 양쪽 끝에서 추가와 삭제가 가능한 선형 리스트

• 스택과 큐를 하나의 선형 리스트 구조로 혼합시킨 형태

• 두 개의 스택의 bottom 부분을 서로 연결시켜 큐 모양이 되게 했음

• L-bottom 포인터 : 왼쪽 끝에서 삽입과 삭제가 일어날 위치를 가리킴

• R-bottom 포인터 : 오른쪽 끝에서 삽입과 삭제가 일어날 위치를 가리킴

데크의 구조

  • 데크의 입출력에 제한을 두어 다음 2개의 데크가 있음

      ① 입력 제한 데크 : 입력을 한쪽 끝에서만 가능하게 한 데크로스크롤(SCROLL)이라 한다.

      ② 출력 제한 데크 : 출력을 한쪽 끝에서만 가능하게 한 데크로쉘프(SHELF)라고 한다.

데크의 종류

  다중 스택과 큐

 다중(Multi) 스택

   

   • 크기가 n인 스택을 하나의 스택 크기가 n/m인 m개의 다중 스택으로 구현

   • 스택 하나 하나의 크기를 예상할 수 없으므로 동일한 크기로 분배한다.

   • top와 bottom은 크기가 m인 1차원 배열이며, i번째 스택의 top과 bottom   포인터는 다음과 같다. 

bottom[i] = top[i] = n/m * (i-1) (단, 1 ≤ i ≤ m)

 

1차원 배열을 이용한 다중 스택

  • i번째 스택에 삽입이 발생하면 top[i]++하여 i번째 top 포인터를 1 증가 시킨 후 삽입이 이루어짐

  • i번째 스택에 삭제가 발생하면 top[i]--하여 i번째 top 포인터를 1 감소 시킨 후 삭제가 이루어짐

  • 오버플로우는 top[i] == bottom[i+1]에 의해 검사됨

  • 언더플로우는 top[i] == bottom[i]에 의해 검사됨

 1) 자료의 삽입

 

  • 삽입하고자 하는 스택을 선택한 후 → top 포인터를 1 증가시킨 후 top 포인터가 가리키는 위치에 자료  삽입

  •  삽입 알고리즘

void multistack_PUSH(char item)

{

/* 개수가 m개인 다중 스택에 item을 삽입하는 알고리즘

STACK : 개수가 m개인 다중 스택

top : 스택 포인터로 i번째 스택의 포인터는 top[i]로 표현된다.

i : i 번째 스택에 대한 인덱스

item : 스택에 삽입할 자료 */

  int top[m], bottom[m], i;

  if(top[i]== bottom[i+1]) then

          {

         printf("Stack %d overflow",i); /* 여분의 기억 장소 없음 */

          exit(0); /* 종 료 */

          }

          else

          {

         top[i]++; /* i 번째 스택의 top 포인터 1 증가시킴 */

         STACK[top[i]] = item; /* i 번째 스택의 top 포인터가 가리키는 곳에 자료 삽입 */

          }

}

2) 자료의 삭제

 

   • 삭제하고자 하는 스택을 선택한 후 → top 포인터가 가리키는 위치의 자료 삭제 → top 포인터를 1 감소시킴

   • 삭제 알고리즘

void multistack_pop()

{

/* 개수가 m 개인 다중 스택에서 자료를 삭제하는 알고리즘.

STACK : 개수가 m개인 다중 스택

top : 스택 포인터로 i번째 스택 포인터는 top[i]로 표현된다.

i : i 번째 스택에 대한 인덱스

item : 스택에서 삭제된 자료가 저장된 변수 */

  int top[m], bottom[m], i;

  char item;

  if(top[i]==bottom[i])

          {

         printf("Stack %d empty"; i); /* 스택이 비었음 */

         exit(0); /* 종 료 */

          }

          else

          {

         item = STACK[top[i]]; /* top 포인터가 가리키는 곳의 자료를 삭제하여 item에 저장한다. */ 

          top[i]--; /* i 번째 스택의 top 포인터 1 감소시킴 */

          }

}

  다중(Multi) 큐

   • 크기가 n인 큐를 하나의  큐 크기가 n/m인 m개의 다중 스택으로 구현

   • 큐 하나 하나의 크기를 예상할 수 없으므로 동일한 크기로 분배한다.  

   • top와 bottom은 크기가 m인 1차원 배열이며, i번째 큐의 front와 rear 포인터는 다음과 같다. 

             front[i] = rear[i] = n/m * (i-1) (단, 1 ≤ i ≤ m)

1차원 배열을 이용한 다중 큐

   • i 번째 큐에서 삽입이 발생하면 rear[i]++하여 i번째 rear 포인터를1 증가시킨 후 삽입이 이루어짐

   • i 번째 큐에서 삭제가 발생하면 front[i]--하여 i 번째 front 포인터를1 감소시킨 후 삭제가 이루어짐

   •  오버플로우는 rear[i]==rear[n/m*(i-1)]에 의해 검사됨

   •  언더플로우는 front[i]==rear[i]에 의해 검사됨

  1) 자료의 삽입

   • 삽입하고자 하는 큐를 선택한 후 rear 포인터를 1 증가시킨 후→rear 포인터가 가리키는 위치에 자료 삽입

   • 삽입 알고리즘

void insert_multiqueue(item)

{

/* 개수가 m개인 다중 큐에서 자료를 삽입하는 알고리즘

Queue : 개수가 m개인 다중 큐

rear : 큐의 삽입 포인터로 i번째 큐의 삽입 포인터는 rear[i]로 표현된다.      

i : i 번째 큐에 대한 인덱스

item : 큐에 삽입할 자료 */

                                                                    

  int front[m], rear[m];

  if(rear[i] == n/m*(i+1)) then

          {

         printf("Queue %d full";i); /* 여분의 기억 장소 없음 */

         exit(o); /* 종료 */

          }

          else

          {

         rear[i]++; /* i번째 큐의 rear포인터 1 증가시킴 /*

         Queue[rear[i]]=item; /* i번째 큐의 rear 포인터가 가리키는 곳에 자료 삽입*/

         }

}

  2) 자료의 삭제

   • 삭제하고자 하는 큐를 선택한 후 → rear 포인터가 가리키는 위치의자료 삭제 →  rear 포인터를 1 감소시킴

   • 삭제 알고리즘

 

void delete_multiqueue()

{

/* 개수가 m개인 다중 큐에서 자료를 삭제하는 알고리즘

Queue : 개수가 m개인  다중 큐

front : 큐의 삭제 포인터로 i번째 큐의 삭제 포인터는 front[i]로 표현된다.

i : i번째 큐에 대한 인덱스

item : 큐에서 자료를 삭제하여 저장할 변수 */

  int front[m], rear[m]; 

  if(front[i]==rear[i]) then

         {

          printf("Queue %d empty“;i); /* 큐가 비었음 */

          exit(0); /* 종료 */

         }

         else

         {

          front[i]++; /* i 번째 큐의 front 포인터 1 증가시킴 */

           item = Queue[front[i]]; /* i 번째 큐의 front 포인터가 가리키는  곳의 자료를 삭제하여 item에 저장 */

         }

}