[자료구조] 스택(Stack)

zzzzsb·2022년 7월 14일

자료구조&알고리즘

목록 보기

1/8

스택(Stack)

스택의 개념

데이터가 일렬로 나열되어 저장되는 선형(linear) 자료구조
한쪽 끝에서 삽입, 삭제가 이루어지는 후입선출(LIFO, Last in First Out) 구조를 가진다.
스택에 데이터가 삽입될 위치를 Top이라고 한다.

스택의 기본 연산

push(data): 스택의 top에 데이터를 삽입
pop: 스택의 top에 위치한 요소를 제거
isEmpty: 스택이 비어있는지 확인
isFull: 스택이 꽉 찼는지 확인
peek or top: 스택의 top에 위치한 요소를 반환

스택 구현

먼저, Stack의 ADT를 알아보자.

추상 자료형(ADT)

ADT란 추상자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고, 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해 놓은 것.

Javascript

자바스크립트에서는 배열을 이용해 스택을 간단하게 구현할 수 있다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

C++

스택의 시간복잡도

Operation	Big-O
Access	O(n)
Search	O(n)
Insert(push)	O(1)
Delete(pop)	O(1)

삽입과 삭제는 top에서 이루어지기 때문에, O(1)만큼의 시간이 걸린다.

스택의 사용 사례

재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우, 임시데이터를 스택에 넣어줌
- 재귀함수를 빠져나와 backtrack(퇴각 검색)을 할때는 스택에 넣어두었던 임시데이터를 빼줘야 함
- 즉, 스택은 재귀 알고리즘을 반복적 형태(iterative)로 구현할 수 있게 해줌.
웹 브라우저 방문기록 (뒤로가기)
실행 취소 (undo)
역순 문자열 만들기
수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
후위 표기법 계산

즉, 스택은 서로 관계가 있는 여러 작업을 연달아 수행하며, 이전의 작업 내용을 저장해둘 필요가 있을때 널리 사용된다.