스택(Stack) 알고리즘(JAVA)



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

- 선형 구조 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


'JAVA > 알고리즘' 카테고리의 다른 글

Codility 간략 소개  (1) 2016.04.17
[JAVA] 소수 구하기 + 실행시간 단축  (1) 2015.12.10
선형 큐(Linear Queue)  (0) 2015.10.28
스택(Stack) 알고리즘(JAVA)  (0) 2015.10.27

Tags

Read Next

*

*