[C언어] 배열로 구현된 스택

작성은 끝냈지만 업로드를 안해서

6개월간 묵혀둔.... 글 공개함미다~

 

 

 

 

 

스택 (Stack)

---

스택 = 쌓아놓은 더미

 

스택의 특징 = 후입선출

* 후입선출(LIFO) = Last In First Out = 가장 최근에 들어온 데이터가 가장 먼저 나간다

​

아래 사진은 awesomeo184.log 님의 블로그 사진을 인용했습니다.

https://velog.io/@awesomeo184/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D

​

스택의 구조

 

(1) 스택의 구조

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO)로 되어있다.

자료를 넣는 것 = PUSH

넣어둔 자료를 꺼내는 것 = POP (꺼내는 데이터는 가장 최근에 PUSH 된 것)

​

객체를 0개 이상의 원소를 가지는 유한 선형 리스트라고 가정했을 때

기본적으로 아래의 연산이 필요하다.

​

 

● create(size) : 최대 크기가 size인 공백 스택을 생성

● is_full(s) : 스택 포화 상태 검출

● is_empty(s) : 스택 공백 상태 검출

● push(s, item) : 스택의 맨 위에 item을 추가

● pop(s) : 스택 맨 위의 원소를 제거해서 반환

● peek(s) : 스택의 맨 위의 원소를 제거하지 않고 반환

 

 

 

 

 

 

배열을 이용한 스택의 구현

---

​1차원 배열 stack[]이 존재한다.

1차원 배열 stack

 

스택에서 가장 최근에 PUSH 된 데이터를 가리키는 변수를 top이라고 할 때

가장 먼저 들어온 데이터는 stack[0]이며, 가장 최근에 들어온 데이터는 stack[top]에 저장

스택이 공백상태(is_empty == true) 이면 top = -1

​

 

 

 

 

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#define MAX_STACK_SIZE 3 // 스택의 최대 크기
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
	int n;
	char name[10];
}element; // 데이터의 자료형

typedef struct {
	element data[MAX_STACK_SIZE]; // 1차원 배열
	int top; // 스택 최상단 데이터의 위치
}StackType;

// 스택 초기화 함수
void init(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))
		printf("스택 포화 에러\n");
	else
		s->data[++s->top] = item; // 스택 맨 위에 item 추가
}

// 삭제 함수
element pop(StackType* s) {
	if (is_empty(s))
		printf("스택 공백 에러\n");
	else
		return s->data[(s->top)--]; // 가장 최근에 push 된 요소를 반환하고 제거
}

// 피크 함수
element peek(StackType* s) {
	if (is_empty(s))
		printf("스택 공백 에러\n");
	else
		return s->data[s->top]; // 가장 최근에 push 된 요소를 제거하지 않고 반환
}

// 스택 상태 출력
void stack_print(StackType* s) {
	if (is_empty(s))
		printf("<empty>\n");
	else{
		for (int i = s->top; i >= 0; i--) {
			if (i == s->top)
				printf("[%d, %s] <- top\n", s->data[i].n, s->data[i].name);
			else
				printf("[%d, %s]\n", s->data[i].n, s->data[i].name);
		}
	}
	printf("--\n");
}

element insert(int num, char str[]) {
	element e;
	e.n = num;
	strcpy(e.name, str);
	
	return e;
}

int main(void) {
	StackType s;

	init(&s);
	stack_print(&s);

	push(&s, insert(10, "ten"));
	stack_print(&s);
	
	push(&s, insert(20, "twenty"));
	stack_print(&s);

	push(&s, insert(30, "thirty"));
	stack_print(&s);

	push(&s, insert(40, "fourty"));
	stack_print(&s);

	pop(&s);
	stack_print(&s);

	push(&s, insert(50, "fifty"));
	stack_print(&s);

	
	for (int i = 0; i < 3; i++) {
		pop(&s);
		stack_print(&s);
	}
	
}

 

​

코드 결과

​

스택의 최대 크기(MAX_STACK_SIZE)가 3으로 정의되어 있기 때문에

push(&s, insert(40, "fourty"));
stack_print(&s);

​해당 부분을 실행하면 이미 스택이 꽉 차있으므로

is_full == true

가 되면서 스택 포화 에러가 출력되는 걸 확인할 수 있다.

​

​

​

​