스택(Stack)

스택(Stack)

LIFO구조(후입선출) : 마지막에 들어온 데이터가 먼저 나가는 구조

(Last In First Out)

 

* 주 연산

- pop(값)

- pop()

- peek() : 스택의 가장 마지막으로 들어온 값 반환

- contains(값) : 스택 안 값의 존재 유무(있으면 true, 없으면 false 반환)

- empty() : 비어있는지 유무(비어있으면 true, 하나라도 있다면 false 반환)

- clear() : 모두 삭제

---

실습 코드

// 선형 자료구조 - 스택

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);

        System.out.println(stack.pop());
        System.out.println(stack);

        System.out.println(stack.pop());
        System.out.println(stack);

        System.out.println(stack.peek());
        System.out.println(stack);

        System.out.println(stack.contains(1));
        System.out.println(stack.size());

        // 비어있는지 유무. 비어있으면 true, 하나라도 있으면 false
        System.out.println(stack.empty());

        // 스택 안의 데이터 모두 삭제
        stack.clear();
        System.out.println(stack);

    }

}

---

ArrayList를 이용한 스택 구현

// Practice1
// ArrayList 를 이용한 스택 구현

import java.util.ArrayList;

class MyStack1 {
    ArrayList list; // list 변수

    // 위 객체를 생성할 때 기본 생성자 MyStack1이 자동으로 호출되면서
    // list에 ArrayList가 할당되고 있는 상황
    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);
    }

    // 데이터가 더이상 없을 때는 pop되지 않도록 예외 기능 역시 구현하기
    public Integer pop() {
        if(this.isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }
        // list의 최대사이즈 -1 부분을 인덱스로 해서 get을 하면
        // list의 가장 끝을 가져올 수 있음
        // * 제너릭(Generic): 데이터 타입을 일반화한다는 것을 의미
    //    오류 원인: ArrayList가 제너릭하게 되어있지 않아서 형변환을 한번 해줘야 함
    //    int data = this.list.get(this.list.size() - 1);
        // pop으로 돌려줄 데이터
        int data = (int)this.list.get(this.list.size() - 1);
        // pop을 시키면 스택 자료구조에서 해당 데이터를 제거해주어야 함.
        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.isEmpty();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.printStack();               // 1, 2, 3, 4, 5

        System.out.println(myStack.peek()); // 5
        myStack.printStack();               // 1, 2, 3, 4, 5

        System.out.println(myStack.pop());  // 5
        System.out.println(myStack.pop());  // 4
        myStack.printStack();               // 1, 2, 3

        System.out.println(myStack.pop());  // 3
        System.out.println(myStack.pop());  // 2
        System.out.println(myStack.pop());  // 1
        myStack.printStack();
    }
}

---

배열을 이용한 기본 스택 직접 구현

// Practice2
// 배열을 이용한 기본 스택 직접 구현

class MyStack2 {
    int[] arr;
    int top = -1; // 아무것도 없다는 뜻

    MyStack2(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        if (this.top == -1) {
            return true; // 비어있으면 true
        } else {
            return false; // 하나라도 있다면 false
        }
    }

    // ArrayList와 다르게 사이즈가 고정되어 있다는 점
    public boolean isFull() {
        if (this.top == this.arr.length - 1) { // 마지막까지 데이터가 들어있는 것
            return true;
        } else {
            return false;
        }
    }

    public void push(int data) {
        if (this.isFull()) { // 스택의 공간의 꽉 찼는지 부터 체크
            System.out.println("Stack is full!");
            return;
        }
        this.top += 1; // 꽉 안찼으면 top에 1을 증가시켜줌
        this.arr[this.top] = data; // top 위치에 데이터 할당
    }

    public Integer pop() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }
        int data = this.arr[this.top]; // 가장 마지막에 들어온 데이터 위치
        this.top -= 1;
        return data;
    }

    public Integer peek() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }
        return this.arr[this.top];
    }

    public void printStack() {
        for (int i = 0; i < this.top + 1; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

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

        System.out.println(myStack.peek()); // 5
        myStack.printStack();               // 1, 2, 3, 4, 5

        System.out.println(myStack.pop());  // 5
        System.out.println(myStack.pop());  // 4
        myStack.printStack();               // 1, 2, 3

        System.out.println(myStack.pop());  // 3
        System.out.println(myStack.pop());  // 2
        System.out.println(myStack.pop());  // 1
        myStack.printStack();
    }
}