[자료구조] 자바 스택(Stack)의 클래스 사용하기

스택(Stack)의 특징

1. 먼저 들어간 데이터가 나중에 나오는 후입선출, LIFO (Last In First Out) 구조로, 마트용 음료수 진열대와 같은 구조이다.

2. 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료 구조여서 데이터를 쌓는 형식으로 저장하며 조회, 추가, 삭제 등 모두 가장 위에 있는 (가장 마지막에 삽입된) 값에서 이루어진다. 이 데이터를 Top이라고한다.

3. 그래프(Graph)의 깊이 우선 탐색(DFS)에 사용된다.

4. 재귀적(Recursion) 함수를 호출할 때 사용한다.

스택(Stack) 클래스

선언  

import java.util.Stack;
Stack<Element> stack = new Stack<>();

메서드

public Element push(Element item);	// 데이터 추가
public Element pop();			// 최근에 추가된(Top) 데이터 삭제
public Element peek();			// 최근에 추가된(Top) 데이터 조회
public boolean empty();			// 스택(Stack)의 데이터가 비어있는 지 여부 (비어있으면 true)
public boolean contains(Object o);	// 스택(Stack)의 인자값이 있는 지 여부 (있으면 true)
public int search(Object o);		// 인자값으로 받은 데이터의 위치(순번) 반환 (인덱스 X)

예제 코드

Stack<Integer> stack = new Stack<>();

for(int i=0; i<5; i++) {
	stack.push(i+1);		// 데이터 추가
}	// stack = { 1, 2, 3, 4, 5 }

System.out.println(stack.peek());
stack.pop(); 	// stack = { 1, 2, 3, 4 }
System.out.println(stack.peek());
System.out.println(stack.search(1));
System.out.println(stack.empty());

// output
// 5
// 4
// 4
// false

 

 

 

스택(Stack) 구현 : Array, LinkedList

배열(Array)

예제 코드

public class ArrayStack {

    int top;
    int size;
    int [] stack;

    public UserArrayStack(int size) {
        this.size = size; //
        stack = new int[size];
        top = -1; // top 의 값 초기화
    }

    private void push(int item) {
        stack[++top] = item;
        System.out.println(stack[top] + " push!");
    }

    private void peek() {
        System.out.println(stack[top] + " peek!");
    }

    private void pop() {
        System.out.println(stack[top] + " pop!");
        stack[top--] = 0;
    }

    private int search(int item) {
        for (int i = 0; i <= top; i++) { // for 문은 top 만큼
            if (stack[i] == item)
                return (top - i) + 1; // top - 탐색한 배열의 인덱스, 배열 이므로 +1 추가
        }
        return -1;
    }

    private boolean empty() {
        return size == 0;
    }
    
    private boolean contains(int item) {
        for(int s : stack) {
            if(s == item) return true;
        }
        return false;
    }
}

배열 구현의 장단점

+ 구현이 쉬움

+ 데이터의 접근 속도(조회)가 빠름

-  항상 최대 개수를 정해놔야 사용 가능

링크드리스트(LinkedList)

예제 코드

public class Node {

    private int data;
    private Node nextNode;

    public Node(int data) {
        this.data = data;
        this.nextNode = null;
    }

    protected void linkNode(Node node) {
        this.nextNode = node;
    }

    protected int getData() {
        return this.data;
    }

    protected Node getNextNode() {
        return this.nextNode;
    }
}

public class UserLinkedListStack {

    Node top;

    public UserLinkedListStack() {
        this.top = null;
    }

    private void push(int data) {
        Node node = new Node(data);
        node.linkNode(top);
        top = node;
    }

    public int peek() {
        return top.getData();
    }

    private void pop() {
        if (empty())
            throw new ArrayIndexOutOfBoundsException();
        else {
            top = top.getNextNode();
        }
    }

    private int search(int item) {
        Node searchNode = top;
        int index = 1;
        while(true) {
            if (searchNode.getData() == item) {
                return index;
            } else {
                searchNode = searchNode.getNextNode();
                index ++;
                if (searchNode == null)
                    break;
            }
        }

        return -1;
    }

    private boolean empty() {
        return top == null;
    }
}

링크드 리스트 구현의 장단점

+ 데이터 최대 개수 한정하지 않아도 삽입/삭제가 용이함

- 데이터의 접근 속도(조회)가 힘듦