1.2 Stack

 

 

Stack

뜻 : Data를 돌탑처럼 쌓거나 내리는 방식의 자료구조

 

종류 : Array Stack, LinkedList Stack

 

추가 용어

Push : Stack에 Data를 올리다

Pop :  Stack에서 Data을 내리다

 

Array Stack

뜻 : 저장공간을 배열로 확보하는 Stack

 

STRUCT* addrSTRUCT

기능 : STRUCT의 메모리 주소를 저장

 

struct STRUCT

멤버 : int Capacity, int nowPosition, Node* NodeAddr

 

기능 :

1. NodeAddr : Node들의 메모리 시작주소 저장

2. Capacity : ArrStack의 최대 Node의 개수 저장

3. nowPosition : 현재 참조하고있는 노드의 인덱스 저장

 

 

LinkedList Stack

뜻 : 저장공간을 LinkedList로 확보하는 Stack

struct STRUCT

멤버 : Node* Head, Node* Tail

 

기능 :

1. Head : 헤드 Node의 주소를 저장

2. Tail : 테일 Node의 주소를 저장

 

Stack을 쓰는 후위식 계산

중위식 표기법 : 1 + 1 같이 연산자를 두 피연산자의 중간에 위치시키는 방식

후위식 표기법 : 1 1 + 같이 연산자를 두 피연산자를 쓴 후 위치시키는 방식

 

Stack과 후위식 계산식 간의 관계

후위 계산식에서 항이 1,3,2일때 : 1,3,2를 담은 노드 삽입

*일때 : 3과 2를 담은 Node들을 제거하고 6(=3*2)을 담은 Node를 삽입한다

-일때 : 1과 6을 담은 Node들을 제거하고 -5(=1-6)를 담은 Node를 삽입한다