[자료구조] 스택 (Stack)

후입 선출.

[스택의 종류]

 

• 배열을 기반으로 구현한 스택
• 연결리스트를 기반으로 구현한 스택

[배열을 기반으로 구현한 스택]

 

<특징>

→ 인덱스 0의 배열요소가 스택의 바닥 ! (길이와 상관없이 무조건 인덱스 0이 바닥이기 때문)

 

 

▶ ADT 

 

필요한 기능 : 스택 초기화, 스택이 빈 경우 true 반환, 스택에 데이터 저장, 마지막에 저장된 요소 삭제, 마지막에 저장된 요소 들여다보기

 

void StackInit(Stack * pstack); // 스택 초기화
int SIsEmpty(Stack * pstack); // 스택 비었는지 확인
void SPush(Stack * pstack, Data data); // 스택에 데이터 삽입
Data SPop(Stack * pstack); // 스택에서 데이터 반환&삭제
Data SPeek(Stack * pstack); // 스택 들여다보기

 

▶ 구현

 

• 스택을 의미하는 구조체 = 배열 + topIndex

typedef struct _ArrayStack
{
    int stackArr[100];
    int topIndex;
} ArrayStack;

 

→ topIndex는 마지막에 값이 저장된 위치이다

 

 

• ADT의 구현

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack)
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

 

<특징>

 

SPop

→ 데이터를 아얘 없엔다기 보단 그냥 topIndex 하나 줄여서 안보이게 하는 느낌

 

 

---

 

 

[연결 리스트를 기반으로 구현한 스택]

 

<특징>

→ 연결 리스트 기반 스택은 연결 리스트와 굉장히 유사하다

 

 

▶ ADT (배열 기반 스택과 동일)

 

필요한 기능 : 스택 초기화, 스택이 빈 경우 true 반환, 스택에 데이터 저장, 마지막에 저장된 요소 삭제, 마지막에 저장된 요소 들여다보기

 

void StackInit(Stack * pstack); // 스택 초기화
int SIsEmpty(Stack * pstack); // 스택 비었는지 확인
void SPush(Stack * pstack, Data data); // 스택에 데이터 삽입
Data SPop(Stack * pstack); // 스택에서 데이터 반환&삭제
Data SPeek(Stack * pstack); // 스택 들여다보기

 

 

▶ 구현

 

• 스택을 의미하는 구조체 (초간단!)

typedef struct _listStack
{
	Node * head;
} ListStack;

 

 

• ADT의 구현

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->head->data;
}

 

<특징>

 

SPush

→ 단일 연결 리스트에서 head로 데이터 넣는것과 다를바가 없음

SPop

→ head 위치만 바꿈 (배열 기반 스택하고 핵심이 같음)