[알고리즘] 2.1. 자료구조 : 연결리스트 기반 스택(Stack) 구현

  개요

스택이 무엇인지, 어디에 사용하고 무엇으로 만드는지에 대한 전체적인 내용은 이전 게시물을 참고하시면 됩니다.

스택 이해하기

연결리스트 기반 스택의 프로퍼티(속성) 으로는 top(데이터 삽입/삭제하는 위치), Node(스택을 구성하는 요소)로 구성되어 있습니다. 메쏘드(함수)로는 pop(삭제), push(삽입), peek(탐색)이 있고, 부수적인 함수로는 isEmpty(스택이 비어있는지 확인)가 있습니다. 

  구현

//연결 리스트로 사용 할 노드 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)이 있고, getData()와 getNextNode()는 private으로 설정된 프로퍼티의 값을 외부에서 가져오기 위해 구현하였습니다. 

주요 메쏘드는 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);

그 후에 할 일은 새로만든 노드와 이전의 노드와 연결만 해주면 되겠지요? newNode.linkNode(top);

마지막으로 top = newNode; 는 새로운 노드가 가장 앞에 있으니 top으로 표시를 하는 것입니다. 

pop()은 백업용도로 지울 데이터를 반환하고, top(head)의 위치를 이전 노드로 표시만 해주면 됩니다. 그림으로 이해하면, 원래 4를 갖는 노드를 지우려고 합니다. head는 원래 4를 가리키고 있었지만, 이 노드는 지울것이므로 head를 지울 다음노드(3)를 가리키게 하면 됩니다.  top = top.getNextNode(); 여기서 조금 헷갈릴 수 있는데 오른쪽 항의 top은 지울 노드를 가리킵니다. 즉, 지울 노드의 getNextNode()는 지울 노드의 이전 노드를 말합니다. 이제 top은 지울 노드의 이전 노드를 가리키게 되는거죠. 

public class main {

public static void main(String[] args) {

//array를 사용한 스택과 사용방법이 같다.

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());

}

}

}