자료구조 (4)

새 데이터를 맨 위에 두고 가장 먼저 사용하는 후입선출(Last-In-First_Out) 유형의 자료구조이다. 스택이 저장된 원소는 top이라는 곳에서만 접근 가능. 이는 데이터를 저장하면 할수록 같이 올라간다.

가장 나중에 들어온 자료가 먼저 나간다.

스택은 순차자료구조나 연결자료구조로 구현할 수 있다. 순차자료구조로 스택을 구현할 때는 크기가 고정된 배열이므로 비어있는 공간이 생겨서 낭비될 수 있으며 크기 변경이 불가하다는 단점이 있다. 물론, 연결 자료구조로 이러한 단점들을 해결할 수 있다.

위는 배열, 아래는 연결리스트이다.

스택이 empty 상태라면 top은 -1의 값을 갖는다.

 

스택의 연산

• 삽입 : push
• 삭제 : pop
• 스택 맨 위 값 알아보고 리턴 : peek

스택의 응용

• push와 pop을 이용하여 역순 문자열을 만들 수 있다.

• 프로그램에서 호출과 복귀에 따른 수행 순서를 관리할 수 있다.

• 괄호를 검사할 수 있다. 수식에 대한 검사가 모두 끝났을 때 스택은 공백이어야 한다.

• 수식을 뒤에 표기할 수 있다. 이 상태로 컴퓨터가 계산하기 편하도록 하는 것이다. (후위표기법 Postfix notation)

중위에서 후위로 수식 전환.

스택으로 구현하는 단계