스택(Stack)

스택(Stack)

가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조

후입선출(LIFO) 

init() : 스택을 초기화

is_empty() : 스택이 비어있으면 TRUE 아니면 FALSE 반환

is_full() : 스택이 가득 차 있으면 TRUE 아니면 FALSE 반환

size() : 스택 내의 모든 요소들의 개수 반환

push(x) : 주어진 요소 x를 스택의 맨 위에 추가

pop() : 스택 맨 위에 있는 요소를 삭제하고 반환

peek() : 스택 맨 위에 있는 요소 삭제하지 않고 반환

배열을 이용한 스택 구현

#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
typedef int Element;

Element data[MAX_STACK_SIZE];

Element top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE == -1; }
int size() { return top + 1; }


void push(Element e)
{
	if (is_full())
		error("스택 포화 에러");
	data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top--];
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top];
}

//스택 테스트를 위한 코드

void print_stack(char msg[]) {
	int i;
	printf("%s[%2d] = ", msg, size());
	for (i = 0; i < size(); i++)
		printf("%2d ", data[i]);
	printf("\n");
}

void main()
{
	int i;

	init_stack();

	for (i = 1; i < 10; i++)
		push(i);

	print_stack("스택 push 9회");
	printf("\tpop() --> %d\n", pop());
	printf("\tpop() --> %d\n", pop());
	printf("\tpop() --> %d\n", pop());

	print_stack("스택 pop 3회");
}

만약 스택에 저장되어야 하는 값이 정수나 문자가 아닌 복잡한 구조를 갖는 항목이라면? 구조체를 사용해야 한다.

배열을 이용한 스택 구현(구조체 자료형 저장)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100

typedef struct Student {
	int id;
	char name[32];
	char dept[32];
}Student;

typedef Student Element;


Element data[MAX_STACK_SIZE];

int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE == -1; }
int size() { return top + 1; }


void push(Element e)
{
	if (is_full())
		error("스택 포화 에러");
	data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top--];
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top];
}

//스택 테스트를 위한 코드

void print_stack(char msg[]) {
	int i;
	printf("%s[%2d] = ", msg, size());
	for (i = 0; i < size(); i++)
		printf("\n\t%-15d %-10s %-20s", data[i].id, data[i].name, data[i].dept);
	printf("\n");
}

Student get_student(int id, char name[], char dept[])
{
	Student s;
	s.id = id;
	strcpy(s.name, name);
	strcpy(s.dept, dept);
	return s;
}

void main()
{
	init_stack();
	push(get_student(201813007, "홍길동", "컴퓨터공학과"));
	push(get_student(201713123, "이순신", "거북선학과"));
	push(get_student(201623423, "김연아", "체육과"));
	push(get_student(201523343, "갓갓갓", "컴퓨터공학과"));
	
	print_stack("학생 4명 삽입 후 ");
	pop();
	print_stack("학생 1명 삭제 후 ");

	
}

문자열을 복사하기 위해 strcpy() 함수가 사용 되었다. 문자 배열은 대입 연산자로 복사할 수 없다.