스택과 큐, 데크

스택과 큐, 데크 

 

  3.1 스택(Stack)

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

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

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

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

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

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

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

             →  top = top + 1

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

             →    top = top - 1

   •  top의 초기치는 -1이다

그림 3.1  스택의 구조

 

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

  • 예 - 동전통(택시)

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

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

  3.1.1 자료의 삽입

  • 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이다.)

  

 

 

 

3.1.2 자료의 삭제

  • 현재 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이다.)

   3.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 포인터가 가리키는 곳의 자료를 되돌려 준다*/
}

 

 

  3.2 큐(Queue)

 

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

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

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

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

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

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

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

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

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

그림 3.4 큐의 구조

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

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

   3.2.1 자료의 삽입

 

   • 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이다.)

 

  3.2.2 자료의 삭제

 

   • 현재 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에 저장한다. */
}

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

 

 

3.3 원형 큐(Circular Queue)

   • 큐를 원형으로 표현한 것

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

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

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

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

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

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

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

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

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

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

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

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

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

   • front와 rear의 초기치 : 0

원형 큐의 경우 하나의 공간을 비워둔다
그 이유는 그 비어있는 공간이 하나 없다면 꽉찬 큐와 비어있는 큐를 구별 할 수 없게 된다. 10개의 큐일 경우 9의 자료를 저장할 수 있다.

  

   3.3.1 자료의 삽입

 

   • 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 포인터가 가리키는 곳에 자료 삽입 */ 
 }

 

 

  3.3.2 자료의 삭제

 

  • 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에 저장한다. */
           }
}

 

 

 

  3.4 데크(Deque)

 

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

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

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

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

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

그림 3.8  데크의 구조

 

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

 

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

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

그림 3.9 데크의 종류