[자료구조] 스택(stack)의 구조와 구현

 

스택이란?

 

스마트폰, 컴퓨터에서 '뒤로 가기'(undo 기능 - Ctrl+z)와 같은 기능, 혹은 일상생활에서 볼 수 있는 책상 위에 쌓여있는 책 등과 같이 자료가 차곡차곡 쌓여있는 구조를 스택 형태의 예라 할 수 있다.
순환 호출 시, 함수가 호출될 때마다 복귀 주소가 저장되는 활성 레코드가 운영체제가 사용하는 시스템 스택에 쌓이는 것 또한 컴퓨터 내의 스택의 사용 예이다.

최근에 들어온 자료가 가장 위에 있게 되고, 먼저 나가게 되는 구조가 바로 스택이고, 이러한 입출력 형태를 후입선출(LIFO: Last-In First-Out)이라고 한다.


스택에 저장되는 데이터를 요소(element)라 부른다.
스택에서 요소에 대한 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽 바닥 부분을 스택 하단(stack bottom)이라 한다.

스택의 입출력은 크게 두 가지이다.
두 가지는, 스택에 요소를 삽입(push)하고 스택에 저장된 요소를 삭제(pop)하는 입출력 연산으로 구분할 수 있다.
그리고 스택에 요소가 하나도 없는 상태를 공백 스택(empty stack),
미리 지정한 크기만큼 요소가 가득 차 있는 상태의 스택을 풀 스택(full stack)이라 부른다.

---

정리를 하며, 기억해야 할 것은 다음과 같다.

스택(stack)

- 요소(element) 입출력 형태: 후입선출(LIFO)
- 스택 상단(top), 스택 하단
- 입출력 연산: 삽입(push), 삭제(pop)
- 공백 스택(empty), 가득 찬 스택(full)

 

---

 

스택(stack)의 구현

스택이 구현된 코드를 살펴보자.
전체 코드는 다음과 같다.
여러 스택을 한 가지 프로그램 내에서 생성하여 사용할 수 있는,
구조체 포인터를 각 함수의 매개변수로 전달하여 구현한 것이다.

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

#define MAX_STACK_SIZE 100

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

// 함수 원형 정의
void init_stack(StackType* s);
int is_empty(StackType* s);
int is_full(StackType * s);
void push(StackType* s, element item);
element pop(StackType* s); element peek(StackType* s);

// main 함수

int main() {
	StackType s;

	init_stack(&s);
	init_stack(&s);

	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
}

// 스택 초기화 (top값을 -1로 설정)
void init_stack(StackType* s) { s->top = -1; }

// 스택이 비어 있는지 검사하는 함수
int is_empty(StackType* s) { return (s->top == -1); } // s->top이 -1 이라면 true(1) 반환}

// 스택이 가득 차 있는지 검사하는 함수
int is_full(StackType * s){	return (s->top == (MAX_STACK_SIZE - 1));}

// 스택에 요소를 삽입하는 함수
void push(StackType* s, element item) {
	if (is_full(s)) {		// 스택이 가득 차 있는지 체크
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	s->data[++(s->top)] = item; // 인덱스 증가 후 item을 스택에 삽입
}

// 스택이 요소를 삭제하는 함수
element pop(StackType* s) {
	if (is_empty(s)) {		// 스택이 비어 있는지 체크
		fprintf(stderr, "스택 공백 에러\n");
		return;
	}
	return s->data[(s->top)--]; // data를 반환 후 인덱스 감소
}

// 피크 함수 (피크의 요소 반환)
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공벡 에러\n");
		return;
	}
	return s->data[s->top];
}

 

---

자세하게 살펴보면 다음과 같다.


1. 스택의 요소, 구조체 정의
스택 한 개에 저장할 수 있는 요소의 개수를 100개로 지정하고, 이를 MAX_STACK_SIZE 로 정의하였다.
stack의 요소는 element라는 새로운 자료형으로 정의하였다.
현재는 int형의 자료형 한 가지가 element로 선언되었지만, 구조체를 활용하여 여러가지 자료를 저장할 수 있다.
100개까지의 요소를 저장할 수 있는 element형의 data 배열과, 스택의 상단을 가리키는 top 정수를 멤버로 가지는 StackType 구조체가 정의되었다.
StackType의 변수를 선언하게 되면, 이 구조체 변수가 스택 한 개의 역할을 하게 된다.

#define MAX_STACK_SIZE 100

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

2. 함수 원형 정의
스택을 초기화하고, 삽입하고 삭제하는 등의 입출력 연산을 위한 함수들의 원형을 main함수 이전에 정의하였다.
원본 구조체의 data 배열, top 멤버 변수의 값을 변경하여야 하기 때문에, 구조체의 포인터를 매개 변수로 전달하도록 한다.

// 함수 원형 정의
void init_stack(StackType* s);
int is_empty(StackType* s);
int is_full(StackType * s);
void push(StackType* s, element item);
element pop(StackType* s); element peek(StackType* s);

3. main함수
StackType 구조체의 변수 s를 선언하였다. 스택 자료가 한 개 선언된 것이다.
먼저 s의 주소를 인수로 전달하여 init_stack함수를 호출하고, 해당 스택의 초기 과정을 거친다.
차례대로 1,2,3의 요소를 스택에 저장하는 push 연산을 수행하고,
pop 함수를 총 3번 호출하여 차례대로 스택의 요소들을 삭제하며 삭제되는 각 요소들을 출력하도록 한다.

int main() {
	StackType s;

	init_stack(&s);
	init_stack(&s);

	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
}

4. init_stack, is_empty, is_full 함수
init_stack : 선언된 스택 구조체에 대한 입출력 연산을 하기 전 초기화하는 함수이다. top의 값에 -1를 대입한다.
is_empty : 스택 구조체의 top값이 -1인지 검사하는 함수이다.
is_full : 스택 구조체의 top값이 (MAX_STACK_SIZE-1)인지 검사하는 함수이다. 인덱스는 0부터 시작하기 때문에 지정한 스택 요소의 최대 크기 MAX_STACK_SIZE보다 1 작은 숫자와 동일하면, 스택이 가득 찼다는 것과 동일하다. MAX_STACK_SIZE를 100으로 지정하였기 때문에, 99의 값에 도달했다면 스택이 가득 찬 것이다.

// 스택 초기화 (top값을 -1로 설정)
void init_stack(StackType* s) { s->top = -1; }

// 스택이 비어 있는지 검사하는 함수
int is_empty(StackType* s) { return (s->top == -1); } // s->top이 -1 이라면 true(1) 반환}

// 스택이 가득 차 있는지 검사하는 함수
int is_full(StackType * s){	return (s->top == (MAX_STACK_SIZE - 1));}

5. push 연산
스택 구조체의 포인터와 element형 item 요소를 매개 변수로 전달 받아 해당 구조체에 삽입하는 push 함수이다.
is_full 함수가 호출되어 먼저 스택이 가득 차있는지 체크를 한다.
가득 차있지 않은 스택이라면, top 값을 먼저 증가시킨 후, 증가한 인덱스에 해당하는 data 멤버 공간에 새로운 요소인 item을 대입하여 저장한다.

// 스택에 요소를 삽입하는 함수
void push(StackType* s, element item) {
	if (is_full(s)) {		// 스택이 가득 차 있는지 체크
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	s->data[++(s->top)] = item; // 인덱스 증가 후 item을 스택에 삽입
}

6. pop 연산
구조체에 저장되어 있는 요소를 삭제하는 함수이다.
먼저 is_empty 함수가 호출되어 스택이 비어 있는지 체크를 한다.
비어있지 않고, 요소가 저장되어 있는 스택이라면, top 인덱스 공간에 저장되어 있는 요소를 반환하고, 인덱스를 감소시킨다.

// 스택이 요소를 삭제하는 함수
element pop(StackType* s) {
	if (is_empty(s)) {		// 스택이 비어 있는지 체크
		fprintf(stderr, "스택 공백 에러\n");
		return;
	}
	return s->data[(s->top)--]; // data를 반환 후 인덱스 감소
}

7. peek - 요소 반환
현재 top 인덱스에 저장되어 있는 요소를 반환하는 peek 함수이다.
먼저 스택이 비어 있는지를 체크하고, 그렇지 않다면, 데이터 배열의 top인덱스에 해당하는 요소를 반환한다.

// 피크 함수 (피크의 요소 반환)
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공벡 에러\n");
		return;
	}
	return s->data[s->top];
}

 

---

 

스택: 도전 문제

- 스택의 요소를 구조체로 선언(학생의 학번, 이름을 멤버로 담는 element 구조체)
- 두 개의 스택을 생성하여, 첫번째 스택에 3개의 요소를 추가하였다가 삭제하여 그대로 두번쨰 스택에 넣은 후, 두번쨰 스택에서 삭제하여 출력해보는 프로그램


문제를 풀기 전, 고민을 해보았다.

스택 1은 학생 3명의 정보를 입력 받아 각 요소를 저장하기 위해 push 연산을 총 세 번 수행하게 된다.
이 때, top은 -1에서 차례대로 0, 1, 2까지 값이 변경이 되었다가
요소를 삭제하는 pop연산이 다시 세 번 실행되어 2에서 1, 0, -1로 값이 다시 바뀐다.

이렇게 요소 삽입과 삭제 연산이 수행된 스택1을 그대로 스택2에 넣는다.
스택1과 같이 top의 값은 그대로 삭제 연산이 완료되어 -1의 값을 가지고 있을 테다.
하지만 인덱스 2까지는 학생 데이터가 저장되어 있을 것이라고 예상을 해보았다.
이 부분은 peek 연산을 이용하여 확인해 볼 수 있지 않을까? 생각을 해보았다.


일단, 전체 코드와 실행 결과는 다음과 같다.

// p.116 도전 문제 + 추가 구현
// 스택 2개 생성. 첫번Š 스택에 학생 데이터 추가 후 삭제하여 그대로 두번Š 스택에 넣넣고 삭제

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

#define MAX_STACK_SIZE 100

typedef struct {
	int number;
	char name[10];
}element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

// 스택 초기화 (top값을 -1로 설정)
void init_stack(StackType* s) { s->top = -1; }

// 스택이 비어 있는지 검사하는 함수
int is_empty(StackType* s) { return (s->top == -1); } // s->top이 -1 이라면 true(1) 반환}

// 스택이 가득 차 있는지 검사하는 함수
int is_full(StackType* s) { return (s->top == (MAX_STACK_SIZE - 1)); }

// 스택에 요소를 삽입하는 함수
void push(StackType* s, element item) {
	if (is_full(s)) {		// 스택이 가득 차 있는지 체크
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	s->data[++(s->top)] = item; // 인덱스 증가 후 item을 스택에 삽입
}

// 스택이 요소를 삭제하는 함수
element pop(StackType* s) {
	if (is_empty(s)) {		// 스택이 비어 있는지 체크
		fprintf(stderr, "스택 공백 에러\n");
		return;
	}
	return s->data[(s->top)--]; // data를 반환 후 인덱스 감소
}

// 피크 함수 (피크의 요소 반환)
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공벡 에러\n");
		return;
	}
	return s->data[s->top];
}

int main() {
	element dat;

	// 스택 두 개 생성과 초기화
	StackType s1, s2;
	init_stack(&s1);
	init_stack(&s2);

	printf("<스택1: 세 명 학생 정보 입력>\n");
	for (int i = 0;i < 3;i++) {
		printf("학번과 이름 입력 : ");
		scanf("%d %s", &dat.number, &dat.name);
		push(&s1, dat);
	}
	for (int i = 0;i < 3;i++) {
		dat = pop(&s1);
		printf("%d %s\n", dat.number, dat.name);
	}
	printf("\n<스택2: 스택1의 정보 대입>\n");
	s2 = s1;
	printf("\n<스택 2 삭제>\n");
	for (int i = 0;i < 3;i++) {
		dat = pop(&s2);
		printf("%d %s\n", dat.number, dat.name);
	}
}

실행 결과 :

기존 코드에서 추가/변경된 부분만 자세히 살펴보자.

 

 

typedef struct {
	int number;
	char name[10];
}element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

1. 구조체로 정의된 element
int형 자료 한 개만을 가지고 있던 element를 두 멤버를 갖는 구조체로 정의하였다.
학생의 학번, 이름을 저장하는 int형 number, char배열 name을 멤버로 선언하였다.
스택의 역할을 하는 구조체 StackType은 이전과 형태가 동일하다.

int main() {
	element dat;

	// 스택 두 개 생성과 초기화
	StackType s1, s2;

2. 스택 2개를 선언한 main함수

이번에는 기존에 스택 한 개 s를 생성한 것과 달리, 두 개 s1과 s2를 생성하여 연산을 수행하도록 하였다.

먼저 입력을 받아 임시로 학생의 데이터를 저장할 element형 변수 dat을 선언하였다.
스택 s1, s2를 선언한 뒤 각각 초기화를 시켜준다.

	init_stack(&s1);
	init_stack(&s2);

그리고 for문을 3번 실행하여, 학생의 학번과 이름을 입력 받아 각각 dat의 멤버에 저장 한 후,
이를 매개 변수로 전달하는 push 함수를 호출하였다.

	printf("<스택1: 세 명 학생 정보 입력>\n");
	for (int i = 0;i < 3;i++) {
		printf("학번과 이름 입력 : ");
		scanf("%d %s", &dat.number, &dat.name);
		push(&s1, dat);
	}

이후 다시 pop 함수를 3번 실행하여 각각에 대한 데이터를 출력하도록 하였다.
이 때에도 dat에 먼저 pop함수의 반환값을 저장한 후 이를 출력하도록 구현하였다.

	for (int i = 0;i < 3;i++) {
		dat = pop(&s1);
		printf("%d %s\n", dat.number, dat.name);
	}

이후 두번째 스택인 s2에 s1를 대입하였다.

(구조체는 비교를 할 떄에는, 각 멤버에 대한 비교를 해주어야 하지만, 대입할 때에는 구조체에 대한 대입이 가능하다!)

이 때, data 배열과 top 변수 멤버의 값 모두 그대로 대입 되었을 것.

	printf("\n<스택2: 스택1의 정보 대입>\n");
   	 s2 = s1;

다음으로 도전 문제의 지시대로, 스택2의 요소들을 삭제하도록 한다.
하지만 이 때 요소들을 삭제하기 위해 pop 연산을 실행하면,
스택 1의 값들이 그대로 모두 대입되었으므로 -1로 설정된 top의 값에 의해,
공백 스택 에러 문장이 출력되고 프로그램이 종료된다는 것을 확인할 수 있다.

	printf("\n<스택 2 삭제>\n");
	for (int i = 0;i < 3;i++) {
		dat = pop(&s2);
		printf("%d %s\n", dat.number, dat.name);
	}
}
© 2021 GitHub, Inc.