[자료구조] 스택 (Stack)

스택

 

스택은 선형 자료구조이고, LIFO(Last In First Out)의 후입선출 구조를 가진다.

스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태이다.
삽입(Push)과 제거(Pop)는 모두 Top이라는 스택의 한쪽 끝에서만 일어난다.

 

동작

• push() - 스택 맨위에 항목을 삽입
• pop() - 스택 맨위에 항목 삭제
• peek(), top() - 스택의 맨 위(top)를 표시
• isEmpty() - 스택이 비어있는지 확인
• isFull() - 스택이 가득 차 있는지 확인
• getSize() - 스택에 있는 요소 수를 반환

 

구현

배열로 구현 - 구현하기 쉽지만 정적인 크기를 가짐
연결리스트로 구현 - 동적인 크기를 가짐, 포인터를 위한 추가 메모리 공간 필요

 

스택의 사용 사례

함수의 콜스택, 문자의 역순 출력, 연산자 후위표기법, 백트래킹

 

 

참고 : https://yoongrammer.tistory.com/81