티스토리 뷰

자료구조

베니의 자료구조 - 스택 (Stack)

사용자 개발자 베니 2019. 10. 15. 22:51

베니의 자료구조 - 스택(Stack)

베니는 생활코딩 책, 구글링을 통해 자료구조를 공부하고 있습니다.  
인용하는 내용의 출처는 링크를 남겨놓고 있습니다.
도움 주신
하이언님, 이지스퍼블리싱님 감사드립니다!

개발이 하고 싶어요 , Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편

목차

1. 정의

2. 특징

3. 활용

4. 베니의 생각

 

스택은 마치 쌓아놓은  동전과도  같습니다. ( 출처 - pixnio.com )

 


1. 정의

 

스택은 사전적인로 '더미', '쌓아 올림' 이라는 의미를 가지고 있으며
쌓아 올리는 형태를 한 자료구조입니다.

 

2. 특징

    LIFO( Last In First Out )의 구조

     - 데이터 출력 시에 마지막에 들어간 데이터가 가장 먼저 출력이 되는 형태를 가지고 있습니다.

 

3. 활용

    단순 연결 리스트를 이용한 Stack의 구현

   

public class ListStack {

    private Node top; // top은 Stack의 노드 중 최상단의 노드를 의미합니다.
    
    // data와 nextNode가 있는 Node 객체 
    public class Node{
    
    	private Object data;
        private Node nextNode;
        
        Node(Object data){
        	this.data = data;
            this.nextNode = null;
    	}
    }
    
    // 처음 생성 시에는 Stack에 Node가 없으므로 top은 null입니다.
    public ListStack() {
        this.top = null;
    }
    
}

우선 Node 객체를 만들고 최상단 노드를 가리키는 top을 null로 만들어주었습니다.

 

 

(1) EMPTY

public boolean empty(){
    return (top == null); // top에 데이터가 없다는 건 stack에 데이터가 없는 것입니다.
}

먼저 Stack에 데이터가 있는지 체크 하는 empty 함수입니다.

top이 null이라면 데이터가 없는 것이므로 true를 반환하고

데이터가 있다면 false를 반환합니다.

 

(2) PUSH

public void push(Object item){

    Node newNode = new Node(item); // item을 받아 Node 객체를 만들고
    newNode.nextNode = top; // 새로운 노드의 nextNode로 top 노드를 할당합니다.
    top = newNode; // 그리고 top으로 새로운 노드를 할당합니다.
    
}

새로운 object인 item을 Stack의 push를 하는 소스입니다.

새로운 노드를 받아 Stack에 쌓아줍니다.

 

(3) PEEK

public Object peek(){

    // Stack이 비어 있다면 Exception을 발생시킵니다.
    if(empty()){
    	throw new ArrayindexOutOfBoundsException();
    }
    
    return top.data; // top의 데이터를 반환합니다.

}

현재 top의 data가 무엇인지 반환하여 줍니다.

 

(4) pop

public Object pop(){

    Object item = peek(); // top의 데이터를 item으로 받은 후 
    top = top.nextNode; // top에 top의 nextNode를 할당한 후
    return item; // item을 출력합니다.

}

pop 함수는 peek 함수를 통해 top의 데이터를 가져와서 item에 저장을 한 후

top이 top의 nextNode를 가리키게 합니다.

그 후에 출력되는 item 값을 리턴하며 이는 pop을 통해 나온 결과입니다.

 

4. 베니의 생각

Stack은 앞서 진행했던 LinkedList 보다는 내용이 상대적으로 짧은 것 같습니다.
Array로 구현하는 방법과 LinkedList로 구현하는 방법 중 이 글에서는 LinkedList로 구현하였습니다.

다음 수업은 큐를 진행할 예정이며 큐도 스택과 내용의 양이 비슷할 것으로 예상됩니다.
글을 최소 1주일에 1번씩 쓰려고 하는데 이것도 일하면서 하기가 쉽지가 않은 것 같습니다. ㅜㅜ
화이팅하겠습니다!

글에 대한 피드백은 언제든지 감사합니다!

TODO
- 큐(Queue)
 
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
243
Today
0
Yesterday
0
링크
«   2020/02   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
글 보관함