push와 pop으로 구성된 stack
LIFO
export default class Stack < T > {
private stack : T [ ]
constructor ( ) {
this . stack = [ ]
}
push ( value : T ) {
this . stack . push ( value)
}
pop ( ) : T | undefined {
return this . stack . pop ( )
}
size ( ) : number {
return this . stack . length
}
}
데이터 삽입과 삭제가 서로 반대쪽에서 일어나는 자료구조
FIFO
export default class Queue< T > {
private queue: T [ ]
constructor ( ) {
this . queue = [ ]
}
dequeue ( ) : T | undefined {
return this . queue. shift ( )
}
enqueue ( value: T ) {
this . queue. push ( value)
return this
}
size ( ) {
return this . queue. length
}
}
각 원소들이 우선순위를 가지고 있는 큐
큐에서 무작정 pop이나 shift하는 것이 아니라, 우선순위가 가장 높은 것이 나오는 형태
export type PQItem< T > = { priority: number ; data: T }
export default class PriorityQueue< T > {
private queue: PQItem< T > [ ]
constructor ( ) {
this . queue = [ ]
}
enqueue ( value: PQItem< T > ) {
this . queue. push ( value)
}
dequeue ( ) : PQItem< T > | undefined {
let entry = 0
this . queue. forEach ( ( _, i) => {
const nextIndex = i + 1
if ( ! this . queue[ nextIndex] ) {
return undefined
}
if ( this . queue[ entry] . priority > this . queue[ nextIndex] . priority) {
entry = nextIndex
}
} )
const [ dequeuedItem] = this . queue. splice ( entry, 1 )
return dequeuedItem
}
}
export class Node< T > {
data: T
next: Node< T > | null
constructor ( data: T ) {
this . data = data
this . next = null
}
}
export default class LinkedList< T > {
// TODO
