[자료구조]스택(Stack)

스택의 구조

LIFO: Last-In First-Out

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

이러한 입출력 형태를 후입 선출이라고 한다.

스택에서 입출력이 이루어지는 부분을 스택 상단(Stack top)이라 하고 반대쪽인 바닥 부분을 스택 하단(Stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다.

 

그림 1. 스택의 구조

 

 

스택의 삽입, 삭제

스택의 삽입과 삭제는 모두 스택 상단에서 발생한다.

스택으로의 삽입 연산은 push 연산이라고 하고 삭제 연산은 pop 연산이라고 한다.

 

그림2. 스택의 삽입, 삭제

그림 2는 스택에서의 push와 pop연산을 보여준다.

공백 스택에서 push(A)를 수행하면 비어 있는 스택에 A가 삽입된다.

마찬가지로 push(B)를 수행하면 스택에 B가 삽입되고, B가 A위에 쌓이게 된다.

이때 스택 상단(top)은 B를 가리킨다.

여기서 pop() 연산이 수행된다면 가장 위에 쌓여있는 B가 삭제된다.

 

 

스택의 이용

스택은 특히 자료의 출력순서가 입력 순서의 역순으로 이루어져야 할 경우에 유용하게 사용된다.

예를 들면 (A,B,C,D)의 데이터가 있을 때 데이터들의 순서를(D, C, B, A)처럼 역순으로 하고 싶다면 데이터를 전부 스택에 입력했다가 다시 꺼내면 역순으로 만들 수 있다.

스마트폰에서 "뒤로 가기" 키 또한 스택을 이용한 것이다. 

 

 

스택의 구현

C언어로 1차원 배열 스택을 구현해보자.

MAX_STACK_SIZE로 스택의 사이즈를 지정해주었다.

element는 편의상 int로 선언하였다.

스택 사이즈 크기의 1차원 배열과 top의 정보를 가지고 있는 StackType구조체를 선언하였다.

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef int element;

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

 

배열은 0부터 시작하므로 스택이 비어 있다면 top은 -1이다.

이를 이용하여 스택 초기화 함수 init_stack과 스택이 비어 있는지를 확인하는 함수 is_empty를 작성하였다.

스택이 가득 찼다면 top은 스택의 최대 사이즈보다 1이 작을 것이다.

이를 이용하여 스택이 가득 찼는지 확인하는 함수 is_full을 작성하였다.

//스택 초기화 
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);
}

스택의 주요 연산인 push, pop함수이다.

push를 하기 전에 스택이 가득 차 있는지 확인 하고,

가득 차 있다면 메세지를 출력하고 아니라면 삽입 연산을 수행한다.

기존의 스택상단을 가리키고 있었던 top에 1을 더해준 후 배열의 top 인덱스에 데이터를 넣도록 작성하였다.

pop을 하기 전에 스택이 비어 있는지 확인 하고,

비어 있다면 메세지를 출력하고 아니라면 삭제 연산을 수행한다.

스택상단에 있었던 데이터를 data변수에 대입한 뒤 top이 다음 데이터를 가리키도록 1을 빼준다.

data변수를 return한다.

//스택이 가득 차 있는지 확인 후 삽입 연산
void push(StackType* s, int data) {
	if (is_full(s)) {
		printf("Stack is full \n");
	}
	else {
		s->data[++(s->top)] = data;
	}
}

//스택이 비어 있는지 확인 후 삭제 연산
element pop(StackType* s) {
	if (is_empty(s)) {
		printf("Stack is empty \n");
		exit(1);
	}
	else {
		int data = s->data[(s->top)--];
		return data;
	}
}

스택의 모든 element를 출력하는 함수이다.

스택이 비어 있다면 빈 스택이라는 메세지를 출력한다.

그렇지 않다면 index 0부터 차례로 출력을 한다.

//스택의 모든 요소 출력
void print_stack(StackType* s) {
	if (is_empty(s)) {
		printf("Empty Stack \n");
	}
	else {
		printf("STACK:");
		for (int i = 0; i < s->top; i++) {
			printf(" %d |", s->data[i]);
		}
		printf(" %d \n", s->data[s->top]);
	}
}

main함수에서는 StackType을 선언해주고 각 element들을 push, pop한 후 출력을 해 주었다.

int main() {

	StackType stack;
	
	init_stack(&stack);

	push(&stack, 7);
	print_stack(&stack);

	push(&stack, 8);
	print_stack(&stack);

	push(&stack, 9);
	print_stack(&stack);

	pop(&stack);
	print_stack(&stack);

	push(&stack, 10);
	print_stack(&stack);

	pop(&stack);
	print_stack(&stack);

	return 0;
}

 

 

전체 코드

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef int element;

typedef struct StackType {
	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, int data) {
	if (is_full(s)) {
		printf("Stack is full \n");
	}
	else {
		s->data[++(s->top)] = data;
	}
}

//스택이 비어 있는지 확인 후 삭제 연산
element pop(StackType* s) {
	if (is_empty(s)) {
		printf("Stack is empty \n");
		exit(1);
	}
	else {
		int data = s->data[(s->top)--];
		return data;
	}
}

//스택의 모든 요소 출력
void print_stack(StackType* s) {
	if (is_empty(s)) {
		printf("Empty Stack \n");
	}
	else {
		printf("STACK:");
		for (int i = 0; i < s->top; i++) {
			printf(" %d |", s->data[i]);
		}
		printf(" %d \n", s->data[s->top]);
	}
}

int main() {

	StackType stack;
	
	init_stack(&stack);

	push(&stack, 7);
	print_stack(&stack);

	push(&stack, 8);
	print_stack(&stack);

	push(&stack, 9);
	print_stack(&stack);

	pop(&stack);
	print_stack(&stack);

	push(&stack, 10);
	print_stack(&stack);

	pop(&stack);
	print_stack(&stack);

	return 0;
}

그림 3. 출력 결과