[Data Structure] 스택(Stack)이란?

스택(Stack) 이란?

- 스택은 접근하는 것이 제한되어있는 나열 구조

- 삽입과 삭제가 목록의 끝인 "Top"에서만 가능하다.

 

쉽게 생각해서 말그대로 stack, 쌓여있는 것으로

예를 들어, 바닥에 동전을 여러개 쌓아올린다고 했을때 다시 동전을 치우려면 가장 나중에 쌓은 동전부터 치울 수 밖에 없다.

 

이처럼 스택은 한쪽이 막힌 구조라, 나머지 한 쪽에서만 넣고 뺄 수 있어 나중에 들어간 것이 먼저 나올 수 밖에 없는 구조이다.

 

그래서 스택은 '후입선출 방식의 자료구조', 또는 'LIFO(Last-In, First Out) 구조의 자료구조' 라고도 불린다.

 

 

 

자료를 넣는 것을 푸쉬(push), 반대로 꺼내는 것을 팝(pop)이라고 한다.

 

스택 연산

- pop() :  스택의 가장 윗 데이터(마지막에 저장된 요소)를 삭제. (자료를 꺼내는 것)

- push() : 스택에 데이터를 저장. (자료를 넣는 것)

- peek() (또는 top()) : 스택의 가장 윗 데이터를 반환하되 삭제는 하지 않음.

- isEmpty() : 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환

 

스택을 구현하는 두 가지 방법

  1. 배열 기반 구현

  2. 연결 리스트 기반의 구현