[자료구조] stack, queue

stack

stack은 FILO(first in last out) 형태의 자료구조입니다. 간단히 엘레베이터를 떠올리면 됩니다. 

마지막에 탄 사람이 처음으로 나가겠죠? 문앞에 있으니 

method	설명
push	새로운 아이템을 추가합니다.
top	마지막에 추가한 아이템을 가르킵니다.
pop	마지막에 추가한 아이템을 꺼냅니다.
empty	스택에 아이템이 더 있는지 확인합니다.

간단히 네 가지 메소드가 있습니다. 여기서 헷갈리는것이 top과 pop의 차이입니다.

간단히 말하면 pop은 마지막 아이템을 리턴하고 stack에서 제거합니다. top은 아이템을 리턴만 하게 되지요.

코드는 다음과 같습니다.

	function Node(value) {
	this.value = value;
	let prev = null;
	}
	function Stack() {
	this.firstNode = null;
	this.lastNode = null;
	this.value;
	}
	Stack.prototype.top = function() {
	if(this.empty()) {
	return;
	}
	return this.lastNode.value;
	}
	Stack.prototype.push = function(value) {
	if(value === undefined) {
	console.log('input any thing');
	return;
	}
	const newNode = new Node(value);
	newNode.prev = this.lastNode;
	this.lastNode = newNode;
	}
	Stack.prototype.pop = function() {
	if(this.empty()) {
	return;
	}
	const lastNode = this.lastNode;
	this.lastNode = this.lastNode.prev;
	return lastNode.value;
	}
	Stack.prototype.empty = function() {
	if(!this.lastNode) {
	console.log('data is empty');
	return true;
	}
	return false;
	}
	const stack = new Stack();
	console.log(stack.empty());
	console.log(stack.push(32));
	console.log(stack.empty());
	console.log(stack.top());
	console.log(stack.pop());
	console.log(stack.empty());
	console.log(stack.push(32));
	console.log(stack.push('ddsc'));
	console.log(stack.push('12121'));
	console.log(stack.push(32));
	console.log(stack.push('cccc'));
	console.log(stack.top());
	console.log(stack.pop());
	console.log(stack.top());
	console.log(stack.pop());

view raw stack.js hosted with ❤ by GitHub

Queue

queue는 FIFO(first in first out) 형태의 자료구조입니다. 간단히 은행 번호표를 생각하면 됩니다. 먼저 온 사람부터 처리를 해주는 형태죠.

method	설명
enqueue	새로운 아이템을 넣습니다.
dequeue	첫 아이템을 뺍니다.
front	첫 아이템을 가져옵니다.

	function Node(value) {
	this.value = value;
	this.next = null;
	}
	function Queue() {
	this.firstNode = null;
	}
	Queue.prototype.enqueue = function(value) {
	if(value === undefined) {
	console.log('input anything');
	return;
	}
	const newNode = new Node(value);
	if(this.firstNode) {
	newNode.next = this.firstNode;
	}
	this.firstNode = newNode;
	}
	Queue.prototype.dequeue = function() {
	if(!this.firstNode) {
	console.log('queue is emtpy');
	return;
	}
	const firstNode = this.firstNode;
	this.firstNode = this.firstNode.next;
	return firstNode.value;
	}
	Queue.prototype.front = function() {
	if(!this.firstNode) {
	console.log('queue is emtpy');
	return;
	}
	return this.firstNode.value;
	}
	const queue = new Queue();
	console.log(queue.enqueue(212));
	console.log(queue.front());
	console.log(queue.dequeue());
	console.log(queue.enqueue(4324));
	console.log(queue.enqueue('d'));
	console.log(queue.enqueue('dssdsdsdd'));
	console.log(queue.front());
	console.log(queue.dequeue());
	console.log(queue.front());
	console.log(queue.dequeue());
	console.log(queue.front());
	console.log(queue.dequeue());

view raw queue.js hosted with ❤ by GitHub

지금 껏 간단히 stack과 queue를 구현해보았습니다.

Queue는 더 확장된 자료구조로, 원형큐와 dequeue가 있습니다. dequeue는 자바스크립트에서 배열이 dequeue를 구현한 것으로 볼 수 있습니다.

queue의 경우 첫 아이템만 꺼낼 수 있지만, dequeue는 첫 아이템과 마지막 아이템 둘다 꺼낼 수 있습니다.