관리 메뉴

don't stop believing

Queue - 큐 본문

Golang/Basic

Queue - 큐

Tongchun 2019. 5. 15. 19:05

Stack과 대비되는 Queue 입니다.

Queue에서는 FIFO(First-In, First-Out)의 개념을 가지고 있습니다.

 

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

 

Queue (abstract data type) - Wikipedia

Representation of a FIFO (first in, first out) queue In computer science, a queue is a collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear te

en.wikipedia.org

아래 Go로 구현된 코드는 선형 큐 입니다.

package main

import "fmt"

// QueueItem 구조체
type QueueItem struct {
	item interface{} // 아이템의 값을 가지고 있습니다.
	prev *QueueItem  // 이전 아이템 구조체를 가지고 있습니다.
}

// Queue 구조체
type Queue struct {
	current *QueueItem // 현재 QueueItem을 가지고 있습니다.
	last    *QueueItem // 가장 마지막 QueueItem을 가지고 있습니다.
	depth   uint64     // 아이템이 몇개가 있는지를 저장합니다.
}

// Queue를 생성합니다.
func New() *Queue {
	var queue *Queue = new(Queue)

	queue.depth = 0

	return queue
}

// 새로운 아이템을 Queue에 저장합니다.
func (queue *Queue) Enqueue(item interface{}) {
	if queue.depth == 0 {
		queue.current = &QueueItem{item: item, prev: nil}
		queue.last = queue.current
		queue.depth++
		return
	}

	q := &QueueItem{item: item, prev: nil}
	queue.last.prev = q
	queue.last = q
	queue.depth++
}

// Queue에서 가장 오래전(처음) 저장된 아이템을 제거합니다.
func (queue *Queue) Dequeue() interface{} {
	if queue.depth > 0 {
		item := queue.current.item
		queue.current = queue.current.prev
		queue.depth--

		return item
	}

	return nil
}

func main() {
	var queue *Queue = New()

	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	queue.Enqueue(4)
	queue.Enqueue(5)

	// 가장 오래전 들어간 데이터가 가장 먼저 나옵니다. (FIFO)
	for i := 1; i < 6; i++ {
		item := queue.Dequeue()

		if item != i {
			fmt.Println("TestQueue failed...", i)
		}

		fmt.Println("Dequeue value :", item)
	}
}

로그 데이터의 처리 등 Stack보다는 더 많이 사용되는 것 같습니다.

 

'Golang > Basic' 카테고리의 다른 글

Queue - 큐  (0) 2019.05.15
Stack - 스택  (0) 2019.05.15
Binary Search Tree - 이진 탐색 트리  (0) 2019.05.15
Doubly Linked List - 이중 연결 리스트  (0) 2019.05.13
Binary Search - 이진 검색  (0) 2019.05.13
Jump Point Search - 점프 포인트 서치 (블록 탐색)  (0) 2019.05.13
0 Comments
댓글쓰기 폼