Stack(스택)

1. 스택의 정의와 추상 데이터 타입(ADT)

 - 상자 더미처럼 쌓이는 자료구조

 - LIFO : 후입선출, 스택의 중간에서 데이터를 삭제할 수 없다

 - 객체 : n개의 element 타입의 요소들의 순서 있는 모임

 - 연산 :

• create()
• is_empty(s)
• is_full(s)
• push(s, e)
• pop(s)
• peek(s)

 - 가장 전형적인 예제로 함수 호출에서 복귀주소를 기억하는데 스택을 사용

 - 사용자가 접근할 수 없고 운영 체제만 사용하는 스택이 있는데 함수가 호출될 때마다 활성화 레코드가 만들어지며 여기에 함수로부터 복귀 후에 실행될 명령어의 주소인 프로그램 카운터 값이 기록된다.

 

2. 배열로 구현한 스택

 - top값은 마지막 입력 위치로 스택이 비어있을 때 top = -1

 - 구조체로 스택구현

typedef struct {
	element stack[MAX_STACK_SIZE];
	int top;
} StackType;

 

3. 연결리스트로 구현한 스택

typedef int element;	
typedef struct StackNode { 
	element item;
	struct StackNode *link;
} StackNode;

typedef struct {
	StackNode *top;
} LinkedStackType;

 

4. 스택을 이용한 괄호 검사와 수식의 계산

 1) 괄호 검사는 여는 괄호는 push하고 닫히는 괄호를 만날 때마다 스택에서 pop하여 비교

 2) 수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)

  - 컴파일러는 주로 후위 표기법을 사용한다. 후위표기는 우선순위가 반영되어 있음.

  - 후위 계산 알고리즘 : 피연산자는 push 연산자나오면 second <- pop(); first <- pop();

  - 중위 -> 후위 변환 : 여는 괄호는 스택에 쌓고 닫는 괄호 나오면 여는 괄호 만날때까지 pop(), 연산자 간에 우선순위 따져서 (top에 있는 연산자보다 같거나 낮은 놈이 들어오면 pop()) 출력하면 됨

 

5. 미로 탐색

 - 알고리즘 : 스택의 역할은 현재 위치에서 갈 수 있는 위치들을 매번 쌓아놓는 통

스택 S와 출구의 위치, 현재 생쥐의 위치를 초기화

while (현재의 위치가 출구가 아니면)
do 현재위치를 방문한 것으로 표기
  if (현재위치의 상하좌우 위치가 아직 방문되지 않았고, 갈수 있으면
    then 그 위치들을 스택 S에 push
  if (is_empty(s))
    then 실패
  else 스택에서 하나의 위치를 꺼내어 현재위치로 만든다

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년