스택 (stack)

스택은 후입선출의 입출력형태를 나타낸다. (Last-in, First-out)

ADT 추상 자료형으로 스택을 나타내면 다음과 같다.

• 객체: 0개 이상의 원소를 가지는 유한 선형 리스트
• 연산:
  • create(size) ::= 최대 크기가 size인 공백 스택을 생성
  • is_full(s) :=  
  • is_empty(s)
  • push(s,item)
  • pop(s)
  • peek(s)

 

 

전역변수와 1차원 배열을 이용한 스택 구현

#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;	//stack[0]부터 item 저장,top값이 하나 증가
	}
}
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top--];	//stack[top]를 반환하고 top를 하나 감소
	}
}
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top];	//stack[top]를 반환만 한다.
	}
}
int main()
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

 

구조체를 이용한 스택 구현

typedef struct {
	int student_no;
	char name[MAX_STRING];
	char address[MAX_STRING];
} element;
element  stack[MAX_STACK_SIZE];

구조체 데이터를 함수의 매개변수로 전달할때는 그대로 전달하면 call by vallue기 때문에 반드시 포인터를 사용해야한다.

그리고 간접참조 연산자를 사용하여 데이터를 활용할때, 예를 들어 생성된 구조체 포인터s라고 하면 s->top 등으로 사용.

#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)
{
	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 t;	//스택을 정적으로 생성

	init_stack(&t);
	push(&t, 1);	//함수 호출할 때 스택의 주소를 전달한다.
	push(&t, 2);
	push(&t, 3);
	printf("%d\n", pop(&t));
	printf("%d\n", pop(&t));
	printf("%d\n", pop(&t));
}