1. 스택이란?
스택이라는 것을 설명하라고 했더니 갑자기 감자칩 그림이 나왔다. 이 X브랜드 감자칩은 필자가 가장 좋아하면서도 가격 대비 맛이 매우 뛰어나서 자주 사먹는다. 집과 스타필드가 가까운 것도 한 이유기는 하지만
한편 스택이라는 말을 사전에 찾아보면 아래와 같이 나온다.
한마디로 말해서 "데이터(data)를 순서대로 쌓는 자료구조"가 스택이다. 맨 위에 나와있는 노X랜드 감자칩도 나름 스택의 예이다. 저 감자칩은 제조 과정에서 아래서부터 차곡차곡 쌓일 것이다. 하지만 우리가 감자칩을 구매하여 먹는 순서는 맨 위에서부터 먹는다. 즉, 나중에 들어온 것이 먼저 나가는 선입후출형(LIFO(Last In First Out) 혹은 FILO(First In Last Out)라고도 함)자료구조이다.
2. 스택의 예시
스택이 컴퓨터에서 많이 쓰이는 곳은 브라우저와 실행취소 기능이다. 브라우저에서 뒤로가기와 앞으로 가기가 대표적인 스택의 예이며, 거의 모든 프로그램에서 제공하는 실행취소 기능도 스택의 예이다. 인터넷 서핑을 하다가 뒤로가기 버튼을 누르면 가장 나중에 실행되었던 사이트가 먼저 뜨게 된다. 실행취소 가능도 가장 최근에 실행되었던 것을 취소시킨다.
3. 스택 자료구조 구현
스택이 무엇인지 개념을 알았으니, ES6 문법인 클래스를 이용하여 스택 데이터 타입을 만들어 볼 것이다. 아래는 클래스를 이용한 코드이다.
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
}
size() {
return Object.keys(this.storage).length;
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
if (Object.keys(this.storage).length === 0) {
return;
// 위의 return문은 코드의 가독성을 위하여 쓰는 것이다(없어도 같은 결과가 나옴)
}
const result = this.storage[this.top-1];
delete this.storage[this.top-1];
this.top -= 1;
return result;
}
}아래는 위의 클래스를 실제로 적용해본 예시이다.
const stackData = new Stack; // stackData 변수를 선언하고 변수의 내용은 Stack 클래스이다.
stackData.push('a'); // storage에 'a'를 추가
stackData.push('b'); // storage에 'b'를 추가
stackData.push('c'); // storage에 'c'를 추가
console.log(stackData); // Stack {storage: {…}, top: 3}
// storage의 내용은 {0: 'a', 1: 'b', 2: 'c'}이다.
// top은 앞으로 추가하게 될 위치 내지 key의 값이다.
console.log(stackData.size()); // 3
stackData.pop();// 'c'
console.log(stackData); // {storage: {…}, top: 2}
// storage는 {0: "a", 1: "b"}이다. 나중에 들어온 'c'가 제거된 것을 볼 수 있다.주의) 스택은 추상적 자료구조이다. 추상적 자료구조란 자료 자체의 형태와 그 자료에 관계된 연산들을 수학적으로만 정의한 것을 의미하며, 자료구조가 포함하는 구현 세부사항은 전혀 정의하지 않는다. 간단히 말해서 '후입선출'이라는 특성만 만족 되면 무엇이 되었든 스택이 되는 것이다. 스택 자료구조를 객체가 아닌 배열로도 구현할 수 있다. 배열로 구현한 스택 자료구조는 밑에서 알아볼 것이다.
4. 브라우저 뒤로 가기 앞으로 가기 구현
앞서 스택의 예시에서 브라우저 얘기가 나왔다. 이를 실제로 작성해 볼 것이다. 브라우저의 뒤로 가기 앞으로 가기는 네 가지의 조건 하에서 작동한다.
<조건>
- 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
- 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
- 앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
- 브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.
위의 조건 하에서 두가지 인자를 가지고 browserStack 함수를 만들어 볼 것이다.
- 인자 1: actions
String과 Number 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열- 인자 2: start
String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳
그리고 actions에서 새로운 페이지 접속은 알파벳 대문자로 표기하며, 뒤로 가기 버튼, 앞으로 가기 버튼을 누른 행동은 각각 -1, 1로 표기한다.
한편, 다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속한다.
마지막으로 반환되는 출력값 배열의 첫 번째 요소 prev 스택, 두 번째 요소는 현재페이지, 세 번째 요소 next 스택은 배열이다. 스택을 사용자 정의한다면 출력에서는 배열로 변환해서 리턴해야한다.
위의 조건에 따라서 함수를 짜면 다음과 같다.
function browserStack(actions, start) {
let currentPage = start; // start가 현재 페이지이다.
let prevStack = []; // 이전 페이지와 다음 페이지는 빈 배열로 초기화
let nextStack = [];
// 액션이 배열로 되어있으며, 엘리먼트가 여러개이기 때문에 처음부터 끝까지 반복시킨다.
for (let element of actions) {
// 경우의 수는 세가지이다. 새로운 페이지로 가는 경우, 뒤로 가는 경우, 앞으로 가는 경우
if (typeof element === 'string') { // 새로운 페이지로 가는 경우
prevStack.push(currentPage); // prev 스택에 원래 있던 페이지를 넣음
currentPage = element;
nextStack = []; // next 스택을 비움.
} else if (element === -1 && prevStack.length !== 0) { // 뒤로 가기 버튼을 누를 경우
nextStack.push(currentPage); // 원래 있던 페이지를 next 스택에 넣음
currentPage = prevStack.pop() // prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
} else if (element === 1 && nextStack.length !== 0) {
prevStack.push(currentPage);
currentPage = nextStack.pop()
}
}
return [prevStack, currentPage, nextStack];
}위의 prevStack과 nextStack은 추가할 때는 push로 추가한다. 그러면 처음에 오는 element는 앞에, 나중에 오는 element는 뒤에 온다. 하지만 비울때는 뒤에서부터 비우므로, pop() 메소드를 쓴다. 따라서 스택 자료구조의 조건을 만족한다.
