- 처음에 들어간 것이 가장 마지막에 나오도록 되어 있는 구조
- FILO(First In, Last Out) / LIFO(Last In, First Out)
- 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어짐
주요 연산
삽입 Push : 새 노드를 스택에 올린 후 Top의 값++
제거 Pop : 최상위 노드의 데이터를 호출자에게 반환해야함!!
실제 최상위 노드가 배열 내에서 위치하는 인덱스 값보다 1만큼 더 큼
최상위 노드의 인덱스 == Top-1
* 구현 방법
● 배열
동적으로 스택의 용량을 조절하기 어렵지만 / 구현이 간단 / 스택 생성 초기에 사용자가 부여한 용량만큼 한꺼번에 노드 생성 / 최상위 노드의 위칠르 나타내는 변수를 이용해 삽입과 제거 연산 수행
노드
typedef int ElementType;
typedef struct tagNode
{
ElementType Data;
} Node;
스택
typedef struct tagArrayStack
{
int Capacity; //용량
int Top; //최상위 노드의 위치
Node* Nodes; // 노드 배열
} ArrayStack;
포인터를 배열로 사용
● 링크드 리스트
- 스택의 용량에 제한X
- 스택으로 구현하기 위해
자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 함
노드
typedef struct tagNode
{
char* Data;
struct tagNode* NextNode;
} Node;
스택
typedef struct tagLinkedListStack
{
Node* List;
Node* Top;
} LinkedListStack;
스택의 용량이나 최상위 노드의 인덱스가 없기 때문에
링크드 리스트의 Head와 Tail에 대한 포인터 필요
Top 포인터는 링크드 리스트의 Tail을 가리켜 최상위 노드에 대한 정보 유지
List 포인터는 자유 저장소에 존재하는 Head 노드의 주소를 가리킴
* 스택의 응용
- 사칙 연산 계산기
출처 : 뇌를 자극하는 알고리즘 (한빛미디어)
댓글