1. 개요
ⓐ 삽입.삭제가 이뤄지는 곳은 맨 끝부분이다.
ⓑ LIFO(Last in, First Out), 후입선출
2. 주요작업
> create, destory, push(삽입), pop(삭제or삭제하면서 top의 값을 리턴), gettop(맨위출력)...
3. 종류
ⓐ 배열 스택
ex )
#define Max 100
typedef struct{
int Top;
int Stack[Max];
}stackType;
void push(stackType *Sptr,int item){
Sptr -> stack[top++] = item;
}
void Init(stackType *sptr) // 스택 함수 초기화 , top의 값을 0으로 지정
※Top 값의 초기값
ⓐ top의 초기 값이 -1 일때 : 현재까지 들어간 자리를 top가 가르킨다.
ⓑ top의 초기값이 0 일때 : 앞으로 들어갈 자리를 top가 가르킨다.
> 둘 중에 하나만, 일관되게 사용하라.
(push,pop인덱스가 달라지기 때문에...)
ⓑ 연결리스트 스택
ex )
typedef struct{
int data;
node *next;
}node;
typedef node * Nptr;
void psh(Nptr Top, int Item){
Nptr New = (Node *)malloc(sizeof(Node));
New -> data = Item;
Top -> next = New;
}
> 링크드 리스트에서 위치를 찾아가는 temp변수가 필요 없다.
무조건, top에서 삽입과 삭제가 일어나기 때문에...
void freelist(Nptr Top);
>리스트를 메모리 반환까지 하여 반환한다.
4. 스택응용의 예
ⓐ 후위 표기 계산 연산
1) 중위 표기 : 연산을 중간에 써준다 ex) a+b
2) 후위 표기 : 연산을 맨뒤에 써준다 ex )ab+
>>장점 : 괄호가 사라진다.
ex ) 중위표시 : (2+3)*3-1
후위표시 : 23+3*1-
후위표시는 각각의 숫자를 push하여 스텍에 쌓은뒤 연산자가 나오면 숫자들을 pop하면서 연산을 실행해준다.
연산한 결과를 return하여 스택에 쌓고 다음 숫자를 받아들여 스텍에 쌓은 뒤 연산자가 나호면 숫자들을
pop하여 연산을 실행한다. 이를 반복하여 값을 구한다.
※스택을 이용하여 치리하는 후위 표시방식을 사용하는 이유
: 중위 표기를 사용한다면 *트리구조(tree struct)가 되어 처리가 복잡호고 느려잔다.
┌ 3 ┐
┌ 2 ┐ │
1 │ │
┌┐ │ │
(x + y) * a - b =? >>*트리구조 : 나중에 자세히 설명하겟다.
ⓑ 문자열 뒤집기(스택과 재귀호출의 비교)
s = "abcd" > push를 순서대로 한뒤 pop로 하나씩 출력하면 문자열이 뒤집힌다. > 재귀보다 편하다.
ⓒ 길찾기
1) 깊이 위주 탐색 : 선택한 길을 끝까지 갔다가 돌아와서 다시 출발하는 방법(stack)
> 소모적 탐색
2) 너비 위주 탐색 : 시작점에서 같은 위치만큼 이동하여 돌아다니는 방법 (que)