스택

 

선형 자료구조

 

'쟁반 위에 쌓인 접시'

 먼저 쌓아 올려진 것이 먼저 나온다.

 후입선출 Last-In, First-Out

 

 

스택 ADT

 

//스택을 초기화 하는 함수이다.
void StackInit(Stack* pstack);

// 스택 비어있는지 검사 (빈 경우 1 반환, 아닐 시 0반환)
int SIsEmpty(Stack* pstack);

//스택에 데이터를 저장하는 함수
void SPush(Stack* pstack, Data data);


//마지막에 저장된 요소를 삭제하는 함수이다. (삭제된 데이터 값은 반환)
Data Spop(Stack* pstack);


//마지막에 저장된 요소를 반환하는 함수이다.
Data SPeek(Stack* pstack);

 

 

 

 

스택을 구현하는 방법

 

1. 배열 기반으로 구현한다.

2. ㅇ연결 리스트 기반으로 구현한다. (구현한 자료구조를 이용하여 또 다른 자료구조를 이용하는 방법도 존재 따지고 보자면 배열 역시 자료구조의 범주안에 속한다. 리스트를 만들어 놓고 이 리스트를 활용하여 스택을 또 만드는건 아니다. 리스트 구현을 약간 변경하여 스택으로 만드는 것이 옳다.)

 

 

스택의 배열 기반 구현

 

구현 시 주의사항. 

인덱스 0이 바닥이다. - 배열의 길이와 상관없이 언제나 스택의 바닥은 인덱스 0으로 접근할 수 있다.

마지막에 저장된 위치(Top)를 기억해야한다. - 스택의 작동(Push, Pop) 연산의 원리이다.

 

push : Top을 위로  한 칸 올리고, Top이 가리키는 위치에 데이터를 저장

pop : Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

 

 

 

 

 

 

 

스택의 연결 리스트 기반 구현

 

스택은 리스트와 유사하다. 삭제 방법에 차이가 날 뿐이다. 

 

 

 

스택활용

계산기 프로그램 연산자 중위 교기법을 후위 표기법으로 변경하는데 사용할 수 있다. 

 스택 구조로 연산자를 쌓아 우선순위가 높은 연산자(마지막에 쌓인 연산자)를 먼저 처리하는 방식이다.