Stack
1. Stack 구조란?
stack은 선입후출 (Frist In Last Out) 의 형식을 가지고 있는
말 그대로 데이터를 순서대로 쌓는 자료구조이다.
과자 프링글스 통 안에 있는 과자가 만들어질때는 맨 아래에서 부터 하나씩 쌓여서 나오지만
우리가 과자를 먹을때는 맨위 (마지막에 쌓인) 의 과자부터 꺼내먹을 수 있는것과 비유할 수 있다.
컴퓨터 상에서 가장 대표적으로 이 stack 구조가 쓰이는 예로는
브라우저의 뒤로가기, 앞으로가기 기능을 들 수 있겠다.
& 웹 브라우저에서 Stack 구조가 사용되는 예
브라우저에서 자료구조 Stack이 사용될 때에는 다음과 같은 순서를 거친다.
-
새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
-
뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고
Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다. -
앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는,
Next Stack의 가장 마지막으로 보관된 페이지를 가져온다. -
마지막으로 현재 페이지를 Prev Stack에 보관한다.
이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다.
2. Stack 구조 구현
stack 구조를 구현하기 위한 코드를 작성해 보자.
1) Stack 클래스 지정 및 빈 stack 생성
데이터가 쌓여갈 빈 스택을 가지고 있는 Stack class 를 먼저 만들어준다.
class Stack { // class를 생성하고
construtor() {
this.storage = {}; // 빈 스택을 만들어주고
this.top = 0; // 스택의 최 상단을 표시하는 인스턴스를 만든다.
} // (이것이 곧 스택의 크기가 된다.)
}2) Stack 의 Size 파악하기
데이터가 쌓일때, 스택의 사이즈를 파악하기 위한 size() 메서드를 생성한다.
size() {
return this.top // 위에서 정의했던 this.top이 증가함에따라 크기가 커지므로
} // 스택의 크기를 파악할 수 있다.3) Stack 에 data 추가하기
스택에 데이터를 쌓는 코드를 구현한다.
push(element) {
this.storage[this.top] = element; // this.storage의 가장 최상단에 인자를 추가한다
this.top += 1; // 그리고 this.top에 카운트를 한다.
}4) Stack 에서 data 추출하기
스택에 쌓인 데이터를 꺼내는 코드를 구현한다.
pop() {
if (this.top === 0) { // 스택에 아무것도 없다면
return; // 스택을 그대로 반환한다.
}
const result = this.storage[this.top - 1]; // 변수에 top-1을 저장하고
delete this.storage[this.top - 1]; // 스택에서 삭제한다.
this.top -= 1; // 감소하는 카운트를 준다.
return result; // 변수를 리턴한다.
}5) 최종
class Stack {
constructor() {
this.storage = {};
this.top = 0;
}
size() {
return this.top;
}
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
pop() {
if (this.top === 0) {
return;
}
const result = this.storage[this.top - 1];
delete this.storage[this.top - 1];
this.top -= 1;
return result;
}
}
Frontend Developer