[JAVA]선형자료구조 Stack, Arraylist를 통해 Stack 구현하기, Stack 연산

스택(stack)

후입선출(Last in First Out) 자료구조

- 마지막에 들어온 데이터가 먼저 나가는 구조

 

데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용

ex. 함수 콜 스택, 수식 계산, 인터럽트 처리 등

 

기본구조

 

 

 

기본연산

 

-데이터 추가(Push):

스택의 가장 마지막 위치에 데이터 추가

 

-데이터 꺼내기(Pop):

 

 

 

ArrayList를 통해 직접 스택 구현하기:

 

import java.util.ArrayList;

class myStack1{
    ArrayList list;

    myStack1(){
        this.list = new ArrayList();
    }
    public boolean isEmpty(){
        if(this.list.size() ==0){
            return true;
        }else{
            return false;
        }
    }

    public void push(int data){
        this.list.add(data);
    }

    public Integer pop(){
        if(this.isEmpty()){
            System.out.println("Stack is empty");
            return null;

        }
        int data = (int)this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
    }

    public Integer peek(){
        if(this.isEmpty()){
            System.out.println("Stack is empty");
            return null;

        }
        int data = (int)this.list.get(this.list.size()-1);
        return data;
    }

    public void printStack(){
        System.out.println(this.list);
    }


}
public class Practice1 {
    public static void main(String[] args){
    //Test code
        myStack1 myStack = new myStack1();
        System.out.println(myStack.isEmpty());
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.printStack();

        System.out.println(myStack.peek());
        myStack.printStack();

        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        myStack.printStack();
    }
}

 

Java에서는 stack 인터페이스를 제공하기에, 바로 import도 가능하다!

 

stack을 import해 문자열 뒤집기 예제를 실행하였다.

import java.util.Stack;

//문자열 뒤집기
public class Practice1 {
    public static String reverseString(String str){
        Stack stack = new Stack();
        String result = "";

        for (String s: str.split("")){
            stack.push(s);
        }
        while (!stack.isEmpty()){
            result = result + stack.pop();
        }
        return result;
    }

    public static void main(String[] args) {
        //Test code
        String result = reverseString("Hello");
        System.out.println("result = " +result);
        
        result = reverseString("1 3 5 7 9");
        System.out.println("result = " + result);
    }
}

 

 

스택의 주요연산

 

연산
push()	데이터를 삽입한다.
pop()	가장 나중에 들어온 데이터를 삭제한다.
imEmpty()	boolean형태로 스택이 비었는지 확인한다.
isFull()	boolean형태로 스택이 꽉차있는지 확인한다.

 

 

---

 

오늘 푼 문제

 

백준 25556번 : 포스텍 , 스택 문제임

import java.util.Scanner;
import java.util.Stack;

public class backjoon {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n;
        String str_tmp;
        String[] str = {}; //String 타입을 넣을 수 있는 배열 만들어주기
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> stack3 = new Stack<>();
        Stack<Integer> stack4 = new Stack<>();
        int result = 1;

        System.out.println("순열 길이 N을 입력하세요: ");
        n = Integer.parseInt(sc.nextLine());
        System.out.println("순열 A의 원소를 공백을 이옹해 입력하세요: ");
        str_tmp = sc.nextLine();
        str = str_tmp.split(" ");

        for (int i = 0; i < n; i++) {
            if (stack1.empty() || stack1.peek() < Integer.parseInt(str[i])){
                stack1.push(Integer.parseInt(str[i]));
            } else if (stack2.empty() || stack2.peek() < Integer.parseInt(str[i])) {
                stack2.push(Integer.parseInt(str[i]));
            } else if (stack3.empty() || stack3.peek() < Integer.parseInt(str[i])) {
                stack3.push(Integer.parseInt(str[i]));
            } else if (stack4.empty() || stack4.peek() < Integer.parseInt(str[i])) {
                stack4.push(Integer.parseInt(str[i]));
            } else {
                result =0;
            }

        }

        if(result == 0){
            System.out.println("NO");
        }else{
            System.out.println("YES");
        }

    }
}

 

---

 

Scanner를 호출하는 것은 이제 조금 익숙해져, 드디어 변수에 값을 넣을 때 scanner를 불러올 수 있게 되었다.

위의 문제를 풀 때, Stack stack = new stack(); 으로 호출하니 stack.peek에서 오류가 났다.

데이터 타입 선언에 유의해서 stack을 사용해야함을 유의할 것!

아직 데이터 타입 선언을 해야하는지 안해야하는지에 대한 이해가 낮다.

문제를 푸는 과정에서 오류가 나면 데이터 타입을 하지 않아서 인지를 먼저 확인해야겠다.