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

자료구조 스택(Stack) 

스택(Stack)의 개념

스택(Stack)이란 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료구조(Structure)입니다.

 

브라우저에서 웹 서핑 중 [뒤로가기] 버튼을 누르면 가장 마지막에 들어갔던 페이지로 이동하게되죠. 이것을 예시로 이해하시면됩니다.

 

스택(Stack)의 연산

1. 삭제 pop() : 스택에서 가장 위에 있는 항목을 꺼낸다.
2. 삽입 push(item) : item을 스택의 가장 위에 추가한다.
3. 읽기 peek() : 스택의 가장 위에있는 항목을 반환한다.
4. 비어있는지 확인 isEmpty() : 스택이 비어있을 때 true를 반환한다.

 

스택(Stack)의 구현

프로그래밍은 문제의 종류에 따라 적합한 방법을 찾아 코딩합니다. 때문에 어떠한 문제냐에 따라 배열에 저장하는 것보다 스택을 사용하여 저장하는 것이 적합한 방법일 수 있습니다.

• 배열은 동적 자료구조가 아니기 때문에 원소들을 하나씩 옆으로 밀어주어야 되는 반명 스택은 동적으로 작용한다. 등등의 이유

스택(Stack)은 배열, 연결리스트로 구현할 수 있습니다.

//연결 리스트로 사용 할 노드 class
public class Node {

	private Object data;
	private Node nextNode;

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

	//해당 노드를 원하는 노드(Node top)와 연결해주는 메소드
	public void linkNode(Node top){
		this.nextNode = top;
	}

	//해당 노드의 데이터를 가져오는 get메소드
	public Object getData(){
		return this.data;
	}

	//해당 노드와 연결된 노드를 가져오는 get메소드
	public Node getNextNode(){
		return this.nextNode;
	}
}

연결리스트는 노드로 구성되어 있으며 노드는 데이터와 다음 노트를 가르키는 주소로 구성되어있습니다.

 

Node Class의 코드를 보면 프로퍼티로 data와 nextNode가 있습니다. linkNode(Node top) 메서드를 통해 자신의 nextNode 프로퍼티에 인자로 받은 top 노드를 주입합니다. 이로써 자신과 top 노드를 연결됩니다. 

 

 

아래는 연결리스트로 구현된 스택입니다.

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();
        else{
            Object item = peek();
            top = top.getNextNode();
            return item;
        }
    }
}

① push(Object item) 메서드에서 새로운 노드를 생성합니다. Node newNode = new Node(item);

 

② 만들어진 노드를 linkNode(Node top) 메서드를 활용해 만들어진 노드와 기존에 노드랑 연결해줍니다. newNode.linkNode(top);

 

③ 마지막으로 새로운 노드가 가장 앞에 있으니 top으로 표시를 해줍니다. newNode.linkNode(top);

 

pop()은 지울 데이터를 반환하고 top의 위치를 이전 노드로 표시해줍니다. top = top.getNextNode();

 

public class main {

	public static void main(String[] args) {

		ListStack stackL = new ListStack();

		stackL.push(5);
		stackL.push("Hi");
		stackL.push("again");
		stackL.push("Monsieur Songsong");
        
		while(!stackL.isEmpty()){
			System.out.println(stackL.pop());
		}
	}
}

배열, 연결리스트 각각의 장단점이 있습니다. 배열은 데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리합니다. 반대로 연결리스트는 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리합니다.