[알고리즘] 스택(Stack)이란 ?

스택(Stack)이란 ?

- 선형 자료구조의 한 종류로써 한쪽 끝에서만 입/출력이 일어나는 자료구조

 

스택의 특징

- LIFO ( Last In First Out) : 가장 나중에 추가된것이 가장 먼저 제거된다.

                                   --> 가장 처음의 추가된것은 가장 마지막에 제거된다.

 

연산의 종류

- pop()    : 가장 위의항목을 제거

- push()   : 가장 위에 Item을 추가

- empty() : 비어있는지 검사

- peek()   : 가장 위의항목을 반환 (아래 구현부에서는 top이라 칭한다)

 

TIP..peek와 pop의 차이점

-> pop은 제거하지만 peek는 제거가 아니다 

ex) 1 2 3 이 차례대로 있는 Stack의 경우 peek를 하면 1 2 3 이 그대로 있지만 pop을 하면 1 2 만 남게된다.

 

스택의 구현

배열로 구현하는방법과 연결리스트로 구현하는 방법이 있다.

이 글에서는 배열로 구현해보도록 하겠다.

import java.util.Scanner;
public class StackMain {
    public static void main(String[] args) {
        Stack stack = new Stack();
        Scanner sc = new Scanner(System.in);
        int commandCnt = 0;
        int value = 0;
        String command = "";

        commandCnt = sc.nextInt();
        sc.nextLine();
        for(int i=0; i<commandCnt; i++){
            command = sc.nextLine();
            sc.nextLine();
            switch (command){
                case "push":
                    value = sc.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    System.out.println(stack.pop());
                    break;
                case "top":
                    System.out.println(stack.top());
                    break;
                case "empty":
                    System.out.println(stack.isEmpty());
                    break;
                case "size":
                    System.out.println(stack.size());
                    break;
            }
        }
    }
}

 

public class Stack{
    private int top = 0;
    private int maxSize = 20;
    private int[] stack = new int[20];

    public int size(){
        return top;
    }
    public int isEmpty(){
        int check = 0;
        if(top == 0){
            check = 1;
        }

        return check;
    }
    public void push(int value){
        if(top >= maxSize){
        }else {
            stack[top++] = value;
        }
    }
    public int pop(){
        int topValue = -1;
        if(top == 0){
        }else{
            topValue = stack[--top];
        }
        return topValue;
    }
    public int top(){
        int topValue = -1;
        if(top == 0){
        }else{
            topValue = stack[top-1];
        }
        return topValue;
    }
}