Stack
Stack은 말 뜻 그대로 쌓다, 쌓이다, 포개지다 라는 뜻입니다. 우리가 자판기에서 커피를 뽑아 마신 후 종이컵을 회수대에 버리는 구조와 유사합니다. 먼저 들어간 종이컵위에 새로운 종이컵이 포개지고, 만약 종이컵을 빼야 한다면 가장 나중에 버린 종이컵부터 빼야합니다. 이렇듯 Stack은 먼저 들어간 자료가 가장 나중에 나오고 가장 나중에 들어간 자료가 먼저 나오는 구조로 입력과 출력이 한 방향으로 이루어지는 특징이 있습니다. 이런 구조를 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 합니다.
Stack에서 삽입연산은 Push, 삭제 연산은 Pop이라고 합니다. 자바스크립트에선 배열의 Length를 미리 정의하는 경우가 별로 없지만 C에서는 만약 꽉 차있는 (Length가 한정된) Stack에 자료를 Push 하려하면 'Stack Overflow' 에러가 뜹니다.(그 유명한 Stack Overflow가 여기서….). 그 반대의 경우인 텅 비어있는 Stack에서 존재하지 않는 값을 Pop하려 한다면 'Stack Underflow' 에러가 뜹니다.
Stack의 활용 예
웹 브라우져의 뒤로가기 및 앞으로 가기
실행취소
Stack을 Javascript로 구현하면 다음과 같습니다.
class Stack {
constructor() {
this.storage = [];
}
push(item) {
this.storage.push(item);
}
pop() {
return this.storage.pop();
}
isEmpty() {
return this.storage.length === 0
}
isFull() {
return this.storage[this.storage.length - 1] !== undefined
}
}
Queue
Queue는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있습니다. Queue 말뜻과 같이 줄을 스는 것과 비슷한 구조로 작동합니다. 우리가 화장실을 이용하거나 매표소에서 줄을 선다고 가정할때, 가장 먼저 온 사람이 가장 먼저 볼일을 보고 표를 삽니다. 그리고 너무나 당연하게도 나중에 온 사람은 가장 나중에 일을 처리 할 수 있습니다. 이렇듯 Queue는 먼저 들어온 데이터가 먼저 나오고, 나중에 들어온 데이터가 나중에 나오는 구조입니다. 주로 자료를 입력한 순서대로 처리해야 할때 사용되며, FIFO(First In First Out) 혹은 LILO(Last In Last Out) 라고도 합니다.
Queue에서의 삽입연산은 Enqueue, 삭제 연산은 Dequeue이라고 합니다.
Queue의 활용 예
OS(operating system)의 작업 처리 시스템
프린터의 작동 원리
Queue를 Javascript로 구현 하면 다음과 같습니다.
class Queue {
constructor() {
this.storage = []
}
enqueue(item) {
this.storage.push(item);
}
dequeue() {
return this.storage.shift();
}
}
Stack과 Queue의 차이를 볼 수 있는 간단한 표
Stack | Queue | |
---|---|---|
입출력 방식 | 선입후출(First In Last Out) | 선입선출(First In First Out) |
입출력 방향 | 단방향 | 양방향 |
입출력 용어 | 입력(Push) / 출력(Pop) | 입력(Enqueue) / 출력(Dequeue) |