[자료구조] Stack 개념과 Java 구현 & 사용법 예제

Stack이란?

메모리 안에 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식 중 하나이다. 단어의 의미가 '쌓아서 올린다', '더미'인 것처럼 택배 상자가 쌓이는 모습을 상상하면 되는데 제일 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료구조이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조이다.

 

스택의 예로는 'Ctrl + Z' 즉, 실행 취소를 들 수 있다. 누를 때마다 최근에 한 작업이 실행 취소된다. 그외에는 웹브라우저 뒤로 가기 기능이나 계산기 등이 있다.

 

 

Stack의 주요 기능

1. pop() : 스택에서 가장 위에 있는 항목을 꺼낸다.

2. push(item) : item을 스택의 가장 위에 추가한다.

3. peek() : 스택의 가장 위에 있는 항목을 반환한다.

4. isEmpty() : 스택이 비어있을 때 true를 반환한다.

 

 

Java로 Stack 구현하기

class Stack<T> {
	class Node<T> {
    	private T data;
        private Node<T> next;
        
        public Node(T data) {
        	this.data = data;
            this.next = null;
        }
    }
    
    private Node<T> top;
    
    public T pop() {
    	if (top == null) {
        	throw new EmptyStackException();
        }
        T item = top.data;
        top = top.next;
        return item;
    }
    
    public void push(T item) {
    	Node<T> t = new Node<T>(item);
        t.next = top;
        top = t;
    }
    
    public T peek() {
    	if (top == null) {
        	throw new EmptyStackException();
        }
        return top.data;
    }
    
    public boolean isEmpty() {
    	return top == null;
    }
   
}

public class Main {
	public static void main(String[] args) {
    	Stack<Integer> s = new Stack<Integer>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.pop());
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
    }
}

- Null 일 때 EmptyStackException()으로 예외 처리를 해준다.

 

 

대표적인 스택 구현 방법

1. Array

구현이 상대적으로 쉽지만 input 사이즈를 미리 알아야 한다.

 

public class StackUsingArray {
	private int size;
    private int arr[]
    private top;
    
    public StackUsingArray(int size) {
    	this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }
    
    public boolean isEmpty() {
    	return top == -1;
    }
   
    
    public int peek() {
    	return arr[top];
    }
    
    public void push(int input) {
        arr[++top] = input;
    }
    
    public int pop() {
    	if (isEmpty()) {
        	return -1;
        }
        int value = arr[top];
        top--;
        return value;
    }
}

 

2. LinkedList

구현이 상대적으로 어렵지만 제한된 사이즈로부터 자유롭다.

 

위 자바 구현 코드보다 보기 쉬운 코드 예제 (출처 : https://devmoony.tistory.com/54)

public Class Node {
	
    private Object data;
    private Node next;
    
    public Node(Object input) {
    	this.data = input;
        this.next = null;
    }
    
    // 해당 노드를 원하는 노드와 연결해주는 메소드
    public void linkNode(Node top) {
    	this.next = top;
    }
    
    public Object getData() {
    	return this.data;
    }
    
    public Node getNext() {
    	return this.next;
    }
    
}

public class ListStack {
	private Node top;
    
    public ListStack() {
    	top = null;
    }
    
    public boolean isEmpty() {
    	return top == null;
    }
    
    public void push(Object item) {
    	Node newNode = new Node(item);
        newNode.linkNode(top);
        top = newNode;
    }
    
    public Object(peek) {
    	return top.getData();
    }
    
    public Object pop() {
    	if (isEmpty()) throw new ArrayIndexOutOfBoundsException();
        Object item = peek();
        top = top.getNext();
        return item;
    }
}

 

 

참고

- [자료구조] 스택(Stack)이란 무엇인가? (스택 개념, 연산, 구현)

- 제어문

- 배열을 사용하여 스택 구현 - Java 코드

- [자료구조 알고리즘] Stack 구현하기 in Java