스택 구조 (Stack )

Stack

LIFO (Last In First Out) 구조를 갖는 데이터 저장방식 

ex) 되돌리기 기능, 괄호쌍 검사, 수식 계산 등

Stack ADT

객체: 0개 이상의 원소를 갖는 유한 선형 리스트

연산:

• create : 최대 크기가 정해진 공백 스택 생성
• is_full
• is_empty
• push : 스택 맨 위에 원소 추가
• pop : 스택 맨 위의 원소를 제거, 반환
• peek : 스택 맨 위의 원소를 제거하지 않고 반환

배열을 이용한 Stack

-자료를 담을 배열, 가장 마지막에 입력된 자료의 index를 나타내는 top 변수를 사용

-배열의 크기에 제한이 있음

연결 리스트를 이용한 Stack

크기에 제한이 없음 (필요할 때 마다 노드 생성하고 연결)

Node는 data와 다음 Node를 가리키는 link 로 구성되어있음

head pointer는 배열에서 top의 역할을 하며 가장 마지막에 inset된 노드를 가리킴

가장 처음 insert된 노드는 NULL을 가리킴

구현이 어려워지나 메모리 낭비도 없음

Stack의 활용

-괄호쌍 검사

-후위 표기식 계산 

-중위 표기식 -> 후위 표기식 변환