스택

스택이란

 

정의 : 스택은 ‘먼저 들어간 것이 나중에 나오는 자료구조’로써 초코볼이 담겨있는 통에 비유할 수 있다.

 

 

스택의 기본 연산

초코볼 통에 초코볼을 넣는다. (push) 

초코볼 통에서 초코볼을 꺼낸다. (pop) 

이번에 꺼낼 초코볼의 색이 무엇인지 통 안을 들여다 본다. (peek)

 

 

스택의 ADT 정의

 

 

 

스택의 배열기반 구현

 

인덱스가 0인 위치를 스택의 바닥으로 정의해야 배열 길이에 상관없이 바닥의 인덱스 값이 동일해진다.

 

- 인덱스 0의 배열 요소가 '스택의 바닥으로 정의 되었다.

- 마지막에 저장된 데이터의 위치를 기억해야 한다. (Top의 위치 중요)

 

 

두번의 PUSH 연산(그림)

 

 

push : Top을 위로 한칸 올리고(+1), Top이 가리키는 위치에 데이터 저장 (선 증가, 후 저장) 

pop : Top이 가리키는 데이터를 반환하고, Top을 한칸 내림(-1) (선 반환, 후 감소)

 

코드

ArrayBaseStack.h

 

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE	1
#define FALSE	0
#define STACK_LEN	100

typedef int Data;

//배열 기반을 고려하여 정의된 스택의 구조체
typedef struct _arrayStack
{
	Data stackArr[STACK_LEN];
	int topIndex;
} ArrayStack;

typedef ArrayStack Stack;


void StackInit(Stack * pstack); //스택의 초기화
int SIsEmpty(Stack * pstack);  //스택이 비었는지 확인

void SPush(Stack * pstack, Data data); //push 연산
Data SPop(Stack * pstack);//pop 연산
Data SPeek(Stack * pstack); //peek연산

#endif

 

 

ArrayBaseStack.c

 

#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"

//-1은 스택이 비었음을 의미
void StackInit(Stack * pstack)
{
	pstack->topIndex = -1;
}

//스택이 비었으면 TRUE 반환
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];
}

 

ArrayBaseStackMain.c

 

#include <stdio.h>
#include "ArrayBaseStack.h"

int main(void)
{
	// 스택의 생성 및 초기화
	Stack stack;
	StackInit(&stack);

	//데이터 넣기
	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);

	//데이터 꺼내기
	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

 

 

스택의 연결 리스트 기반 구현

 

 

코드

ListBaseStack.h

 

#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;


typedef ListStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

 

 

ListBaseStack.c

 

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"

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;
}

 

 

ListBaseStackMain.c

 

#include <stdio.h>
#include "ListBaseStack.h"

int main(void)
{

	Stack stack;
	StackInit(&stack);


	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);


	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

 

 

Chapter 06 스택(Stack).pdf

1.65MB

 

Ch06.zip

0.03MB

 

 

 

참고 : 윤성우의 열혈 자료구조 도서