티스토리 뷰

자료구조

베니의 자료구조 - 큐 (Queue)

사용자 개발자 베니 2019. 10. 22. 21:53

베니의 자료구조 - 큐 (Queue)

 

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

Heee's Development Blog

 

우리는 이미 터널을 지나갈 때 Queue를 경험하였습니다. ( 출처  - https://www.pexels.com/ko-kr/photo/1174177/ )

 

목차

1. 정의

2. 특징

3. 활용

4. 베니의 생각

 

 

 

1. 정의

Queue는 표 같은 것을 구매하기 위해 줄서는 것을 의미하며
선입선출 구조의 자료구조이다.

2. 특징

 FIFO( First In First Out )의 구조

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

 

 

3. 활용

 

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

 

public class MyQueue {

    // Queue에서 객체로 사용될 노드의 구현
    public class QueueNode {

        private T data;
        private QueueNode nextNode;

        public QueueNode(T data){
            this.data = data;
        }
    }
	
    private QueueNode first;	// 데이터가 출력되는 가장 앞의 위치입니다.
    private QueueNode last;  // 데이터가 삽입되는 가장 뒤의 위치입니다.
    
 
}

클래스에서 사용될 변수, Node, 생성자의 선언을 마쳤습니다.

이제 Queue를 사용하는데 필요한 기능들을 구현해보겠습니다.

 

(1) isEmpty()

 

public boolean empty(){
    return (first == null); // front에 null이라면 곧 Queue에 객체가 없는 것을 의미합니다.
}

 

(2) add

public void add(T item) {
    QueueNode t = new QueueNode(item); // 새로운 노드를 받아서
    
    if(last != null) last.next = t; // 기존에 노드가 있을 때 last의 next에 새로운 노드를 할당합니다
    last = t;	// last에도 새로운 노드를 할당합니다.
    if (first == null) first = last; // first가 null이 아닐 때 last를 first에 할당합니다.
}

 

(3) remove

// 큐의 remove는 데이터 출력과 삭제가 함께 이루어집니다.
public T remove() {
    // 큐에 데이터가 없을 시 Exception을 활성화합니다.
    if(first == null) throw new NoSuchElementException(); 
    T data = first.data;	// first의 데이터를 data에 할당 후
    first = first.next;		// first의 next를 first로 할당합니다.
    						// 그러면 기존 first.data는 first.next.data로 변경되며 없어집니다.
                            
    if(first == null) last = null; // first에 값이 비었다면 last도 데이터가 없습니다.
    return data; // 삭제한 데이터를 리턴합니다.
}

 

(4) peek

public T peek() {
	// first가 null 일 때는 반환할 값이 없으므로 예외처리를 합니다.
	if (first == null) throw new NoSuchElementException();
    return first.data; // 가장 첫번째 데이터를 반환합니다.
}

 

4. 베니의 생각

오늘도 간단하게 큐에 대해서 살펴보았습니다.
단순 연결리스트를 통해 구현하였고 add에서 last와 last.next 둘 다 t를 할당하는 부분이
last.next에는 왜 할당하는지 이해가 되지 않았습니다. 하나의 큐 객체로 생각하고 구현이 된 것일까요..?

블로그를 조금 더 가독성 있고 읽기 쓰기 쉽게 쓰기 위해서 조금씩 글마다 변화를 주고 있습니다.
어느정도 가독성이 좋은 글이 됬다는 생각이 든다면 블로그 글 전체의 폼을 하나로 통일하려고 합니다!

다음에는 트리에 대해 공부를 해보려고 하는데 트리가 처음 접할 때 워낙 양이 방대하다고 느껴져
아마 글이 여러개가 되지 않을까 예상해봅니다 ㅎㅎ..

가독성과 내용이 아직 좋다고 느껴지지는 않지만 봐주셔서 감사하며 더 좋은 글이 되기 위해
발전하는 베니가 되도록 하겠습니다. 감사합니다!

TODO
- 트리(Tree)

댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
317
Today
0
Yesterday
1
링크
«   2020/06   »
  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 30        
글 보관함