Microsoft PowerPoint - 제4장-스택과큐.pptx

Transcription

1 제 4 강의. 스택과큐자료구조 1

2 제 4 강. 스택과큐자료구조 학습목차 1. 스택과큐자료구조 2. 스택자료구조 3. 큐자료구조 4. 원형큐의구현 2

3 1. 스택 (Stack) 과큐자료구조 리스트, 스택과큐 (Stack and Queue) 스택과큐는리스트자료구조의특별한경우이다. 리스트 - 순서가있다 - 읽기, 삽입 (insert) 과삭제 (delete) 를리스트의어느곳에서나행함 스택 - 순서가있다 - 삽입 (insert) 과삭제 (delete) 를리스트의한쪽 (top 이라고부름 ) 에서행함 큐 - 순서가있다 - 삽입 (insert) 은리스트의한쪽 (rear) 에서하고삭제 (delete) 는삽입의반대쪽 (front) 에서행함 3

4 리스트 ( 순서가있는자료구조 ) 리스트읽기, 삽입 (insert), 삭제 (delete) : 아무곳에서나가능 스택삽입 (insert) - 리스트의한쪽 (top 이라고부름 ) 에서행함삭제 (delete) - 리스트의한쪽 (top 이라고부름 ) 에서행함 큐삽입 (insert) - 리스트의한쪽 (rear) 에서행함삭제 (delete) - 삽입의반대쪽 (front) 에서행함 4

5 자료구조와연산모델 자료구조연산 읽기 검사 삽입삭제 search ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 자료구조 = 자료선언 + 연산자료구조는자료의선언과자료에대한연산으로구성된다. 자료의선언은프로그램언어의타입을이용하여선언된다. 연산은자료의검색과갱신에관한연산으로이루어진다. 검색은원하는자료를 1개혹은일부를찾는작업이다. 갱신은삽입, 삭제, 수정을말한다. 5

6 2 스택 (Stack) -스택S = (a0,, an-1) a0 : bottom 원소 an-1 : top 원소 ai : 스택원소 (0<i<n), i+1번째원소 -삽입은리스트의마지막에삭제도리스트의마지막에서행한다. A A B top A B C top push(a) push(b) push(c) - Last-In-First-Out (LIFO) 자료구조 A B top pop() top A B D push(d) top 스택에서의원소의삽입과삭제 6

7 스택자료구조와연산 스택자료구조연산 읽기 검사 삽입삭제 top ( ) push ( ) pop( ) isempty ( ) isfull( ) top() : 스택의맨위에있는데이터값을반환한다. push() : 스택에데이터를삽입한다. pop() : 스택에서데이터를삭제하여반환한다. isempty() : 스택에원소가없으면 true 있으면 false 값반환 isfull() : 스택에원소가없으면 false 있으면 true 값반환 7

8 스택의생성 스택자료구조연산 읽기 검사 삽입삭제 top ( ) push ( ) pop( ) isempty ( ) isfull( ) 스택의생성 1 차원배열의사용 #define MAX_STACK_SIZE 100 int stack[max_stack_size]; int top = -1; /* top의초기값은스택이비어있을때 1이다. */ 8

9 스택의구현 push() 함수 스택자료구조연산 읽기 검사 삽입삭제 top ( ) push ( ) pop( ) isempty ( ) isfull( ) 스택의원소삽입 (push) void push(int item) { if(top >= MAX_STACK_SIZE - 1) { stack_full(); return; } stack[++top] = item; // top++; stack[top] = item; } 9

10 스택의구현 pop( ) 함수 스택자료구조연산 읽기 검사 삽입삭제 top ( ) push ( ) pop( ) isempty ( ) isfull( ) 스택의원소삭제 (pop) int pop( ) { if(top == -1) return stack_empty(); return stack[top--]; // int x; x = stack[top]; top--; return x; } 10

11 스택의구현 isempty(), isfull() 스택자료구조연산 읽기 검사 삽입삭제 top ( ) push ( ) pop( ) isempty ( ) isfull( ) 스택의검사 스택이비어있는지검사하는함수 int isempty() { if( top < 0 ) return(1); else return(0); } 스택이가득차있는지검사하는함수 int isfull() { if ( top >= MAX_STACK_SIZE 1 ) return(1); else return(0); } 11

12 스택의구현 C 언어 아래프로그램을실행해보자 - 실행후다음과같은점을생각해보자스택의원소타입이 int 가아니면어떻게고쳐야하는가? 스택 (stack) 을 2 개사용하려면어떻게해야하는가? #include <stdio.h> #define MAX_STACK_SIZE 100 int stack[max_stack_size]; int top = -1; void push(int item) { if(top >= MAX_STACK_SIZE - 1) { printf("stack_full()\n"); return; } stack[++top] = item; } int pop() { if(top == -1) { printf("stack_empty()\n"); exit(); } return stack[(top)--]; } 12

13 스택의구현 - 계속 int isempty() { if( top == -1 ) return(1); else return(0); } int isfull() { if ( top >= MAX_STACK_SIZE -1 ) return(1); else return(0); } int main() { int e; push(20); push(40); push(60); printf(" Begin Stack Test...\n"); } while(!isempty()) { e = pop(); printf("value = %d\n", e); } 13

14 Stack 연습 ( 스택의실험 ) stacktest.c 를바꾸어다음과같은프로그램을완성하여보아라.( 스택과스택관련함수를 2 개씩만든다 ) ( 실험 1) 수유역에도착하는임의의마을버스이름 4개를스택에입력한다. 어느프로야구팀의선수번호 4개를스택에입력한다. 마을버스와야구선수번호를양쪽스택에서하나씩 pop() 하여출력한다. ( 실험 2) 실험 1에서야구선수번호대신야구선수이름을스택에입력한다. ( 실험 3) 실험 2에서 ( 야구선수번호, 야구선수이름 ) 을구조체로만들어스택에입력한다. 14

15 스택의구현 Java 언어 // Stack.java import java.io.*; // for I/O class StackX { private int maxsize; // size of stack array private double[] stackarray; private int top; // top of stack public StackX(int s) // constructor { maxsize = s; // set array size stackarray = new double[maxsize]; // create array top = -1; // no items yet } public void push(double j) // put item on top of stack { stackarray[++top] = j;} // increment top, insert item public double pop() // take item from top of stack { return stackarray[top--]}; // decrement top public double peek() // peek at top of stack { return stackarray[top]; } public boolean isempty() // true if stack is empty { return (top == -1); } public boolean isfull() // true if stack is full { return (top == maxsize-1); } } // end class StackX 15

16 스택의구현 Java 언어 - 실행후다음과같은점을생각해보자스택의원소타입이 int 가아니면어떻게고쳐야하는가? 스택 (stack) 을 2 개사용하려면어떻게해야하는가? //////////////////////////////////////////////////////////////// class StackApp { public static void main(string[] args) { StackX thestack = new StackX(10); // make new stack thestack.push(20); // push items onto stack thestack.push(40); thestack.push(60); thestack.push(80); while(!thestack.isempty() ) // until it's empty, { // delete item from stack double value = thestack.pop(); System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); } // end main() } // end class StackApp 16

17 C 언어와 Java 의스택구현방법비교 int stack[size]; void push(int item); int pop(); int isempty(); int isfull(); int main() { int e; push(20); push(40); push(60);... class StackX private int maxsize; private.. stackarray; private int top; public void push( ) public double pop() public boolean isempty() public boolean isfull() class StackApp public main() { StackX thestack = new StackX(10); thestack.push(20); thestack.push(40);... 17

18 C 언어 1 개의프로그램에서 2 개의스택사용 int stack1[size]; void push1(int item); int pop1(); int isempty1(); int isfull1(); int main() { int e; push1(20); push2(40); push1(60);... int stack2[size]; void push2(int item); int pop2(); int isempty2(); int isfull2(); 18

19 Java 1 개의프로그램에서 2 개의스택사용 스택 Class 정의 class StackX private int maxsize; private.. stackarray; private int top; public void push( ) public double pop() public boolean isempty() public boolean isfull() class StackApp public main() { StackX thestack1 = new StackX(10); StackX thestack2 = new StackX(10); thestack1.push(20); thestack2.push(40);... Java 다른프로그램에서스택사용 class StackApp2 public main() { StackX mystack = new StackX(10); mystack.push(20); mystack.push(40);... 19

20 3. 큐자료구조 - 순서있는리스트 - 삽입연산은한쪽끝에서일어난다 (rear 라고부른다 ) - 삭제연산은삽입의반대쪽에서일어난다.(front 라고부른다.) - FIFO(First In First Out) A front=rear A B front rear front A B C B C insert(a) insert(b) insert(c) rear delete(a) front rear B C D insert(d) front rear 큐에서의원소의삽입과삭제 20

21 큐의생성 큐자료구조연산 읽기 검사 삽입삭제 first ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 큐의구현 /* 1차원배열의사용, front와 rear 변수사용 */ #define MAX_QUEUE_SIZE 100 typedef struct { int key; /* other fields */ } element; element queue[max_queue_size]; int rear = -1; int front = -1; 21

22 큐의구현 insert, add() 큐자료구조연산 읽기 검사 삽입삭제 first ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 큐원소의삽입 void insert(int *rear, element item) { if(*rear == MAX_QUEUE_SIZE - 1) { queue_full(); /* 처리방법 큐의원소를모두원쪽으로이동? */ return; } queue[++*rear] = item; } 22

23 큐의구현 delete 큐자료구조연산 읽기 검사 삽입삭제 first ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 큐원소의삭제 element delete(int *front, int rear) { if(*front == rear) return queue_empty(); /* return an error key */ return queue[++*front]; } 23

24 큐의구현 isempty(), isfull() 큐자료구조연산 읽기 검사 삽입 삭제 first ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 큐원소검사 큐가비어있는지검사하는함수 int isempty() { if( front == rear ) return(1); else return(0); } 큐가가득차있는지검사하는함수 int isfull() { if ( rear == MAX_QUEUE_SIZE 1 ) return(1); else return(0); } 24

25 큐의예 예 - 고객작업처리은행, 미용실등고객은큐를구성한다. 각고객은점원에게한개의처리작업이된다.(job) 점원은작업을한개씩처리한다. front rear Q[0] Q[1] Q[2] Q[3] 설명 s J1 J1 J1 J2 J2 J2 J3 J3 J3 초기상태 Job 1 삽입 Job 2 삽입 Job 3 삽입 Job 1 삭제 Job 2 삭제 큐에작업이들어온상태 25

26 4. 원형큐 (circular queue) 큐의구현에서문제점작업큐에서 MAX_QUEUE_SIZE 만큼원소가삽입되면? -> 큐가 full이된다. (issempty(), isfull() 동시에참인경우도있다 ) 해결 - 배열을원형으로만들고원형배열에데이터를저장한다. - 초기값 front와 rear는 0으로만든다 (-1이아님 ) 두값이같으면 empty 이다. - front 변수는 ( 큐의처음값위치에서 1을뺀값이다 ) - rear 변수는 ( 큐의마지막값위치 ) 를가리킴 - 최대 MAX_QUEUE_SIZE 1 개를저장한다.(MAX_QUEUE_SIZE 가아님!!) 26

27 원형큐의예 [ 비어있는큐 ] [2] [3] [2] [3] [2] [3] J2 J3 [1] [4] [1] J1 [4] [1] J7 [4] [0] front = 0 [5] [0] front = 0 [5] [0] J6 J5 front = 4 [5] rear = 0 rear = 3 rear = 1 비어있는큐와 3 개가삽입된큐의상태 27

28 [Full 큐 ] [Full 큐 ] [2] [3] [2] [3] J2 J3 J8 J9 [1] J1 J4 [4] [1] J7 [4] [0] J5 J6 J5 [5] [0] front = 0 rear = 5 front = 4 rear = 3 [5] Full 원형큐 28

29 원형큐구현에주의할점 -insert 연산후 rear 의값 *rear = (*rear +1) % MAX_QUEUE_SIZE ; -delete 연산후 front 의값 front = (front +1) % MAX_QUEUE_SIZE ; 29

30 원형큐구현 원형큐의삽입 add() void add(int front, int *rear, element item) { *rear = (*rear + 1) % MAX_QUEUE_SIZE; if(front == *rear) { queue_full(rear); /* reset rear and print error */ return; } queue[*rear] = item; } 30

31 원형큐의삭제 delete () element delete(int *front, int rear) { /* remove front element from the queue and put it in item */ element item; if(*front == rear) return queue_empty(); /*queue_empty returns an error key*/ *front = (*front + 1) % MAX_QUEUE_SIZE; return queue[*front]; } 31

32 원형큐구현 - 정리 - full 큐와 empty 큐의구별방법 (1가지를선택하여실천한다.) 방법 1 : 최대 MAX_QUEUE_SIZE 1 만저장한다 (front==rear+1 이면 full) (MAX_QUEUE_SIZE가아님 ) 방법 2 : 변수를추가하여두상태를구별한다,( 데이터개수 n을항상계산한다.) - 큐를유지하기위해데이터이동이불필요해진다. queue: O(n) - circular queue: O(1) ( 생각할점 ) front 와 rear 의초기값을 -1 로하면무슨문제가생기는가? 32

33 Review 리스트는가장많이사용되는자료의형태이다. 리스트자료에대한연산은검색과변경이다. 변경은삽입과삭제연산을말한다. 스택은리스트의특별한형태로삽입과삭제가한쪽끝에서만일어난다. 마치문이한개인관광버스에손님들을타고내릴때, 먼저탄사람이맨나중에내리는것과같은구조이다 (First In Last Out). 다시말하면맨나중에탄사람이맨먼저내리는구조이다 (Last in First Out, LIFO). 큐또한리스트의특별한형태로삽입과삭제가한쪽끝에서만일어난다. 삽입과삭제는서로반대쪽에서일어나는것이스택과다르다. 문이두개인마을버스의타는곳과내리는곳이따로있어서먼저탄사람이먼저내리게되는구조이다 (First In First Out, FIFO). 스택과큐는이렇게리스트의특별한형태이지만많이쓰이는자료구조이다. 스택과큐는배열을이용하여구현할수있다. 큐를구현할때는일반배열을사용하면자료를이동해야하는불편함이있어서일반배열을원형으로만들어서원형배열을이용하여구현한다. 33