728x90
반응형

- FIFO - First In First Out(선입선출)

- 인큐(EnQueue)를 통해 자료 입력, 디큐(DeQueue)을 통해 자료 출력


* 매표소, 가장 먼저 줄서있는 사람에게 표를 먼저 제공한다.



* 선형 큐 알고리즘은 Rear가 배열의 끝에 닿아 있으면, 앞에 배열의 빈 부분(Q[0])이 남아 있어도 더이상 삽입연산을 하지 못한다.

메모리를 효율적으로 관리하지 못함. 이러한 문제점을 해결하기 위해 원형 큐가 만들어졌다.


JAVA 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.io.InputStream;
import java.util.Scanner;
 
public class Queue {
    
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    //Queue 생성
    public Queue(int maxSize){
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }
    
    //Queue 비었는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
    
    //Queue 꽉 찼는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
    
    //Queue에 item 입력
    public boolean enqueue(Object item){
        if(full()){
            System.out.println("Queue is FULL!!");
            return false;
        }
        queueArray[++rear] = item;
        return true;
    }
 
    //Queue 가장 먼저들어온 데이터 출력
    public Object dequeue(){
        if(empty()){
            System.out.println("Queue is EMPTY!!");
            return null;
        }else{
            Object item = queueArray[front];
            queueArray[front] = null;
            front++;
            return item;
        }
    }
    
    //Queue 출력
    public void printQueue(Queue queue){
        if(!empty()){
            for(int i = 0; i<maxSize; i++ ){
                if(queue.queueArray[i] == null){
                    System.out.print("|\t\t");
                }else{
                    System.out.print("|\t"+ queue.queueArray[i]+ "\t");
                }
            }
            System.out.println(" |");
        }else{
            System.out.println("큐 비어있음");
        }    
    }
    
    public static void main(String[] args) {
 
        InputStream a = System.in;
        Scanner sc = new Scanner(a);
        
        System.out.println("큐 SIZE 입력 : ");
        int size = sc.nextInt();
        Queue arrayQueue = new Queue(size); //create queue
        
        boolean flag = true;
        
        while(flag){
            menu();
            String s = sc.next();
            switch(s){
            case "1":
                System.out.print("ENQUEUE : ");
                String data = sc.next();
                arrayQueue.enqueue(data);
                break;
            case "2":
                System.out.println("DEQUEUE : " + arrayQueue.dequeue());
                break;
            case "3":
                arrayQueue.printQueue(arrayQueue);
                break;
            case "q":
            case "Q":
                flag = false;
                break;
            }
        }
    }
    public static void menu(){
        System.out.println("1. enQueue");
        System.out.println("2. deQueue");
        System.out.println("3. QUEUE");
        System.out.println("Q. 종료");
    }
}
cs



출처: http://hahahoho5915.tistory.com/11?category=653539 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지

'Web Programming > java-jsp' 카테고리의 다른 글

Codility 자바 코딩실력 검증  (0) 2018.08.29
java 소수 구하기 + 실행시간 단축  (0) 2018.08.29
java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
728x90
반응형

- 제한적으로 접근할 수 있는 나열 구조(접근 방법은 언제나 목록의 끝에서만 가능)

- 선형 구조 LIFO - Last In First Out(후입선출)

- 푸쉬(push)를 통해 자료 입력, 팝(pop)을 통해 자료 출력


* 프링글스, 통 안에 가장 나중에 들어간(push) 감자칩부터 먹게 된다(pop).



스택 활용 예

- 역순 문자열 만들기

- 수식 괄호 검사

- 수식 후위표기법으로 변환, 후위표기 수식의 연산


JAVA 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.InputStream;
import java.util.Scanner;
 
public class Stack {
 
    private int top;
    private int maxSize;
    private Object[] stackArray;
 
    //스택 생성, 스택의 최대 크기로 생성
    public Stack(int maxSize){
        this.maxSize = maxSize;
        this.stackArray = new Object[maxSize];
        this.top = -1; //top은 -1로 초기화
    }
    
    //스택이 비어있는지 체크
    public boolean empty(){
        return (top == -1);
    }
    
    //스택이 꽉 찼는지 체크
    public boolean full(){
        return (top == maxSize-1);
    }
    
    // 스택에 item 입력
    public boolean push(Object item){
        if(full()){    
            System.out.println("Stack is FULL!!");
            return false;
        }    
        stackArray[++top] = item;
        return true;
    }
    
    // 스택의 가장 위의 데이터 제거
    public Object pop(){
        if(empty()){
            System.out.println("Stack is empty!!");
            return null;
        }else{
            Object item = stackArray[top];
            stackArray[top] = null;
            top--;
            return item;
        }
    }
 
    //스택 출력
    public void printStack(Stack stack){
        if(top != -1){
            for(int i = top; i<=top; i-- ){
                if(i == -1)
                    break;
                System.out.println("| "+ stack.stackArray[i] +" |");
                System.out.println("------");            
            }        
        }else{
            System.out.println("스택 비어있음!");
        }    
    }
    
    public static void main(String[] args) {
 
        InputStream a = System.in;
        Scanner sc = new Scanner(a);
 
        System.out.println("스택 SIZE 입력 : ");
        int size = sc.nextInt();
        Stack arrayStack = new Stack(size); //create stack
        
        boolean flag = true;
        
        while(flag){
            menu();
            String s = sc.next();
 
            switch(s){
            case "1":
                System.out.print("PUSH : ");
                String data = sc.next();
                arrayStack.push(data);
                break;
            case "2":
                System.out.println("POP : " + arrayStack.pop());
                break;
            case "3":
                arrayStack.printStack(arrayStack);
                break;
            case "q":
            case "Q":
                flag = false;
                break;
            }
        }
    }
    public static void menu(){
        System.out.println("1. push");
        System.out.println("2. pop");
        System.out.println("3. STACK");
        System.out.println("Q. 종료");
    }
}
cs



출처: http://hahahoho5915.tistory.com/10?category=653539 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지
728x90
반응형

- 리스트 가운데서 하나의 원소를 고름(pivot 선정)

- pivot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 리스트를 둘로 분할한다.

- 분할된 두 개의 리스트에 대해 재귀함수를 통해 이 과정을 반복한다.

- 시간복잡도 : 최악 O(n^2), 평균 O(nlogn)




JAVA 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Quick {
    
    public void sort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];
        
        do{
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);
        
        if(l < right) sort(data, l, right);
        if(r > left) sort(data, left, r);
    }
    
    public static void main(String[] args) {
        
        int data[] = {66, 10, 1, 34, 5, -10};
        
        Quick quick = new Quick();
        quick.sort(data, 0, data.length - 1);
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] : "+data[i]);
        }
    }
}
cs



출처: http://hahahoho5915.tistory.com/9?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지

'Web Programming > java-jsp' 카테고리의 다른 글

java 소수 구하기 + 실행시간 단축  (0) 2018.08.29
java 선형 큐(Linear Queue)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
728x90
반응형

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.

- 배열의 두 번째 데이터 부터 연산을 시작함.

- 시간복잡도 : O(n^2)



[1회전]


[2회전]


[3회전]


[4회전]


JAVA 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Insertion {
 
    public void sort(int[] A){
        int size = A.length;
        int temp = 0;
        int j = 0;
        for(int i = 1; i < size; i++){
            temp = A[i];
            for(j=i-1; j>=0 && temp<A[j]; j--){
                A[j+1] = A[j];
            }
            A[j+1] = temp;
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Insertion insertion = new Insertion();
        
        int A[] = {66, 10, 1, 34, 5};
        
        insertion.sort(A);
        for(int i = 0; i < A.length; i++){
            System.out.println("A["+i+"] : " + A[i]);
        }
    }
}
cs




출처: http://hahahoho5915.tistory.com/8?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지

'Web Programming > java-jsp' 카테고리의 다른 글

java 선형 큐(Linear Queue)  (0) 2018.08.29
java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
java 면접 예상 질문  (0) 2018.08.29
728x90
반응형

두 인접한 원소를 검사하여 정렬하는 방법

- 시간복잡도 : O(n^2)

- 세번의 회전에 걸쳐 정렬은 완료되었지만 프로그램은 남은 데이터의 비교연산을 계속 처리함.

- 정렬은 비교연산을 통해 가장 큰 데이터 부터 끝에 정렬됨.


버블 정렬의 장점

- 구현이 쉽다.

- 이미 정렬된 데이터를 정렬할때 가장 빠르다.


버블 정렬의 단점

- 다른 정렬에 비해 정렬 속도가 느리다.

- 역순배열을 정렬할때 가장 느리다.


JAVA 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Bubble {
    public void sort(int [] data){
        int temp = 0;
        for(int i=data.length-1; i>=0; i--){
            for(int j=0; j<i; j++){
                if(data[j] > data[j+1]){
                    temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }                
            }
        }
    }
    public static void main(String[] args) {
 
        Bubble bubble = new Bubble();
        
        int data[] = {66, 10, 1, 34, 5};
        
        bubble.sort(data);
        
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] : " + data[i]);
        }
    }
}
cs



출처: http://hahahoho5915.tistory.com/6?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지

'Web Programming > java-jsp' 카테고리의 다른 글

java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
java 면접 예상 질문  (0) 2018.08.29
java 동기화, synchronized, wait()-notify() 메서드  (0) 2018.08.29

+ Recent posts

티스토리툴바