Chapter 4 스택, 큐, 데크.

Presentation on theme: "Chapter 4 스택, 큐, 데크."— Presentation transcript:

1 Chapter 4 스택, 큐, 데크

2 스택 스택 여러 데이터 항목을 일정한 순서로 입출력하기 위한 선형 데이터 구조 한쪽 끝에서만 데이터의 추가와 삭제가 수행
동전 케이스와 같은 작동 원리 먼저 삽입된 데이터는 가장 아래쪽에 위치하고 가장 최근에 삽입된 데이터는 출력 우선순위가 가장 높음

3 스택 스택의 정의 스택은 데이터 구조의 하나로서 원소의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 리스트 스택의 톱(top)
원소들의 삽입 삭제가 일어나는 곳 푸시(push) 원소를 스택에 넣는 것 팝(pop) 스택에서 원소를 꺼내는 것 나중에 들어간 원소가 먼저 꺼내어짐 후입선출(LIFO, Last-In, First Out)

4 스택 스택의 정의 스택은 주로 어떤 내용을 기억시켰다가 다시 이용하고자 할 때 사용되며 컴퓨터 알고리즘에서 자주 쓰이는 중요한 데이터구조 컴퓨터 기억장치의 일부로서 사용 스택 포인터(SP, Stack pointer)에 의해 간접적으로 주소 지정되며 푸시 명령과 팝 명령에 의해 그 내용이 참조 됨 스택 포인터는 스택의 top의 위치를 가리키는 역할을 함 스택 연산 푸시(push) 연산 스택의 톱에 새로운 원소를 삽입 팝(pop) 연산 스택의 톱에서 원소를 하나 제거하여 돌려줌 클리어(clear) 연산 스택을 깨끗이 비움

5 스택 스택의 정의 스택의 활용 예 컴퓨터의 운영체제에서는 차후에 원상 복귀시켜서 처리할 정보를 저장해 두는 데 스택을 사용
프로그램 실행 시에 사용되는 실행시간 스택(execution time stack)에는 현재 수행 중인 프로그램(함수나 서브루틴)에 관한 정보를 쌓아 놓음 스택에 저장하는 정보-실행할 루틴의 이름 혹은 번지, 실행종료후 복귀할 위치의 번지 값, 실행이 계속될 때 사용해야할 데이터 값 등 출구는 들어온 입구뿐이므로, 빠져나가는 순서는 C, B, A순인데, 이는 들어간 순서의 역순

6 스택 스택의 정의 배열로 표현한 스택의 예

7 스택 스택의 정의 스택을 프로그램으로 표현 일단 일정한 크기를 가진 기억 공간을 확보
스택의 윗부분을 가리키는 톱(top)이라는 포인터를 사용 스택에 데이터 항목 삽입 은 push 동작 데이터 항목을 삽입하려면 스택 포인터를 하나만큼 증가 스택의 top에 데이터 항목을 저장 오버플로우 검사 데이터 항목을 삽입하기 전에 새로운 항목을 저장할 빈 곳이 있는지 검사 스택에서 데이터 항목 삭제 pop 동작 스택의 top에 있는 데이터 항목을 출력하고 스택 포인터를 하나만큼 감소 데이터 항목을 삭제하기 전에 스택의 언더플로를 검사

8 스택 스택의 구현 방법 스택은 주로 선형 리스트의 하나인 배열에서 구현되거나 배열과 유사한 특성을 갖는 주기억장치에서 구현 됨
스택 알고리즘은 하나의 top 포인터를 사용하여 구현 top은 마지막으로 기록된 원소를 가리키는 포인터로 사용 top 포인터의 1증가 또는 감소에 의해 push, pop 동작이 수행 C를 기반으로 하는 경우 스택에서 언더플로(underflow) 조건과 오버플로(overflow) 조건 언더플로 조건 : top ≤ 0 오버플로 조건 : top ≥ n

9 스택 스택의 구현 방법 매우 제한적이긴 하지만 스택의 오버플로를 방지하기 위해 스택 구조를 구현하기 위한 링크드 리스트를 사용
스택을 이용한 링크드 리스트 구현

10 스택 스택의 구현 방법 스택을 이용한 링크드 리스트 구현 특징
스택이 당시에 필요한 만큼만의 공간을 차지하고 수행하는 동안 확장 가능함 스택에서 데이터가 삭제될 때 사용되지 않는 공간은 기억장소 관리자에게 보낼 수 있어서 공간을 절약할 수 있지만 기억장소 관리자를 호출하는데 시간이 걸림

11 스택 C/C++에서 스택의 이용 프로그램을 작성할 때, 사용자 입장에서 자동(auto) 변수와 재귀함수(recursive function)의 사용은 스택 사용함을 의미 함수 내에 선언된 변수는 디폴트(default)에 의해 자동 변수가 되지만, 키워드 auto를 사용하면 자동 변수의 의미가 명료해짐 자동 변수의 사용 시 주의점과 특성 스택(stack)으로 불리는 주기억장치 내의 일시적 기억 영역임 main() 함수 내에서는 auto int는 int로 사용되며, 국소적인 변수임 하나의 함수 내에서만 사용되며, 다른 함수에는 영향을 미치지 않음 자동 변수의 변위는 변수가 선언된 블록에 한정 됨

12 스택 C/C++에서 스택의 이용 자동 변수의 사용 시 주의점과 특성
2개의 서로 다른 함수에서 같은 이름의 변수가 사용되어도 서로 독립적임 초기화를 실행한 자동 변수는 그 변수를 포함하고 있는 함수가 호출될 때마다 초기화가 이루어짐 지역 범위를 갖고 있기 때문에 변수가 정의된 함수만이 그 변수를 알고 있으며, 다른 함수들도 동일한 이름의 변수를 사용할 수 있으나, 이는 다른 메모리나 스택에 저장되는 별개의 변수임 자동 변수는 그를 포함하는 함수가 호출될 때 생겼다가 함수가 작업을 마치고 호출자에게 제어를 넘길 때 사라짐

13 스택 C/C++에서 스택의 이용 중괄호를 중복 지정하여 변수의 통용 범위를 재지정 자동 변수의 특성 프로그램 ① ② ③ 01
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 #include <stdio.h> main() { int i = 6, j = 31; int i = 37; int i = 43; printf("i = %d \n", i); printf("j = %d \n", j); printf("\n"); } printf("j = %d \n\n", j); ① ② ③

14 스택 C/C++에서 스택의 이용 자동 변수의 특성 프로그램 - 실행결과

15 스택 C/C++에서 스택의 이용 자동 변수의 특성 프로그램 변수 i의 통용 범위

16 스택 C/C++에서 스택의 이용 자동 변수의 특성 프로그램 변수 j를 위한 스택

17 스택 C/C++에서 스택의 이용 예제 - main( ) 이외에 하나의 파일 내에서 다른 함수를 사용 01 02 03 04 05
06 07 08 09 10 11 12 13 14 15 16 17 #include <stdio.h> void kbs(); main() { int i = 6, j = 31; kbs(); printf("i = %d \n", i); printf("j = %d \n", j); } void kbs() int i = 14;

18 스택 C/C++에서 스택의 이용 예제 – 실행 결과 재귀함수에서도 C/C++에서 처리하는 경우 시스템에 의해 스택이 사용됨

19 스택 스택의 구현 알고리즘 Top 스택에 가장 마지막으로 삽입된 데이터를 가리키는 포인터 공백 조건 : top ≤ 0
오버플로 조건 : top ≥ n n은 스택에 삽입할 수 있는 데이터의 개수

20 스택 스택의 삽입 스택에 데이터를 입력하는 알고리즘의 의사 코드 ① 설명 한 요소를 배열 구조로 실현한 스택에 push함
스택의 크기는 N 색인으로 스택의 윗부분을 가리킴 입력 - 스택에 push한 데이터 출력 없음 별 이상이 없을 때 한함 변수 - TOP은 스택의 윗부분을 가리키는 색인으로 초기 값은 0이고, 0은 스택이 비어 있음을 나타냄 STACK[I] : 스택에서 I번째 요소.

21 스택 스택의 삽입 스택에 데이터를 입력하는 알고리즘의 의사 코드 ②
만일 TOP = n이면 리스트가 꽉 찬 상태이므로 오버플로 처리를 함 아니면 새로운 요소를 스택에 삽입함 색인 TOP을 1만큼 증가시킴 (TOP ← TOP+1, STACK[TOP] ← 새로운 요소) ③ PUSH 알고리즘 수행을 끝냄

22 스택 스택의 삽입 알고리즘으로 작성 - 입력 과정 : push 알고리즘 begin push 스택의 크기 : N
top 초기치 : 0 IF (top ≥ N) 스택 오버플로, EXIT 스택[top] ← 데이터 top ← top + 1 end push

23 스택 스택의 삽입 알고리즘으로 작성 3개의 요소가 정의된 배열(N = 3)에 데이터를 입력하기 위한 과정
데이터가 스택에 계속 추가되는 경우에 오버플로가 발생 스택의 오버플로 처리는 하나의 저장 공간에 2개 내지 그 이상의 스택을 서로 연결하여 운영함 3개의 요소가 정의된 배열(N = 3)에 데이터를 입력하기 위한 과정

24 스택 스택의 삽입 스택의 삽입 프로그램 01 02 03 04 05 06 07 08 void push(char data) {
if (top >= STACK_SIZE) printf("Stack is overflow ... \n"); else stack[top++] = data; stack[top] = NULL; }

25 스택 스택의 삭제 스택에서 데이터를 삭제하는 알고리즘을 의사 코드로 작성 ① 설명
선형 리스트로 실현한 스택에서 한 원자(atom)를 pop 색인으로 스택의 윗부분을 가리킴 색인 값의 최소 값은 1이어야 함 0일 때는 스택이 비어 있으므로 언더플로 처리 입력 - 없음. 출력 - 스택의 윗부분 데이터 변수 - TOP ← 스택의 윗부분을 가리키는 색인 STACK[I] : 스택에서 I번째 요소.

26 스택 스택의 삭제 스택에서 데이터를 삭제하는 알고리즘을 의사 코드로 작성 ②
만일 TOP이 0이면 삭제시킬 것이 없으므로 언더플로 처리 아니면 STACK[TOP] 원자를 추출 윗부분 포인터를 1만큼 감소시킴 (TOP ← TOP - 1, STACK[TOP] 원소 추출) ③ POP 알고리즘 수행을 끝냄

27 스택 스택의 삭제 스택에서 데이터를 삭제하는 알고리즘을 의사 코드로 작성 스택의 삭제 과정 - 출력 과정 : pop 알고리즘
begin pop 인덱스의 최소값 : 1 /* 0이면 pop 불가능 */ IF (top≤0) 스택 언더플로, EXIT top ← top - 1 데이터 ← 스택[top] end pop

28 스택 스택의 삭제 스택의 삭제 프로그램 01 02 03 04 05 06 07 void pop() {
if (top == NULL) printf("Stack is underflow ... \n"); else stack[--top] = NULL; }

29 스택 스택의 삭제 push와 pop 동작을 하나로 구현한 프로그램 01 02 03 04 05 06 07 08 09 10 11
12 13 14 15 16 17 18 19 20 #include <stdio.h> #define STACK_SIZE 100 #define NULL 0 int top = 0; int cnt = 0; char stack[STACK_SIZE]; void push(char data); void pop(); void write(); main( ) { int i; char value; for (value = 'A'; value < 'E'; value++) { write(); push(value); cnt++; }

30 스택 스택의 삭제 push와 pop 동작을 하나로 구현한 프로그램 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 4041 for (i = 0; i < cnt; i++) { pop(); write(); } void push(char data) { if (top >= STACK_SIZE) printf("Stack is overflow ... \n"); else stack[top++] = data; stack[top] = NULL; void pop( ) { if (top == NULL) printf("Stack is underflow ... \n"); stack[--top] = NULL;

31 스택 스택의 삭제 push와 pop 동작을 하나로 구현한 프로그램 push와 pop 동작을 하나로 구현한 프로그램 – 실행결과
42 43 44 void write( ) { printf(" stack -> %6s, top -> %d \n", stack, top); }

32 스택 스택의 사용 스택 활용 예 – 1 컴퓨터 운영체제에서 인터럽트가 발생한 경우에 복귀 주소의 저장이나 산술 계산에 사용됨
서브 프로그램 호출의 연속

33 스택 스택의 사용 스택 활용 예 – 1 프로그램을 실행시킬 때의 실행 시간 동안 스택의 내용

34 스택 스택의 사용 스택 활용 예 – 2 컴파일러(compiler)에서는 고급 언어의 명령문(statement)을 번역하는데 스택을 사용 산술식을 번역하여 대응하는 기계어를 만들 때 스택 활용 컴파일러는 산술식을 검토하면서, 피연산자(operand)와 연산자(operator)를 구별해 내고 또 각 연산의 우선순위에 맞게 그 산술식을 번역 산술식 계산 시 스택을 이용하면 기억 장소와 연산자를 저장하기 위한 두 개의 스택을 사용하는 것이 일반적 임 여러 가지의 수식 표기법 중위 표기법 연산자 - 피연산자 - 연산자의 형태로 수식을 표기 후위 표기법 피연산자 - 피연산자 - 연산자의 형태로 수식을 표기 전위 표기법 연산자 - 피연산자 - 피연산자의 형태로 수식을 표기

35 스택 스택의 사용 스택 활용 예 – 2 예제의 수식 ((x / y) - z) + p * q 중위 표기법
각 표기법의 표현 스택을 이용하여 산술식을 계산할 때의 처리 과정 예제의 수식 ((x / y) - z) + p * q 중위 표기법 (((x / y) - z) + (p * q)) 후위 표기법 x y / z - p q * + 전위 표기법 + - / x y z * p q ∙ 변수 스택에는 변수를 저장하고, 연산자 스택에는 연산자를 저장함 ∙ 연산자는 앞에 있는 연산자와 비교하여 우선순위가 높은 경우에는 삽입하고, 그렇지 않은 경우에는 변수의 내용을 먼저 처리한 후 저장함 ∙ 앞의 두 과정을 순서대로 반복하여 수행

36 스택 스택의 사용 스택 활용 예 – 2 스택을 이용하여 산술식을 계산할 때의 처리 과정

37 스택 스택의 사용 스택 활용 예 – 2 스택을 이용하여 산술식을 계산할 때의 처리 과정 A+B×C-D의 실제 연산 순서
R1 = B × C R2 = A + R1 R3 = R2 - D

38 큐 큐(queue) 리스트의 한쪽 끝의 노드로 삽입을 하고, 다른 쪽 끝의 노드만을 제거하는 것
가장 먼저 입력된 노드가 가장 먼저 제거 ,FIFO(Firstin First-out) 요소를 삽입하는 리스트의 양쪽 끝에 각각 1개씩 2개의 포인터를 사용

39 큐 큐의 정의 여러 데이터 항목을 일정한 순서로 입출력하기 위한 선형 데이터 구조
선형 리스트의 한쪽 끝에서는 삽입 동작만, 반대쪽에서는 삭제 동작만 발생 큐의 종류 선형 큐 한 방향으로 데이터 항목들이 삽입/삭제되는 선형 큐 환형 큐 시작점과 끝점이 서로 연결되어 있음 두 방법 모두 큐의 오버플로와 언더플로를 고려해야 함 rear와 front라는 2개의 포인터를 이용 삽입, 삭제 연산 시 먼저 입력한 데이터를 먼저 삭제 “FIFO(Frist in Frist Out)”

40 큐 큐의 정의 큐에 데이터 항목을 삽입 데이터 항목을 삭제 front 포인터는 rear 포인터보다 큰 값을 가질 수 없음
데이터 항목을 삭제하기 전에 큐의 언더플로를 고려 front 포인터는 rear 포인터보다 큰 값을 가질 수 없음 만약 front 포인터와 rear 포인터가 같은 값을 가진다면 큐에 저장된 데이터가 없다는 의미

41 큐 큐의 구현 방법 큐의 삽입과 삭제 과정 크기 n은 3으로 하고, 초기에 front와 rear는 0의 값을 가짐
데이터 10이 추가 현재 rear 포인터가 가리키는 곳에 데이터가 입력 rear 포인터가 1 증가

42 큐 큐의 구현 방법 큐의 삽입과 삭제 과정 데이터 20과 30이 추가 데이터 삭제 시
rear는 3의 값을 가지게 되므로 인덱스 2보다 커져 더는 데이터를 추가할 수 없게 됨 데이터 삭제 시 현재 front 포인터가 가리키는 10을 삭제 front 포인터가 1 증가 20과 30이 모두 제거된 다음에는 front와 rear가 같아지며, 이러한 경우에 큐 내의 모든 데이터가 삭제된 후 head와 tail이 같은 위치를 가리키게 되면 공백 상태인 언더플로를 의미

43 큐 큐의 구현 알고리즘 큐의 삽입 큐의 기본적인 삽입 알고리즘 front : 실제 위치보다 1 작은 곳을 가리키는 포인터
rear : 마지막으로 큐에 삽입된 원소를 가리키는 포인터 초기 조건 front = 0 rear = 0 오버플로 조건 rear ≥ n

44 큐 큐의 구현 알고리즘 큐의 삽입 큐에 데이터를 입력하기 위한 알고리즘을 의사 코드로 작성 ① 입력
- 큐에 새로이 삽입할 요소 출력 - 없음 ② rear = n이면 큐가 꽉 찬 상태이므로 오버플로 처리를 함 아니면 색인 rear의 값을 1만큼 증가하고, 새로운 item을 삽입함 (Q[rear] ← 새 데이터, rear ← rear + 1) ③ 삽입 알고리즘 수행을 종료함

45 큐 큐의 구현 알고리즘 큐의 삽입 알고리즘으로 표현 입력 과정 : 삽입 알고리즘 begin INSERT_큐 큐의 크기 : N
IF (tail) 〉 N 큐 오버플로; EXIT 큐[tail] ← 데이터 tail←tail+1 end INSERT_큐

46 큐 큐의 구현 알고리즘 큐의 삽입 알고리즘으로 표현 01 02 03 04 05 06 07 08 09 10
void Q_push(int data) { if (tail >= SIZE) printf(" Queue is overflow ... \n"); return; } queue[tail] = data; tail++;

47 큐 큐의 구현 알고리즘 큐의 삭제 큐의 기본적인 삭제 알고리즘
큐에서 head가 0이거나 head와 tail이 같아지면 공백 상태를 뜻하므로 데이터의 삭제가 불가능한 언더플로가 됨 만일 head가 0이 아니면 head를 하나 증가시키고, 큐의 head가 가리키는 곳의 데이터를 삭제 큐에서 데이터를 출력(제거)하기 위한 알고리즘을 의사 코드로 작성 ① 입력 - 없음 출력 - 큐에서 삭제할 데이터

48 큐 큐의 구현 알고리즘 큐의 삭제 큐에서 데이터를 출력(제거)하기 위한 알고리즘을 의사 코드로 작성 ②
front = rear이면 큐 언더플로 처리를 한다. 아니면 색인 front를 1만큼 증가하고, Q[front] 데이터를 삭제함 (item ← Q[front], front ← front + 1) ② 삭제 알고리즘을 종료

49 큐 큐의 구현 알고리즘 큐의 삭제 삭제 알고리즘 - 출력 과정 : 삭제 알고리즘 begin DELETE_큐
IF (head = NULL) 큐 언더플로; EXIT IF (head < tail) { 데이터 ← 큐[head] head ← head+1 IF( head = tail) 큐 언더플로; EXIT } IF (head > tail) head←0, tail←0 end DELETE_큐

50 큐 큐의 구현 알고리즘 큐의 삭제 삭제 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 void Q_pop() { int imsi; if (queue[head] == NULL) { printf("Queue is underflow ... \n"); return; } if (head < tail) { queue[head] = NULL; head++; if (head == tail) { if (head > tail) head = tail = NULL;

51 큐 큐의 구현 알고리즘 큐 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13 14 #include <stdio.h> #include <string.h> #define SIZE 10 #define NUL 0 int queue[SIZE]; int head = 0; int tail = 0; void Q_push(int data); void Q_pop(); void write(); void write1(); void write2();

52 큐 큐의 구현 알고리즘 큐 프로그램 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 main( ) { int i; for (i = 1; i < 5; i++) Q_push(i*100); write2(); for (i = 1; i < 5; i++) { write1(); Q_pop(); } void Q_push(int data) { if (tail >= SIZE) { printf(" Queue is overflow ... \n"); return; queue[tail] = data; write(); tail++;

53 큐 큐의 구현 알고리즘 큐 프로그램 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 void Q_pop( ){ if (queue[head] == NUL) { printf("Queue is underflow ... \n"); return; } if (head < tail) { queue[head] = NUL; head++; if (head == tail) { write(); if (head > tail) head = tail = NUL;

54 큐 큐의 구현 알고리즘 큐 프로그램 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 void write( ) { printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \head, tail, queue[head], queue[tail]); } void write1( ) { printf("Poped data .... \n"); void write2( ) { int i; printf("\n\t\t\t Contents of queue\n"); for (i = 0; i < SIZE; i++) printf("\t queue[%2d] = %d \n", i, queue[i]); printf("\n");

55 큐 큐의 구현 알고리즘 큐 프로그램 – 실행결과

56 큐 큐의 오버플로 처리 이동 큐 환형 리스트로 운영 프로그램 수행시 오버플로가 발생
오버플로 발생 시 큐 내의 모든 데이터를 헤드쪽으로 이동 환형 리스트로 운영 프로그램 수행시 오버플로가 발생

57 큐 이동 큐 프로그램 수행시 오버플로가 발생 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13
14 15 16 #include <stdio.h> #include <string.h> #define SIZE 5 #define NUL 0 int queue[SIZE+1] = {0, 0, 0, 1, 2, 3}; int head = 3; int tail = 5; void Q_push(int data); void Q_pop(); void write(); main( ) { Q_push(6); }

58 큐 이동 큐 프로그램 수행시 오버플로가 발생 프로그램 17 18 19 20 21 22 23 24 25 26
void Q_push(int data) { if (tail >= SIZE) { printf(" Queue is overflow ... \n"); return; } queue[tail] = data; write(); tail++;

59 큐 이동 큐 프로그램 수행시 오버플로가 발생 프로그램 27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 void Q_pop( ) { if (queue[head] == NUL) { printf("Queue is underflow ... \n"); return; } if (head < tail) { queue[head] = NUL; head++; if (head == tail) { write(); if (head > tail) head = tail = NUL; void write( ) { printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \ head, tail, queue[head], queue[tail]);

60 큐 이동 큐 프로그램 수행시 오버플로가 발생 프로그램 – 실행결과

61 큐 이동 큐 이동 큐 작업을 위한 전처리 과정 예

62 큐 이동 큐 프로그램 스택, 큐, 데크 04 121 실행결과 이동 큐 방법은 데이터 이동시간이 필요하고, 데이터가 부분적으로 큐에 들어가 있는 경우 에는 이를 처리하기 위해서 이 프로그램에서 제시한 프로그램보다 더 복잡한 프로그램을 필 요로 한다. 그러므로 실제적인 큐의 오버플로 해결 방안이 될 수 없다. 2.4.2 환형 큐 환형 큐는 선형 큐(이동 큐)의 문제점을 보완하기 위해 만들어진 데이터 구조이다. 삽입과 삭제 동작은 선형 큐와 같지만, 큐의 상한과 하한이 서로 연결된 고리 모양을 하고 있어, 사 실상 큐의 한계가 없는 것과 같다. [그림 4-10] 환형 큐의 구조 Data Structure & Algorithm 122 환형 큐에서는 선형 큐에서와 마찬가지로 삽입 위치를 가리키는 rear 포인터와 삭제 위치 를 가리키는 front 포인터가 있다. 두 개의 포인터는 초기에 시작점에서 출발하여 삽입과 삭제가 일어남에 따라 그 값이 하나씩 증가하여 시계 방향으로 이동한다. 포인터가 큐의 끝 점에 있을 때 삽입이나 삭제가 일어나면 포인터가 reset 되어 다시 시작점을 가리킨다. 환형 큐에서 front 포인터와 rear 포인터가 같은 곳을 가리키면 큐가 오버플로이다. 환형 큐에서 데이터 항목의 삭제는 front 포인터를 하나만큼 증가시키고, 그 위치에 있는 데이 터 항목을 제거한다. 만약 front 포인터가 끝점을 가리키고 있으면 reset 시켜준다. 환형 큐를 구현하기 위해서 큐를 0부터 N-1까지의 배열로 주고, tail = N - 1 일 때, 즉 큐의 마지막에 도달한 경우에 새로운 데이터는 맨 앞에 입력된다. [그림 4-11] 오버플로를 막기 위한 환형 큐의 사용 환형 큐에서는 삽입, 삭제 시 head와 tail은 시계 방향으로 증가되고, 초기 상태는 head 와 tail 값은 0으로 설정한다. 환형 큐의 삽입 알고리즘을 의사 코드로 작성하면 다음과 같다. ① 큐의 크기는 n이다. ② 시계 방향으로 tail을 이동한다. 이를 위해 잉여 연산자 mod를 사용한다. tail = (tail + 1) mod n ③ IF (head = tail) 큐는 오버플로이므로 tag 변수에 1을 저장하고, 큐의 head가 널이면 데이터를 입력하고 EXIT한다. ④ 환형 큐 Q에 item을 삽입한다. tail은 마지막 데이터를 가리키며, head는 Q의 첫 데이터의 앞 위치를 가리킨다. ⑤ ②부터 ④를 반복한다. ⑥ 종료한다. <환형 큐의 삽입을 위한 의사 코드> 123 이를 프로그램으로 작성하면 다음과 같다. void Q_push(int data) { tail = (tail + 1) % SIZE; if (head == tail) { printf(" Queue is overflow ... \n"); tag = 1; if(queue[head]=NUL) queue[head]=data; return; } queue[tail] = data; <환형 큐의 삽입> 예를 들어 살펴보기로 하자. 데이터를 삽입시키기 전에 tail의 위치를 시계 방향으로 증가 시킨다. 증가된 tail과 head가 같게 되면 큐는 오버플로 상태가 되어 데이터를 삽입시킬 수 없으며, 그렇지 않은 경우에는 데이터를 삽입시킨다. 10을 삽입시키는 경우 tail ← (tail+1) mod n에 의해 tail은 인덱스 1이 되며, head≠tail 이므로 인덱스 1에 10이 들어간다. 20을 삽입시키는 경우 tail ← (tail+1) mod n에 의해 tail은 인덱스 2가 되며 인덱 스 2에 20이 들어간다. 124 30을 삽입하는 경우에 tail은 3을 3으로 나눈 나머지를 구하므로 0이 되어 0번째 인덱스 에 30을 입력한다. 이 경우에 head = tail 이므로 큐는 오버플로 된다. 다음은 삭제 알고리즘을 의사 코드로 작성한 것이다. ① IF (head = tail and tag = 0) 큐는 언더플로이므로 EXIT 한다. ② 시계 방향으로 head를 1 증가한다. head = (head + 1) mod n ③ IF (head == tail) tag = 0 ④ 큐의 head 값을 제거한다. ⑤ ①부터 ④를 반복한다. <환형 큐의 삭제를 위한 의사 코드> int Q_pop() int imsi; if (head == tail && tag == 0) { printf("Queue is underflow ... \n"); return(0); head = (head + 1) % SIZE; if(head == tail) tag = 0; imsi = queue[head]; queue[head] = NULL; return(imsi); <환형 큐의 삭제 프로그램> 125 초기에 head와 tail이 모두 0인 경우에는 큐는 공백 상태를 나타내므로 데이터의 삭제가 불가능하다. 그러나 그렇지 않을 경우에는 head를 시계 방향으로 증가한 다음 head가 가 리키는 데이터를 삭제한다. 10을 삭제시키는 경우, head ←(head+1) mod n에 의해 head는 인덱스 1을 가리키며, 10이 제거된다. 20을 삭제시키는 경우, head ←(head + 1) mod n에 의해 head는 2가 되며, 20은 삭제 된다. 만약, 또 한 번 삭제를 하는 경우, head가 증가되어 head = tail이 된다. 이 경우 tag 변수는 0의 값을 가지므로 언더플로 조건이 된다. 다음은 큐 프로그램을 살펴보자. 이 프로그램은 앞에서 제시된 환형 큐의 삽입과 삭제 프로 그램을 가지고 구현한 것이다. #include <stdio.h> #include <string.h> #define SIZE 5 #define NUL 0 int queue[SIZE]; int head = 0; int tail = 0; int tag = 0; void Q_push(int data); int Q_pop(); void write(); 126 void write1(); void write2(); main() Q_push(6); Q_push(14); Q_push(31); write2(); Q_pop(); write1(); Q_push(35); Q_push(37); Q_push(43); if (queue[head] == NUL) queue[head] = data; write(); if(head = tail) tag = 0; queue[head] = NUL; 127 void write() printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \ head, tail, queue[head], queue[tail]); void write1() printf("Poped data .... \n"); void write2() int i; printf("\n\t\t\t Contents of queue\n"); for (i = 0; i < SIZE; i++) printf("\t queue[%d] = %d \n", i, queue[i]); printf("\n"); 128 2.5 큐의 활용 대부분의 운영체제는 컴퓨터 상의 여러 곳에 큐를 형성시키고 또 관리한다. 작업 리스트의 첫 번째 작업을 완료한 후 운영체제는 다음 번 처리할 작업을 그렇게 정리해 놓은 작업 리 스트에서 첫 번째 작업을 선택하여 실행시켜 준다. 이와 병행하여 새로운 작업을 그 리스트 의 마지막에 추가시킬 수 있다. 이러한 리스트 구조를 큐(대기 행렬, queue)라고 부른다. 이 데이터 구조에서는 새로운 요소를 리스트 마지막에 삽입시키며, 저장된 요소를 리스트의 앞에서 삭제한다. 이러한 큐의 한 예로 출력 큐(output queue)를 들 수 있다. 운영체제는 한 작업(job)에서 만들어 낸 모든 출력을 프린터(printer)를 배당할 수 있을 때까지 디스크(disk)에 임시로 저 장시킨다. 출력을 대기하고 있는 작업들이 출력 큐를 형성한다. 프린터가 한 대이고 우선순 위가 없는 체제(non priority system)에서는 데이터 처리가 끝난 순서로 각 작업을 인쇄시 킨다. 프린터의 인쇄 속도와 인쇄 양에 따라서 큐의 길이가 길어졌다 줄어들었다 한다. 어 떠한 경우, 인쇄시킬 파일(file)이 너무 많아, 큐의 길이가 허용치에 육박할 경우 중앙처리 장치(또는 마이크로 프로세서)는 새로운 작업 처리를 잠시 지연시키고 인쇄 작업을 진행시 켜서 큐의 길이를 감소시킨다. 2.6 큐의 길이 앞에서 큐가 비거나 혹은 가득 찰 수 있다고 했다. 후자의 경우 중앙처리장치(CPU)는 처리 중인 작업을 잠시 중단하고 출력을 처리한다고 하지만 출력 큐의 길이를 짧게 잡은 결과로 중앙처리장치를 자주 중단시킬 수는 없는 노릇이다. 가장 적당한 출력 큐의 길이를 결정하 는 데는, 단위 시간당 큐에 도착하는 새로운 item의 평균 개수(λ), 한 item을 처리하는 데 걸리는 시간, 그리고 단위 시간당 큐를 빠져나가는 item의 평균 개수(μ) 등이 필요하다. 이 몇 개 안 되는 수치들을 측정하거나 추정해서 큐의 길이 계산에 이용한다. 통계학의 한 분야이고, 이론이 잘 정립된 대기행렬이론(queueing theory)의 결과를 이용해서 그 길이 를 계산한다. μ가 λ보다 작으면 큐가 점점 길어져서 큐의 길이가 결국 불안정한 상태에 있게 된다고 한다. 한 item을 처리하는 시간이 대부분의 item에 대해서는 짧고 몇몇의 item에 대해서는 길다고 가정한다면 큐의 평균 길이를 다음 식으로 얻을 수 있다.       여기에서 큐의 “평균” 길이는 L이다. 그래서 어떤 경우에는 큐의 길이가 L보다 길 때도 있 겠고 혹은 짧은 경우도 있을 것이다. 큐의 오버플로를 전체 시간의 Z만큼의 시간 동안 허용 한다 할 때 큐에 필요한 전체 기억 장소의 길이(K)는 다음 공식으로 구할 수 있다. 129 3 다중 스택과 다중 큐         큐의 길이 K의 확률 분포 함수에 따라 결정된다고 한다. 공식에서 Z는 백분율이다. 즉, Z를 100으로 나누어 소수 값을 얻는다. P를 번잡도(traffic intensity)라고 하며 λ/μ로 정의 한다. 예를 들면, 새로운 요소의 평균 개수가 5item(atom)/밀리 초(millisecond)이고, 큐를 빠져 나가는 요소의 평균 개수가 8item/밀리 초이고, 전체 시간의 1% 동안 오버플로가 발생한다 고 할 때 이 큐에 필요한 기억 장소의 개수는 앞에서 본 2개의 공식을 적용하면 답을 얻을 수 있다. 먼저 평균 길이 L을 구하면 다음과 같다.        ≈  전체 시간의 1% 동안 오버플로 발생을 허용했을 때, 필요한 기억 장소의 양은,         ≈  인데, 평균 길이 L보다 상당히 큰 값을 얻는다. 하지만 이런 수치들은 큐를 선형 리스트식 으로 구현했을 때 필요한 기억 장소의 개수를 나타낸다. 만일 포인터를 사용할 경우에는 필 요한 기억 장소의 양이 더 많아진다. 밀도(density)가 1/3이라고 가정해 보면, 필요한 기억 장소의 개수가 10÷(1/3)=30개이다. 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 #include <stdio.h> #include <string.h> #define SIZE 5 #define NUL 0 int queue[SIZE+1] = {0, 0, 0, 1, 2, 3}; int head = 3; int tail = 5; int Q_push(int data); void exchange(); void Q_pop(); void write(); void write1(); void write2();

63 큐 이동 큐 프로그램 16 17 18 19 20 21 22 23 24 25 26 void main( ) { int temp;
write1(); temp = Q_push(6); if (temp == 0) return; Q_pop(head); }

64 큐 이동 큐 프로그램 27 28 29 30 31 3233 34 35 36 37 38 39 40 41 42 43 int Q_push(int data) { if ((tail - head + 1) == SIZE) { printf(" Queue is overflow ... \n"); return 0; } if (queue[head] == NUL) { head = 0; tail = 0; else if (tail == SIZE) exchange(); tail++; queue[tail] = data; write(); return 1;

65 큐 이동 큐 프로그램 44 45 46 47 48 49 50 51 52 53 54 55 56 void exchange( ) {
int i, count; count = tail - head + 1; for (i = 0; i < count; i++) { queue[i] = queue[head]; queue[head] = NUL; head = head + 1; } head = 0; tail = count - 1; return;

66 큐 이동 큐 프로그램 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 void Q_pop( ) { if (queue[head] == NUL) { printf("Queue is underflow ... \n"); return; } if (head < tail) { queue[head] = NUL; head++; if (head == tail) { write2(); if (head > tail) head = tail = NUL;

67 큐 이동 큐 프로그램 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 void write( ) { printf("Pushed data .... \n"); printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \ head, tail, queue[head], queue[tail]); } void write1( ) { int i; printf("\n\t\t\t Contents of queue\n"); for (i = 0; i <= SIZE; i++) printf("\t queue[%d] = %d \n", i, queue[i]); printf("\n"); void write2( ) { printf("Poped data .... \n");

68 큐 이동 큐 프로그램 – 실행결과

69 큐 환형 큐 선형 큐(이동 큐)의 문제점을 보완하기 위해 만들어진 데이터 구조
삽입과 삭제 동작은 선형 큐와 같지만, 큐의 상한과 하한이 서로 연결된 고리 모양을 하고 있어, 사실상 큐의 한계가 없는 것과 같음 환형 큐의 구조

70 큐 환형 큐 환형 큐의 포인터 오버플로 데이터 항목의 삭제 삽입 위치를 가리키는 rear 포인터
삭제 위치를 가리키는 front 포인터 두 개의 포인터는 초기에 시작점에서 출발하여 삽입과 삭제가 일어남에 따라 그 값이 하나씩 증가하여 시계 방향으로 이동 포인터가 큐의 끝점에 있을 때 삽입이나 삭제가 일어나면 포인터가 reset 되어 다시 시작점을 가리킴 오버플로 front 포인터와 rear 포인터가 같은 곳을 가리킴 데이터 항목의 삭제 front 포인터를 하나만큼 증가 그 위치에 있는 데이터 항목을 제거 만약 front 포인터가 끝점을 가리키고 있으면 reset 시켜줌

71 큐 환형 큐 구현 큐를 0부터 N-1까지의 배열로 구성
tail = N - 1 일 때, 큐의 마지막에 도달한 경우에 새로운 데이터는 맨 앞에 입력 됨

72 큐 환형 큐 환형 큐의 삽입 알고리즘을 의사 코드로 작성 ① 큐의 크기는 n ② 시계 방향으로 tail을 이동
- 이를 위해 잉여 연산자 mod를 사용 - tail = (tail + 1) mod n ③ IF (head = tail) 큐는 오버플로이므로 tag 변수에 1을 저장 큐의 head가 널이면 데이터를 입력 - EXIT ④ 환형 큐 Q에 item을 삽입 tail은 마지막 데이터를 가리킴 head는 Q의 첫 데이터의 앞 위치를 가리킴 ⑤ ②부터 ④를 반복 ⑥ 종료

73 큐 환형 큐 환형 큐의 삽입 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13 void Q_push(int data) { tail = (tail + 1) % SIZE; if (head == tail) printf(" Queue is overflow ... \n"); tag = 1; if(queue[head]=NUL) queue[head]=data; return; } queue[tail] = data;

74 큐 환형 큐 환형 큐의 삽입 과정 데이터를 삽입시키기 전에 tail의 위치를 시계 방향으로 증가 10을 삽입시키는 경우
증가된 tail과 head가 같게 되면 큐는 오버플로 그렇지 않은 경우에는 데이터를 삽입 10을 삽입시키는 경우 tail ← (tail+1) mod n에 의해 tail은 인덱스 1이 됨 head≠tail 이므로 인덱스 1에 10이 들어감

75 큐 환형 큐 환형 큐의 삽입 과정 20을 삽입시키는 경우 30을 삽입하는 경우
tail ← (tail+1) mod n에 의해 tail은 인덱스 2가 됨 인덱스 2에 20이 들어감 30을 삽입하는 경우 tail은 3을 3으로 나눈 나머지를 구하므로 0이 됨 0번째 인덱스에 30을 입력 이 경우에 head = tail 이므로 큐는 오버플로

76 큐 환형 큐 삭제 알고리즘을 의사 코드로 작성 ① IF (head = tail and tag = 0)
- 큐는 언더플로이므로 EXIT 함 ② 시계 방향으로 head를 1 증가 - head = (head + 1) mod n ③ IF (head == tail) tag = 0 ④ 큐의 head 값을 제거 ⑤ ①부터 ④를 반복

77 큐 환형 큐 삭제 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13 14 int Q_pop() {
int imsi; if (head == tail && tag == 0) printf("Queue is underflow ... \n"); return(0); } head = (head + 1) % SIZE; if(head == tail) tag = 0; imsi = queue[head]; queue[head] = NULL; return(imsi);

78 큐 환형 큐 삭제 과정 초기에 head와 tail이 모두 0인 경우에는 큐는 공백 상태를 나타내므로 데이터의 삭제가 불가능
10을 삭제시키는 경우 head ←(head+1) mod n에 의해 head는 인덱스 1을 가리킴 10이 제거 됨

79 큐 환형 큐 삭제 과정 20을 삭제시키는 경우 만약, 또 한 번 삭제를 하는 경우
head ←(head + 1) mod n에 의해 head는 2가 됨 20은 삭제 만약, 또 한 번 삭제를 하는 경우 head가 증가되어 head = tail이 됨 이 경우 tag 변수는 0의 값을 가지므로 언더플로

80 큐 환형 큐 환형 큐 프로그램 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 #include <stdio.h> #include <string.h> #define SIZE 5 #define NUL 0 int queue[SIZE]; int head = 0; int tail = 0; int tag = 0; void Q_push(int data); int Q_pop(); void write(); void write1(); void write2();

81 큐 환형 큐 환형 큐 프로그램 16 17 18 19 20 21 22 23 24 25 26 27 28 29 main( ) { Q_push(6); Q_push(14); Q_push(31); write2(); Q_pop(); write1(); Q_push(35); Q_push(37); Q_push(43); }

82 큐 환형 큐 환형 큐 프로그램 30 31 32 33 34 35 36 37 38 39 40 41 42 void Q_push(int data) { tail = (tail + 1) % SIZE; if (head == tail) { printf(" Queue is overflow ... \n"); tag = 1; if (queue[head] == NUL) queue[head] = data; return; } queue[tail] = data; write();

83 큐 환형 큐 환형 큐 프로그램 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 int Q_pop( ) { int imsi; if (head == tail && tag == 0) { printf("Queue is underflow ... \n"); return(0); } head = (head + 1) % SIZE; if(head = tail) tag = 0; imsi = queue[head]; queue[head] = NUL; return(imsi); void write( ) { printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \ head, tail, queue[head], queue[tail]);

84 큐 환형 큐 환형 큐 프로그램 61 62 63 64 65 66 67 68 69 70 71 72 73 void write1( ) { printf("Poped data .... \n"); printf("head -> %d, tail -> %d, queue[head] -> %3d, queue[tail] -> %3d \n", \ head, tail, queue[head], queue[tail]); } void write2( ) { int i; printf("\n\t\t\t Contents of queue\n"); for (i = 0; i < SIZE; i++) printf("\t queue[%d] = %d \n", i, queue[i]); printf("\n");

85 큐 환형 큐 환형 큐 프로그램 – 실행결과

86 큐 큐의 활용 - 출력 큐(output queue)
운영체제는 한 작업(job)에서 만들어 낸 모든 출력을 프린터(printer)를 배당할 수 있을 때까지 디스크(disk)에 임시로 저장 출력을 대기하고 있는 작업들이 출력 큐를 형성 프린터가 한 대이고 우선순위가 없는 체제(non priority system)에서는 데이터 처리가 끝난 순서로 각 작업을 인쇄

87 큐 큐의 길이 가장 적당한 출력 큐의 길이를 결정 요인 큐의 평균 길이
단위 시간당 큐에 도착하는 새로운 item의 평균 개수(λ) 한 item을 처리하는 데 걸리는 시간 그리고 단위 시간당 큐를 빠져나가는 item의 평균 개수(μ) 큐의 평균 길이 큐의 오버플로를 전체 시간의 Z만큼의 시간 동안 허용한다 할 때 큐에 필요한 전체 기억 장소의 길이(K)

88 큐 큐의 길이 - 예 새로운 요소의 평균 개수가 5item(atom)/밀리 초(millisecond)
전체 시간의 1% 동안 오버플로가 발생 이 큐에 필요한 기억 장소 전체 시간의 1% 동안 오버플로 발생을 허용했을 때, 필요한 기억 장소의 양 밀도(density)가 1/3이라고 가정해 보면, 필요한 기억 장소의 개수가 10÷(1/3)=30개임

89 다중 스택과 다중 큐 다중 스택 스택의 오버플로 발생 방지를 위해 사용되는 구조로서 2개의 스택을 서로 연결시켜 사용하는 것
하나의 저장 공간에 n개의 스택을 연결시켜 처리하는 것 다중 스택은 1차원 배열 또는 2차원 배열을 이용하여 표현 2차원 배열로 표현한 다중 스택

90 다중 스택과 다중 큐 다중 큐 우선순위 큐 다중 큐의 대표 각각의 우선순위에 따라서 여러개의 큐로 구성
각 큐는 자신의 우선을 갖고 있음 우선순위가 할당된 입력 데이터는 자신의 우선순위에 해당하는 큐에 삽입된 다음에 가장 우선순위가 높은 큐부터 차례로 처리 됨 우선순위 큐의 규칙 가장 높은 우선순위를 갖는 큐에 있는 요소가 자신보다 낮은 우선순위를 갖는 큐에 있는 요소보다 먼저 처리됨 동일한 우선순위를 갖는 요소가 두 개 이상 있으면 큐에 삽입된 순서에 따라 FIFO방식으로 처리

91 다중 스택과 다중 큐 다중 큐 우선순위 큐 우선순위 큐는 2차원 배열을 이용하거나 연결 리스트를 사용하여 구현
배열을 이용하여 우선순위 큐의 구현 2차원 배열을 이용 2차원 배열의 각 행은 각 우선순위 큐를 나타냄 배열은 각 우선순위 큐에 할당된 데이터의 위치를 나타냄 각 우선순위 큐를 표현하고자 한다면 우선순위를 나타내는 2차원 배열과 각 우선순위 큐에 대하여 head와 tail의 위치를 나타내는 두 개의 1차원 배열이 필요 우선순위 큐에서 데이터를 삽입하기 위해서는 먼저 데이터의 우선순위를 확인한 다음에 해당 우선순위 큐에 삽입

92 데크 데크(Deque) 데크의 정의 double-ended queue의 머리글자에서 약어로 구성
리스트의 양쪽 끝에서 삽입과 삭제를 허용하는 데이터 구조 데크의 정의 스택과 큐를 혼합한 상태 비슷한 동작으로 양쪽 끝 모두에서 삽입과 삭제가 일어나도록 되어 있는 데이터 구조 2개의 포인터가 양끝을 가리키게 됨 END1, END2 데크의 구조 선언 배열을 이용할 수 있으며 하나의 배열을 선언한 뒤 포인터 END1, END2가 선언됨

93 데크 데크의 정의 2개의 포인터를 사용하는 데크의 예

94 데크 데크의 구현 데크를 구현하기 위해서 선형 리스트 구조를 사용
만약 데크가 두 개의 스택을 나타낸다면 END1과 END2는 그 스택들의 top을 가리키는 구조로 구현될 수 있음 큐와 스택에서처럼 빈 데크에서 데이터를 삭제하려 한다면 언더플로가 발생 양끝에서 삽입과 삭제를 할 수 있기 때문에 이것을 거대한 큐나 거대한 스택으로 사용할 수 있음

95 데크 데크의 구현 데크의 사용 예

96 데크 데크의 구현 원칙적으로 데크의 양쪽 끝 모두에서 삽입 연산과 삭제 연산이 허용되지만 삽입이나 삭제를 제한함에 따라 다음과 같은 데크의 종류가 생김 입력 제한 데크의 구조 입력이 한쪽 끝에서만 일어날 수 있도록 제한하는 경우로 이를 입력 제한 데크 또는 스크롤(scroll) 이라 함 출력 제한 데크의 구조 출력이 한쪽 끝에서만 일어날 수 있도록 제한하는 경우로 이를 출력 제한 데크 또는 셀프(shelf)라고 함