[C언어로 쉽게 풀어쓴 자료구조] Chapter4. 스택 (1)

4.1 스택이란?

● 스택 : 입출력이 최상단에서만 이루어지는 선형 나열 구조로, 가장 최근에 들어온 입력값이 가장 먼저 나가는

후입선출(LIFO: Last-In First-Out) 방식을 따른다.

- 입출력이 이뤄지는 최상단을 스택 상단(stack top), 반대쪽인 바닥을 스택 하단(stack bottom)이라고 한다.

- 스택에 저장되는 것을 요소(element), 스택이 요소가 하나도 없이 비어있으면 공백 스택(empty stack)이라고 한다.

- 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 긴요하게 사용된다.

 

컴퓨터에서 함수 호출이 이루어질 때, 호출된 함수는 실행이 끝나면 자신을 호출했던 함수로 되돌아가야 한다.

이 때 시스템 스택은 함수가 호출될 때마다 활성 레코드(activation record)를 만들고, 활성 레코드에는

프로그램 카운터, 복귀주소, 함수 호출에 사용한 매개변수와 함수 안에서 선언된 지역 변수들이 저장된다.

* 함수가 자기 자신을 호출하는 재귀함수에서도 같은 방법으로 시스템 스택이 작동한다.

 

 

♠ 106p Quiz

01 후입선출(Last-In Fisrt-Out)

02 입력을 a, d, e, c, b순으로 입력하면 출력은 b, c, e, d, a 순이다.

 

4.2 스택의 구현

스택을 구현할 때는 배열 또는 연결 리스트를 이용하는 방법이 있다.

배열 - 구현이 간단하고 성능이 우수한 반면 스택의 크기가 고정된다.

연결 리스트 - 구현이 약간 복잡하지만 스택의 크기가 가변적이다.

배열을 사용하여 스택을 구현해보자.

 

· int 형의 1차원 배열 stack[MAX_STACK_SIZE]

· int top : 가장 최근에 입력되었던 자료를 가리킨다. 스택이 비어있으면 -1의 값을 갖는다.

 

· is_empty() : 스택이 비어있는 지를 검사한다.

· is_full() : 스택이 가득 찾는 지를 검사한다.

· push(x) : 스택에 새로운 요소를 삽입한다. // 삽입 전에 is_full()을 확인하고, top을 ++해준다.

· pop() : 스택에서 하나의 요소를 제거하고 제거한 값을 반환한다. // 제거 전에 is_empty()를 확인하고, top을 --해준다.

 

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

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

1차원 배열과 top 변수를 전역 변수로 구현하여 스택을 구현하는 프로그램은 하나의 프로그램에서 여러 개의 스택을 동시에 다루기가 어렵다. 이를 해결하기 위해 top과 stack 배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달한다. 구조체에 대한 포인터를 각 함수의 매개변수로 전달하면 필요할 때마다 구조체를 만들어서 다양한 stack을 동시에 여러 개 다룰 수 있다.

후자의 방법만 구현해도 전역변수를 사용하는 예시와 그의 단점을 이해할 수 있기에 후자만 작성해보겠다.

*스택의 요소를 구조체로 구현하는 것도 element가 구조체인 점만 다르기 때문에 구현을 생략한다.

 

#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){
	s->top=-1;
}

int is_empty(StackType *s){
	if(s->top == -1){
		return 1;
	}
	else return 0;
}

int is_full(StackType *s){
	if(s->top == (MAX_STACK_SIZE-1)){
		return 1;
	}
	else return 0;
}

void push(StackType *s,element item){
	if(is_full(s)){
		fprintf(stderr,"스택 가득참");
		exit(1);
	}
	s->top ++;
	s->data[(s->top)]= item;
}

element pop(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	
	return s ->data[(s->top)--];
	
	//return s->data[(s->top)]; 
	//(s->top)-- 이렇게 값 반환하고 top을 줄이려고 했는데
	//return을 하면 함수가 끝난다..^^
}

element peek(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	return s->data[(s->top)];
}

int main(){
	StackType *s1;
	StackType *s2;
	s1 = (StackType*)malloc(sizeof(StackType));
	s2 = (StackType*)malloc(sizeof(StackType));
	init_stack(s1);
	init_stack(s2);
	push(s1,1);
	push(s1,2);
	push(s1,3);
	push(s2,pop(s1));
	push(s2,pop(s1));
	push(s2,pop(s1));
	printf("%d \n", peek(s2));
	printf("%d \n", pop(s2));
	printf("%d \n", pop(s2));
	printf("%d \n", pop(s2));
    free(s1);
    free(s2);
	return 0;
}

116p 도전문제 및 스택을 동적 메모리 할당으로 생성하는 방법까지 구현한 코드이다.

s2에는 3,2,1 순으로 입력이 들어가기에 출력은 1, 2, 3 순으로 나온다.

StackType s1으로 선언하면 함수의 매개변수로 구조체를 넘길 때 &s1와 같이 주소 연산자를 붙여야 하지만

malloc으로 동적 할당하여 포인터를 전달하여 *s1을 넘긴 다음 free로 메모리를 반환할 수 있다.

 

♣ 116p Quiz

01 -1

02 스택의 최상단 입력값

03 9개

 

4.3 동적 배열 스택

위의 코드에선 크기가 결정된 1차원 배열 data[]를 사용하였지만 동적 메모리 할당을 이용할 수 있다.

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

typedef int element;
typedef struct{
	element *data;
	int capacity;
	int top;
}StackType;

void init_stack(StackType *s){
	s->top=-1;
	s->capacity = 1;
	s->data=(element*)malloc(s->capacity*sizeof(element));
}

int is_empty(StackType *s){
	if(s->top == -1){
		return 1;
	}
	else return 0;
}

int is_full(StackType *s){
	if(s->top == (s->capacity-1)){
		return 1;
	}
	else return 0;
}

void push(StackType *s,element item){
	if(is_full(s)){
		s->capacity *=2; // 가득 찰 때마다 2배씩 realloc 해준다
		s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
	}
	s->top ++;
	s->data[s->top]=item;
}

element pop(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	
	return s ->data[(s->top)--];
}

int main(){
	StackType *s;
	s = (StackType*)malloc(sizeof(StackType));
	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));
	return 0;
}