스택(Stack)

1. 개요

- 접근, 삽입 및 삭제

 * 스택 탑만 접근 가능

 * 한쪽 끝에서 삽입, 삭제

 ▷ 삽입, 삭제 위치를 스택 탑 부근으로 제한

 ▷ 구현 자료구조에서 탑이 아닌 다른 곳을 접근할 수 있어도 하지 않기로 약속

 - 연산

스택 탑에 푸시(Push) - 삽입, 팝(Pop) - 삭제

 

2. 추상 자료형 스택

- 주요 작업

- 주요 함수

▪ GetTop(Push(S, X)) = X

▪ Pop(Push(S, X)) = S

▪ IsEmpty(Create( )) = TRUE

▪ IsEmpty(Push(S, X)) = FALSE

▪ GetSize(Push(S, X)) = GetSize(S) + 1

 

스택의 구현

1. 배열을 이용한 스택의 구현

- 연산

// StackA.h (C Interface by Array) 
#define MAX 100 	// 최대 100개 데이터를 저장
typedef struct
{ 
    int Top;		// 스택 탑의 인덱스를 추적
    int Stack[MAX];	// 스택 데이터는 정수형, 최대 100개
} stackType;		//스택 타입은 구조체

void Push(stackType* Sptr, int Item); → 스택 데이터를 정수로 가정

int Pop(stackType* Sptr); → 스택 탑의 데이터 값을 리턴함

void Init(stackType* Sptr); → 스택 초기화

bool IsEmpty(stackType* Sptr); → 비어있는지 확인

bool IsFull(stackType* Sptr); → 꽉 차있는지 확인

 

StackA.c (C Implementation by Array) 
#include <StackA.h>

void Init(stackType* Sptr)
{ 
    Sptr->Top = 0;
} 

boolean IsEmpty(stackType* Sptr)
{ 
    return (Sptr->Top = = 0);
} 

void Push(stackType* Sptr, int Item)
{ 
    Sptr->Stack[Top++] = Item;
}

int Pop(stackType* Sptr)
{ 
    return Sptr->Stack[--Top];
}

 

2. 연결 리스트를 이용한 스택의 구현

StackP.h (C Interface by Linked List) 
typedef struct 
{ 
    int Data;	// 스택 데이터를 정수형으로 가정
    node* Next;	// 다음 노드를 가리키는 포인터 변수
} node;			// 노드는 구조체 타입
typedef node* Nptr; // Nptr 타입이 가리키는 것은 노드 타입

StackP.c (C Implementation by Linked List)
#include <StackP.h>

void Init(Nptr Top);
{ 
    Top = NULL;
} 

bool IsEmpty(Nptr Top);
{ 
    return (Top = = NULL);
}

void Push(Nptr Top, int Item)
{ 
    Nptr Temp = (Nptr)malloc(sizeof(node));
    Temp->Item = Item;
    Temp->Next = Top;
    Top = Temp;
}

- 삽입

 * 반드시 첫 노드

void Push(Nptr Top, int Item);

int Pop(Nptr Top)
{ 
    if (Top = = NULL)
        printf("Empty Stack");
    else 
    { 
    	Nptr Temp = Top;
	int Item = Temp->Data;
	Top = Top -> Next;
	free Temp; 
        
	return Item;
    }
}

void FreeList(Nptr Top )
{ 
    Nptr Temp = Top; 
    while (Temp != NULL)
    { 
    	Top = Top->Next;
	free Temp;
	Temp = Top;
    } 
}

 

스택의 응용

1. 수식의 연산

- 연산자 표현

▪ 중위표현(中位, In-Fix Expression): 5 + 7

 > 연산자(Operator)가 피연산자(Operand)의 가운데 있는 표현

▪ 후위표현(後位, Post-Fix Expression): 5 7 +

 > 연산자가 피 연산자 맨 뒤로 가는 표현

 

ex) 2 5 + 3 * 1 - 연산(Post-Fix Expression)

→ (2 + 5) * 3 - 1 (In-Fix Expression)

 

2. 2진법의 전환

- 10진수의 2진 전환

 

3. 문자열 뒤집기

- 스택과 재귀호출 비교

▪ 주어진 문자열을 들어오는 대로 스택에 푸쉬하였다고 가정

▪ 프로그래머가 만든 스택: 사용자 스택(매우 유리)

▪ 재귀 호출에 의한 스택: 시스템 스택(값 비싼 연산)

// 스택
while (! StackIsEmpty)
{ 
    NewCharacter = Pop( )
    Print NewCharacter
}

// 재귀 호출
void Reverse(char S[ ], int First, int Last)
{ 
    if (First > Last)
    	return;
    else
    { 
    	Reverse(S, First+1, Last);
	printf("%c", S[First]);
    }
}