[자료구조] Stack

📌 Stack ( 스택 )

Stack은 '쌓다, 쌓이다, 포개지다 ' 의 의미를 갖고 있다. 이 의미 그대로 스택은 데이터를 순서대로 쌓는 자료구조이다.

실생활에서 쉽게 예시를 찾아볼 수 있는데, 바로 프링글스 통이다. 우리가 프링글스 통에 과자를 넣는다고 할 때, 맨 위에 뚫려있는 구멍을 통해 과자를 순서대로 넣고 뺄 수 있다. 이 때 프링글스 통을 스택, 과자를 데이터로 비유할 수 있다.

 

 

Stack의 구조

stack의 구조

과자를 순서대로 넣었을 때, 가장 나중에 넣은 과자가 통의 가장 상단에 위치하기 때문에 과자를 꺼내는 경우에 가장 나중에 넣었던, 프링글스 통 상단에 위치한 과자를 먼저 뺄 수 있을 것이다.

 

• 자료구조 Stack의 특징은 입력과 출력이 하나의 방향, 즉 스택의 최상단에서만 이루어지는 제한적 접근
• 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)라고 부름
• Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'

 

Stack의 특징 

#01. LIFO(Last In First Out)

먼저 들어간 데이터가 가장 나중에 나오는 후입선출(LIFO) 구조이다.

위에 있는 stack 구조 사진으로 예시를 들어보자면 , 입력 순서는 1,2,3 이고 출력 순서는 3,2,1 인 것이 LIFO인 것이다.

이러한 특성으로 인해 스택 구조 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있는 특징이 있습니다. 그 때문에 데이터를 저장할 때나 검색할 때 항상 스택의 최상단에서만 행위가 이루어지며 이에 따라 데이터를 저장하고 검색하는 프로세스가 매우 빠르다.

 

#02. 하나의 입출력 방향

Stack 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단, 하나이다. 즉 데이터를 넣을 때도 스택의 가장 최상단으로 넣고(입력) 뺄 때 또한 스택의 가장 최상단으로 데이터를 뺄 수(출력) 있다.

 

#03. 데이터는 하나씩 

앞서 말했듯, Stack 자료구조는 데이터를 넣고 뺄 수 있는 경로가 스택의 최상단, 한 군데이기 때문에 스택 내부에 데이터를 넣을 때도 하나씩 최상단을 통해 넣고 데이터를 뺄 때 또한 항상 스택 최상단에서 하나씩 데이터를 뺄 수 있다. 즉, 스택에 한개 씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만을 뺄 수 있다.

 

 

 

Stack의 실사용 예제

컴퓨터에서 자료구조 Stack은 대표적으로 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 활용된다.

순서는 반시계 방향

위의 사진을 설명하자면,

1. 구글에 접속하여 네이버를 검색한다 - 구글 화면 Prev Stack 에 보관 

2. 네이버 링크를 클릭한다. - 네이버 검색 화면 Prev Stack에 보관 

3. 네이버에 접속한 뒤 뒤로가기 버튼을 클릭한다 - 네이버 화면 Next Stack에 보관, Prev Stack 상단 화면 불러옴 

 

이와 같은 과정으로 Stack이 브라우저에서 활용되고 있다. 

 

 

Stack 구현 

- 클래스를 이용한 Stack 구현 

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
  }

  size() {
    return this.top+1;
  }

  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }
	
  pop() {
    if (this.size() <= 0) {
      return;
    }

    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    
    return result;
  }
}

 

- Array를 이용한 stack 구현 

const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]

console.log(stack); // [1, 2, 3, 4, 5]

stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]

console.log(stack); // [1, 2, 3]