untitled

Size: px

Start display at page:

Download "untitled"

태우 곽
7 years ago
Views:

3 - -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front)

5 A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top

7 #define MAX_STACK_SIZE 100 int stack[max_stack_size]; int top = -1; /* top 1. */

8 void push(int item) { if(top >= MAX_STACK_SIZE - 1) { stack_full(); return; } stack[++top] = item; }

9 int pop( ) { if(top == -1) return stack_empty(); return stack[top--]; }

10 int isempty() { if( top < 0 ) return(1); else return(0); } int isfull() { if ( top >= MAX_STACK_SIZE 1 ) return(1); else return(0); }

11 #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 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 // Stack.java // to run this program: C>java StackApp 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--]; // access item, 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

14 //////////////////////////////////////////////////////////////// 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

15 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

16 #define MAX_QUEUE_SIZE 100 typedef struct { int key; /* other fields */ } element; element queue[max_queue_size]; int rear = -1; int front = -1;

17 void insert(int *rear, element item) { if(*rear == MAX_QUEUE_SIZE - 1) { queue_full(); /*? */ return; } queue[++*rear] = item; }

18 element delete(int *front, int rear) { if(*front == rear) return queue_empty(); /* return an error key */ return queue[++*front]; }

19 int isempty() { if( front == rear ) return(1); else return(0); } int isfull() { if ( rear == MAX_QUEUE_SIZE 1 ) return(1); else return(0); }

20 front rear Q[0] Q[1] Q[2] Q[3] J1 Job J1 J2 Job J1 J2 J3 Job J2 J3 Job J3 Job 2

21 4. (circular queue)

22 J2 J3 J1 front = 0 front = 0 rear = 0 rear = 3 3

23 [Full ] [Full ] J2 J3 J8 J9 J1 J4 J7 J5 J6 J5 front = 0 rear = 5 front = 4 rear = 3 Full

24 *rear = (*rear +1) % MAX_QUEUE_SIZE ; -delete front front = (front +1) % MAX_QUEUE_SIZE ;

27 - () front rear -1?

28 Review

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

Microsoft PowerPoint - 제4장-스택과큐.pptx 제 4 강의. 스택과큐자료구조 1 제 4 강. 스택과큐자료구조 학습목차 1. 스택과큐자료구조 2. 스택자료구조 3. 큐자료구조 4. 원형큐의구현 2 1. 스택 (Stack) 과큐자료구조 리스트, 스택과큐 (Stack and Queue) 스택과큐는리스트자료구조의특별한경우이다. 리스트 - 순서가있다 - 읽기, 삽입 (insert) 과삭제 (delete) 를리스트의어느곳에서나행함