[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[]이 존재한다.
스택에서 가장 최근에 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가 되면서 스택 포화 에러가 출력되는 걸 확인할 수 있다.
