스택(1)

스택

- 후입선출(LIFO: Last In First Out)의 입출력 구조

- 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없음

- 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 때 사용(ex: undo 기능)

• 스택 상단(stack top): 입출력이 이루어지는 부분
• 스택 하단(stack bottom): 반대쪽인 바닥 부분
• 요소(element): 스택에 저장되는 값
• 공백 스택(empty stack): 요소가 하나도 없는 스택

추상 자료형 스택

- push 연산: 스택에 요소 삽입

- pop 연산: 스택에서 요소 삭제 

- is_empty 연산: 스택이 공백 상태에 있는지 검사

- is_full 연산: 스택이 포화 상태에 있는지 검사

- create 연산: 스택 생성

- peek 연산: 요소를 스택에서 삭제하지 않고 보기만 함

---

스택의 구현: 의사 코드

- int형 1차원 배열 stack[MAX_STACK_SIZE]를 이용하여 구현

- 가장 최근에 입력되었던 자료를 가리키는 top변수 설정

- top은 스택이 비어 있으면 -1을 값을 가짐(0을 가지면 stack[0]에 데이터가 있다는 것을 의미하므로 -1)

- 스택이 비어 있는지 검사하는 is_empty 연산

- top이 -1이라면(=스택이 비어 있으면) TRUE

- 스택이 비어 있지 않다면 FALSE

- 스택이 가득 찼는지 검사하는 is_full 연산

- top을 배열 최대 인덱스(MAX_STACK_SIZE-1)와 비교하여 일치하면(=스택이 포화 상태이면) TRUE

- 스택에 새로운 요소를 삽입하는 push 연산

- 삽입 전에 스택이 포화 상태인지 검사해야 하므로 is_full(S) 호출

- 포화 상태라면 에러 출력하고 함수 반환

- 포화되지 않았다면 top의 값을 먼저 증가시키고(top이 현재 가리키는 위치는 마지막으로 삽입되었던 요소이므로 top을 증가시키지 않고 삽입하면 기존 요소가 지워짐)

- 스택에서 요소를 꺼내는 pop 연산

- 요소를 제거하기 전 스택이 비어 있는지 검사해야 하므로 is_empty(S) 호출

- 스택이 비어 있다면 에러 출력

- 비어 있지 않다면 top이 가리키는 값(=가장 위의 값)을 반환하고 top을 하나 감소시킴

---

스택의 구현: 전역 변수로 구현

- 1차원 배열과 top 변수를 모두 전역 변수로 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100	//스택 최대 크기
typedef int element;	//데이터 자료형
element stack[MAX_STACK_SIZE];	//스택 배열
int top = -1;

int is_empty() {
	return (top == -1);
}
int is_full() {
	return(top == (MAX_STACK_SIZE - 1));
}
void push(element item) {
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
}
element pop() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
element peek() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];	//peek는 값 제거하지 않으므로 top-- 아님
}

int main(void) {
	push(1);
	push(2);
	push(3);

	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());

	return 0;
}

>>

- 1, 2, 3 순서대로 삽입했는데 3, 2, 1 순서대로 출력됨→후입선출

---

스택의 구현: 요소를 구조체로

- 스택에 저장되어야 하는 값이 정수나 문자가 아니라 더 복잡한 구조를 갖는 요소일 때

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

typedef struct {
	int student_no;	//학생 번호
	char name[MAX_STRING];	//이름
	char address[MAX_STRING];	//주소
}element;

element stack[MAX_STACK_SIZE];
int top = -1;

int is_empty() {
	return (top == -1);
}
int is_full() {
	return (top == (MAX_STACK_SIZE - 1));
}
void push(element item) {
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
}
element pop() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
element peek() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void) {
	element ie = { 20190001, "Hong", "Seoul" };
	element oe;

	push(ie);
	oe = pop();

	printf("학번: %d\n", oe.student_no);
	printf("이름: %s\n", oe.name);
	printf("주소: %s\n", oe.address);
	return 0;
}

>>

---

관련된 데이터를 함수의 매개변수로 전달하는 방법

- 위 두 방법들은 stack과 top이 전역 변수로 선언되므로 하나의 프로그램에서 여러 스택을 동시에 사용하기 어려움

- C++나 자바에서는 객체지향 사용하여 해결 가능

- C에서는 stack과 top을 하나의 구조체로 결합하고 이 구조체의 포인터를 사용해 해결 가능

 

- 전달된 구조체 포인터가 s라 하면

- 위 코드에서 top으로 사용하던 것을 s->top, stack을 s->stack으로 변경하여 사용(s는 구조체를 가리키는 포인터이므로)

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

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;	//stack과 top을 결합한 새로운 구조체 StackType

//스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}
int is_empty(StackType* s) {
	return (s->top == -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;
	}
	else s->data[++(s->top)] = item;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}

int main(void) {
	StackType 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));
}

- 각 함수에서는 구조체의 포인터를 이용하여 스택을 조작

- C언어에서의 함수 매개변수 전달 방식이 값 전달 방식(call by value)이기 때문

→ 구조체를 함수의 매개변수로 전달했을 때, 구조체 원본이 전달되는 것이 아니라 구조체의 복사본이 전달

→ 함수 안에서는 복사본을 수정해도 원본에는 영향 x

→ 원본에 대한 포인터를 전달하면 원본 변경 가능

---

스택을 동적 메모리 할당으로 생성하는 방법

...
int main(void) {
	StackType* s;
	s = (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	push(s, 1);
	puth(s, 2);
	push(s, 3);
	printf("%d\n", pop(s));
	printf("%d\n", pop(s));
	printf("%d\n", pop(s));
	free(s);
}