[자료구조] 스택(Stack)

스택(Stack)이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 형식의,

선입후출 FILO(First In Last Out)
후입선출 LIFO(Last In First Out)

특정한 순서를 따르는 선형적 자료 구조이다.

스택(Stack)의 연산

• push( item )
  : 스택 안으로 데이터(item)을 넣는다. 만약 스택이 꽉 찬 상태에서 데이터를 더 넣은 경우, 오버플로우 상태라고 한다.
  • 배열로 구현할 경우, 스택의 크기를 고정해서 사용하기 때문에 오버플로우가 발생한다.

• pop( )
  : 스택 안에 있는 데이터를 제거한다. 아이템은 넣어진 역순으로 빠져나옵니다. 만약 스택이 비어있는 상태에서 데이터를 꺼내려는 경우, 언더플로우 상태라고 한다.
  

• peek( )
  : 스택의 가장 위에 있는 항목을 반환한다.
  

• isEmpty( )
  : 스택이 비어 있을 때에 true를 반환한다.

• isFull( )
  : 스택이 가득 차있을 때에 true를 반환한다.

• size( )
  : 현재 스택에 들어있는 데이터의 개수를 리턴한다.
  

• clear( )
  : 스택에 있는 모든 데이터를 한번에 제거한다. (Stack에 저장되어 있는 데이터 값들을 하나하나 null 값으로 할당한다.)
  

• contains( item )
  : 스택에 특정 데이터(item)가 포함되어 있는지 체크하고 있다면 true, 없다면 false를 반환한다.
  
  
  
  
  
  

스택(Stack)의 구현

✔ 배열 사용

• 장점 : 구현하기 쉽다.

• 단점 : 크기가 동적이 아니라 고정돼있다. 런타임시 필요에 따라 늘어나거나 줄어들지 않는다.
  
  

✔ 연결 리스트 사용

• 장점 : 크기가 동적이다. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있다.

• 단점 : 포인터를 위한 추가 메모리 공간이 필요하다.

스택(Stack)의 용도

• 재귀 알고리즘을 반복문을 통해서 구현할 수 있게 해준다.
• 실행 취소 (undo)
• Backtracking
• 웹 브라우저 뒤로가기
• 구문분석
• 후위(postfix) 표기법 연산
• 문자열의 역순 출력 등

Reference

스택의 구조.img | 위키백과

yoongrammer 블로그