[자료구조] 7. 스택(Stack)
스택이란? / 스택의 특징
7.1 스택 ADT
7.2 스택의 구현 방법
7.3 배열 기반 스택 구현
1) 전역 변수로 구현
7.4 동적 배열 기반 스택 구현
7.5 연결 리스트 기반 스택 구현
2) 연결된 스택 연산 구현
스택은 선형 자료구조의 일종이다.
스택은 우리 주변의 사물 중 프링글스 과자 통에 비유할 수 있다.
프링글스 과자 통은 한쪽은 뚫려 있고 한쪽은 막혀 있다. 과자는 통의 뚫려 있는 부분에서 막혀 있는 부분으로 들어가 차곡차곡 쌓이게 된다. 먼저 들어간 과자일수록 통의 아랫부분에 위치하고 나중에 들어간 과자일수록 통의 윗부분에 위치할 것이다. 반대로 과자를 꺼내 먹을 때는 윗부분에 위치한 과자일수록 먼저 꺼내어질 것이다.
이렇듯 스택은 먼저 들어간 것이 나중에 나오고, 나중에 들어간 것이 먼저 나오는 구조이다.
[스택의 특징]
스택의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
후입선출, LIFO(Last-In, First-Out) : 가장 최근에 들어온 데이터가 가장 먼저 나가는 구조.
이러한 입출력 형태를 이용하여 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 하는 것과 같은 상황에 매우 긴요하게 사용된다.
입출력이 이루어지는 부분을 스택 상단(stack top), 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 하며
스택에 저장되는 것을 요소(element)라고 한다.
요소가 하나도 없는 스택은 공백 스택(empty stack)이라고 한다.
[스택 구조의 예시] - 시스템 스택을 이용한 함수 호출
시스템 스택: 운영체제가 사용하는 스택
함수는 호출되었다가 실행이 끝나면 자신을 호출한 함수로 되돌아가야 하는데 이때 스택이 사용된다. 즉, 스택은 복귀할 주소를 기억하는데 사용된다. 함수는 호출된 순서의 역순으로 되돌아가햐 하기 때문이다.
시스템 스택에는 함수가 호출될 때마다 활성 레코드(activation record)가 만들어지고 여기에 함수의 복귀 주소가 저장된다. (활성 레코드에는 프로그램 카운터 뿐만 아니라 함수 호출 시 매개변수와 함수 내의 지역 변수들이 같이 생성된다.)
* 프로그램 카운터(PC) : 다음에 실행될 명령어의 주소를 가지고 있는 명령어 카운터.
* 함수가 자기 자신을 호출하여도 동일한 방법으로 활성 레코드가 만들어졌다가 없어지게 된다.
7.1 스택 ADT
[스택의 ADT]
◾ 객체 : 0개 이상의 원소를 가지는 유한 선형 리스트.
◾ 연산 :
• isEmpty() : 스택이 공백 상태인지 검사
- 공백 상태이면 true 반환
• isFull() : 스택이 포화 상태인지 검사
- 포화 상태이면 true 반환
• push(): 요소 삽입 함수
- 스택이 포화 상태인지 검사
- 최신 입력 위치를 증가하고, 증가된 위치에 요소 데이터 저장
• pop() : 요소 삭제 함수
- 스택이 공백 상태인지 검사
- 최신 입력 데이터를 반환하고, 최신 입력 위치 감소
• peek()
- 스택이 공백 상태인지 검사
- 최신 입력 데이터를 반환
7.2 스택의 구현 방법
① 배열 기반 스택
장점 - 구현하기 쉽고, 성능이 우수하다.
단점 - 스택의 크기가 고정된다.
② 연결 리스트 기반 스택
장점 - 스택의 크기를 필요에 따라 변경할 수 있다.
단점 - 구현이 복잡하다.
7.3 배열 기반 스택 구현
스택을 구현하기 위해서는 스택의 요소들을 저장할 배열과, 요소의 삽입 및 삭제를 위해 가장 최근에 입력된 자료의 인덱스를 저장하는 top 변수가 필요하다.
top 변수는 스택이 공백 상태이면 -1의 값을 갖는다. (top 변수 값 -1로 초기화)
1) 전역 변수로 구현
1차원 배열과 top 변수를 모두 전역 변수로 구현한다. 전역 변수로 구현되기 때문에 배열이나 top 변수를 스택 연산 함수의 인자로 전달할 필요가 없다.
이 방법은 구현이 쉽지만 스택 배열과 top이 전역 변수로 선언되기 때문에 하나의 프로그램에서 여러 개의 스택을 사용하기 어렵다.
[스택 구현]
//[배열 기반 스택을 전역 변수로 구현]
#define MAX_STACK_SIZE 100 //스택의 최대 크기
#define MAX_STRING 100
typedef struct {
int a;
char b[MAX_STRING];
} element; //스택에 저장될 요소의 자료형 (저장될 데이터가 구조체일 경우)
element stack[MAX_STACK_SIZE]; //요소들을 저장할 1차원 배열
int top = -1; //top 변수
[스택 연산 구현]
//[배열 기반 스택 연산 구현]
// 1. 공백 상태인지 검사
int isEmpty() {
return (top == -1);
}
// 2. 포화 상태인지 검사
int isFull() {
return (top == (MAX_STACK_SIZE - 1));
}
// 3. 삽입 연산
void push(element item) {
// 사전 조건 : 스택이 포화 상태가 아니어야 함
if (isFull()) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else {
stack[++top] = item; //스택에 요소 추가 - top 증가 시키고 해당 위치에 요소를 삽입
}
}
// 4. 삭제 연산
element pop() {
// 사전 조건 : 스택이 공백 상태가 아니어야 함
if (isEmpty()) {
fprintf(stderr, "스택 공백 에러\n");
return;
}
else {
return stack[top--]; //스택 요소 삭제 - 삭제할 요소를 반환하고 top 감소
}
}
// 5. peek 연산
element peek() {
// 사전 조건 : 스택이 공백 상태가 아이어야 함
if (isEmpty()) {
fprintf(stderr, "스택 공백 에러\n");
return;
}
else {
return stack[top]; //top 위치의 요소를 반환(top 감소하지 않음)
}
}
2) 스택 구조체 타입 정의
이 방법은 스택으로 사용할 새로운 구조체 타입을 만들어 필요할 때마다 이 스택 구조체를 생성하는 방식이다.
스택을 전역 변수로 구현하는 방법과 달리 하나의 프로그램에서 여러 개의 스택을 동시에 사용할 수 있다.
구조체의 멤버로 배열과 top 변수를 넣고, 구조체의 포인터를 각 함수의 인자로 전달한다. 각 함수에서는 구조체의 포인터를 이용하여 특정 스택에 접근하고 스택을 조작한다.
* 구조체를 인자로 전달할 경우 구조체의 원본에는 아무런 영향을 줄 수 없으므로(call-by-value) 구조체의 포인터를 전달해야 한다.
[스택 구현]
//배열 기반 스택 정의
typedef struct {
element data[MAX_STACK_SIZE]; //요소들을 저장할 배열
int top; //top 변수
} ArrStack;
[스택 구조체 초기화 함수]
이 방법에서는 ArrList 구조체 안에 들어 있는 변수들을 초기화하기 위한 함수가 필요하다.
//[스택 구조체 초기화 함수]
void initArrStack(ArrStack* s) {
s->top = -1;
}
[스택 연산 구현]
//[스택 연산 구현]
// 1. 공백 상태인지 검사
int isEmpty(ArrStack *s) {
return (s->top == -1);
}
// 2. 포화 상태인지 검사
int isFull(ArrStack *s) {
return (s->top == (MAX_STACK_SIZE - 1));
}
// 3. 삽입 연산
void push(ArrStack *s ,element item) {
// 사전 조건 : 스택이 포화 상태가 아니어야 함
if (isFull(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else {
s->data[++(s->top)] = item; //스택에 요소 추가 - top 증가 시키고 해당 위치에 요소를 삽입
}
}
// 4. 삭제 연산
element pop(ArrStack *s) {
// 사전 조건 : 스택이 공백 상태가 아니어야 함
if (isEmpty(s)) {
fprintf(stderr, "스택 공백 에러\n");
return;
}
else {
return s->data[(s->top)--]; //스택 요소 삭제 - 삭제할 요소를 반환하고 top 감소
}
}
// 5. peek 연산
element peek(ArrStack *s) {
// 사전 조건 : 스택이 공백 상태가 아이어야 함
if (isEmpty(s)) {
fprintf(stderr, "스택 공백 에러\n");
return;
}
else {
return s->data[s->top]; //top 위치의 요소를 반환(top 감소하지 않음)
}
}
[정적 메모리 할당 생성 vs 동적 메모리 할당 생성]
int main(void) {
//스택을 정적으로 생성
ArrStack a;
initArrStack(&a);
//스택을 동적 메모리 할당으로 생성
ArrStack *b;
b = (ArrStack*)malloc(sizeof(ArrStack));
initArrStack(b);
....
free(b); // *사용이 끝나면 동적 메모리를 반납해야 한다*
}
7.4 동적 배열 기반 스택 구현
7.3에서의 스택은 모두 컴파일 시간에 정적으로 배열의 크기가 결정되는 1차원 배열을 사용했다. 따라서 컴파일 시간에 필요한 스택의 크기를 알아햐 하고 스택의 크기가 고정적이였다.
이번에는 mallc()함수를 사용하여 실행 시간에 동적으로 메모리를 할당 받아 필요할 때마다 배열의 크기를 늘릴 수 있는 스택을 구현해보자.
[스택 구현]
//[스택을 새로운 구조체 타입으로 정의]
#define MAX_STRING 100
//스택에 저장될 요소의 자료형
typedef struct {
int a;
char b[MAX_STRING];
} element;
//배열 기반 스택 정의
typedef struct {
element *data; //요소들을 저장할 배열 포인터
int capacity; //현재 배열 크기
int top; //top 변수
} ArrStack;
[스택 생성 및 삭제 함수]
//[스택 생성/삭제 함수]
void initArrStack(ArrStack* s) { //스택을 생성할 때 1개의 요소를 저장할 수 있는 공간을 확보
s->top = -1;
s->capacity = 1;
s->data = (element*)malloc(s->capacity * sizeof(element));
}
void deleteArrStack(ArrStack* s) {
free(s);
}
[스택 연산 구현]
삽입 연산의 경우, 배열의 공간이 부족하면 realloc() 함수를 사용하여 메모리를 2배로 더 확보한다.
* realloc() : 동적 메모리의 크기를 변경하는 함수. 현재 내용은 유지하면서 주어진 크기로 동적 메모리를 다시 할당한다.
- 헤더 - stdlib.h
- 형태 - void *realloc(void *ptr,size_t size)
- 인자 - 메모리 크기를 변경시킬 포인터, 재할당 받을 메모리 크기
- 반환 - 메모리 크기가 변경된 메모리의 주소
//[스택 연산 구현]
// 1. 공백 상태인지 검사
int isEmpty(ArrStack *s) {
return (s->top == -1);
}
// 2. 포화 상태인지 검사
int isFull(ArrStack *s) {
return (s->top == (s->capacity - 1));
}
// 3. 삽입 연산
void push(ArrStack *s ,element item) {
// 스택이 포화 상태일 경우, 메모리를 2배로 확보
if (isFull(s)) {
s->capacity *= 2;
s-> data = (element*)realloc(s->data, s->capacity * sizeof(element));
}
else {
s->data[++(s->top)] = item; //스택에 요소 추가 - top 증가 시키고 해당 위치에 요소를 삽입
}
}
// 4. 삭제 연산
element pop(ArrStack *s) {
// 사전 조건 : 스택이 공백 상태가 아니어야 함
if (isEmpty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return s->data[(s->top)--]; //스택 요소 삭제 - 삭제할 요소를 반환하고 top 감소
}
}
// 5. peek 연산
element peek(ArrStack *s) {
// 사전 조건 : 스택이 공백 상태가 아니어야 함
if (isEmpty(s)) {
fprintf(stderr, "스택 공백 에러\n");
return;
}
else {
return s->data[s->top]; //top 위치의 요소를 반환(top 감소하지 않음)
}
}
7.5 연결 리스트 기반 스택
연결된 스택(linked stack) : 연결리스트를 이용하여 구현한 스택.
제공되는 외부 인터페이스는 배열을 이용한 스택과 연결 리스트를 이용한 스택이 완전히 동일하지만, 내부 구현에 있어서 차이가 있다.
연결 리스트를 이용한 스택은 크기가 제한되지 않는다는 장점이 있는 반면 동작 메모리 할당이나 해제가 필요하여 삽입/삭제 연산 시간은 좀 더 걸린다.
1) 노드 / 연결된 스택 정의
연결된 스택은 기본적으로 연결 리스트이기 때문에 데이터 필드와 링크 필드로 구성된 노드를 정의해야 한다.
가장 최근에 입력된 자료를 가리키는 top은 노드를 가리키는 포인터로 선언된다. top은 단순 연결 리스트에서의 head 포인터와 같다.
[노드 정의]
// 노드 정의
typedef int element; //노드에 저장할 요소의 자료형
typedef struct StackNode {
element data;
struct StackNode* link;
} StackNode;
[연결된 스택 정의]
//연결된 스택 정의
typedef struct {
StackNode* top;
}LinkedStack;
2) 연결된 스택 연산 구현
[초기화]
//초기화
void init(LinkedStack* s) {
s->top = NULL;
}
[연결된 스택 연산 구현]
//[연결된 스택 연산 구현]
//공백 상태 검출
int is_empty(LinkedStack* s) {
return(s->top == NULL);
}
// 스택 항목 출력
void print_stack(LinkedStack* s) {
StackNode* p;
for (p = s->top; p != NULL; p = p->link) {
printf("%d->", p->data);
}
printf("NULL\n");
}
//삽입 연산
void push(LinkedStack* s, element item) {
StackNode* temp = (StackNode*)malloc(sizeof(StackNode)); //삽일할 노드 생성
temp->data = item;
temp->link = s->top;
s->top = temp;
}
//삭제(pop) 연산
void pop(LinkedStack* s) {
if (is_empty(s)) { //스택이 공백 상태일 경우 에러 발생
fprintf(stderr, "스택이 비어 있음\n");
exit(1);
}
else {
StackNode* temp = s->top; //삭제할 노드
int data = temp->data;
s->top = s->top->link;
free(temp);
return data; //삭제한 노드의 데이터 필드 값 반환
}
}
//peek 연산
element peek(LinkedStack* s) {
if (is_empty(s)) { //스택이 공백 상태일 경우 에러 발생
fprintf(stderr, "스택이 비어 있음\n");
exit(1);
}
else {
return s->top->data; //top이 가리키는 노드의 데이터 필드 값 반환
}
}