[Data Structure] Stack & Queue

Stack

LIFO(Last In First Out) : 후입선출

나중에 들어간 데이터가 먼저 나오는 구조이다.

 

Stack 구현에 필요한 프로퍼티와 메서드

필요에 따라 여러 가지 메서드가 추가가 될 수 있겠지만, stack 자료구조에서 빠질 수 없는 메서드는 push와 pop이다.

 

▶ 프로퍼티

storage : 데이터 저장

top : 최상위에 있는 데이터의 Index

 

▶ 메서드

push() : 데이터 삽입

pop() : 데이터 추출

next() : 다음에 pop() 할 경우 나올 데이터 출력

count() : storage에 저장되어 있는 데이터 개수 출력

clear() : storage 초기화

print() : storage 출력

구현

Pseudoclassical Style

function Stack(){
    this.storage = {}
    this.top = 0
}
Stack.prototype.push = function(data){
    this.storage[this.top++] = data
}
Stack.prototype.pop = function(){
    let value = this.storage[this.top-- - 1]
    delete this.storage[this.top]
    return value
}
Stack.prototype.next = function(){
    return this.storage[this.top - 1]
}
Stack.prototype.count = function(){
    return this.top
}
Stack.prototype.clear = function(){
    this.storage = {}
    this.top = 0
}
Stack.prototype.print = function(){
    return this.storage
}

var stack = new Stack()

stack.push(10)
stack.push(20)
stack.push(30)
stack.print()		// {0: 10, 1: 20, 2: 30}

stack.pop()		// 30
stack.print()		// {0: 10, 1: 20}

stack.next()		// 20

Class

class Stack{
    constructor(){
        this.storage = {}
        this.top = 0
    }
    push(data){
        this.storage[this.top++] = data
    }
    pop(){
        let value = this.storage[this.top-- - 1]
        delete this.storage[this.top]
        return value
    }
    next(){
        return this.storage[this.top - 1]
    }
    count(){
        return this.top
    }
    clear(){
        this.storage = {}
        this.top = 0
    }
    print(){
        return this.storage
    }
}

var stack = new Stack()

stack.push(10)
stack.push(20)
stack.push(30)
stack.print()		// {0: 10, 1: 20, 2: 30}

stack.pop()		// 30
stack.print()		// {0: 10, 1: 20}

stack.next()		// 20

---

Queue

FIFO(First In First Out) : 선입선출

처음에 들어간 데이터가 먼저 나오는 구조이다.

 

Queue 구현에 필요한 프로퍼티와 메서드

마찬가지로 필요에 따라 여러 가지 메서드를 추가할 수 있겠지만, enqueue와 dequeue는 필수이다.

 

▶ 프로퍼티

storage : 데이터 저장

front : 맨 앞에 위치한 데이터의 Index

rear : 맨 뒤에 위치한 데이터의 Index

 

▶ 메서드

enqueue() : 데이터 삽입

dequeue() : 데이터 추출

next() : 다음에 dequeue() 할 경우 나올 데이터 출력

count() : storage에 저장되어 있는 데이터 개수 출력

clear() : storage 초기화

print() : storage 출력

구현

Pseudoclassical Style

function Queue(){
    this.storage = {}
    this.front = 0
    this.rear = 0
}
Queue.prototype.enqueue = function(data){
    this.storage[this.rear++] = data
}
Queue.prototype.dequeue = function(){
    let value = this.storage[this.front++]
    delete this.storage[this.front - 1]
    return value
}
Queue.prototype.next = function(){
    return this.storage[this.front]
}
Queue.prototype.count = function(){
    return this.rear - this.front
}
Queue.prototype.clear = function(){
    this.storage = {}
    this.front = 0
    this.rear = 0
}
Queue.prototype.print = function(){
    return this.storage
}

var queue = new Queue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.print()		// {0: 10, 1: 20, 2: 30}

queue.dequeue()		// 10
queue.print()		// {1: 20, 2: 30}

queue.next()		// 20

Class

class Queue{
    constructor(){
        this.storage = {}
        this.front = 0
        this.rear = 0
    }
    enqueue(data){
        this.storage[this.rear++] = data
    }
    dequeue(){
        let value = this.storage[this.front++]
        delete this.storage[this.front - 1]
        return value
    }
    next(){
        return this.storage[this.front]
    }
    count(){
        return this.rear - this.front
    }
    clear(){
        this.storage = {}
        this.front = 0
        this.rear = 0
    }
    print(){
        return this.storage
    }    
}

var queue = new Queue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.print()		// {0: 10, 1: 20, 2: 30}

queue.dequeue()		// 10
queue.print()		// {1: 20, 2: 30}

queue.next()		// 20

 

 

※ 잘못된 부분이나 수정해야 할 부분이 있다면 댓글에 남겨주세요~ 바로 반영하도록 하겠습니다!