스택(Stack)

 

스택(Stack)

물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

스택에 저장된 자료는 선형 구조

• 선형구조 : 자료 간의 관계가 1대1 관계
• 비선형구조 : 자료 간의 관계가 1대N의 관계

 

스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.

마지막에 삽입한 자료는 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)

 

 

 

 

스택 구현시 고려 사항

• 1차원 배열을 사용하여 구현할 경우 구현이 용이하다는 장점이 있으나 스택의 크기를 변경하기가 어렵다는 단점

※위 문제를 해결하기위해 저장소를 동적으로 할당하여 스택을 구현하는 방법이 있음(동적 연결리스트를 이용하여 구현)

• 동적 할당은 구현방법이 복잡하다는 단점이 있지만 메모리를 효율적으로 사용한다는 장점을 가짐

 

 

스택 응용

 

1. 괄호검사

괄호의 종류

• 대괄호 : []
• 중괄호 : {}
• 소괄호:()

조건

• 여는 괄호와 닫는 괄호는 개수가 같아야함
• 여는 괄호는 닫는 괄호보다 먼저 나와야함
• 괄호 사이에는 포함 관계만 존재