[자료구조] 스택(stack) 개념 정리와 구현

2022. 1. 12. 11:38ㆍComputer Science/자료구조

스택이란? 

- 쌓아놓은 더미를 말한다.

 

스택의 특징

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

스택의 연산

- push() : 스택에 데이터를 추가

- pop() : 스택에서 데이터를 삭제

- is_empty(s): 스택이 공백상태인지 검사

- is_full(s): 스택이 포화상태인지 검사

- create() : 스택을 생성

- peek(s) : 요소를 스택에서 삭제하지 않고 보기만 하는 연산

 

변수

배열을 이용한 스택의 구현에서는 1차원 배열 stack[]과 가장 최근에 입력되었던 자료를 가리키는 top 변수가 필요하다.

가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장한다.

* 스택이 공백상태이면 top은 -1로 초기화한다.

 

배열을 이용한 스택 ADT 

#include <stdio.h>
#include <stdlib.h>

스택이 전역 변수로 구현된다. 

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element  stack[MAX_STACK_SIZE]; // 1차원 배열
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;
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

 

스택에 정수와 문자열을 동시에 저장하기 (구조체 스택) 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 3
#define MAX_STRING_SIZE 100

typedef struct {
    char str[MAX_STRING_SIZE];
    int num;
} element;

typedef struct {
    element stack[MAX_STACK_SIZE];
    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)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else {
        s->stack[++(s->top)] = item;
    }
    
}

element pop(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else
        return s->stack[(s->top) --];
}

element peek(StackType *s)
{
    if(is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else
        return s->stack[s->top];
}

void stack_print(StackType *s)
{
    int i = 0;
    
    if (is_empty(s))
        printf("<empty>\n");
    
    for (i = s->top; i >= 0; i--) {
        printf("[%d, %s] ", s->stack[i].num, s->stack[i].str);
        
        if (i == s->top)
            printf("<- top\n");
        else
            printf("\n");
    }
    
    printf("--\n");
    
}

int main()
{
    StackType s;
    element item;
    
    init(&s);
    stack_print(&s);
    item.num = 10;
    strcpy(item.str, "ten");
    push(&s, item);
    stack_print(&s);
    
    item.num = 20;
    strcpy(item.str, "twenty");
    push(&s, item);
    stack_print(&s);
    
    item.num = 30;
    strcpy(item.str, "thirty");
    push(&s, item);
    stack_print(&s);
    
    item.num = 40;
    strcpy(item.str, "forty");
    push(&s, item);
    stack_print(&s);
    
    pop(&s);
    stack_print(&s);
    item.num = 50;
    strcpy(item.str, "fifty");
    push(&s, item);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
}

 

연결리스트로 구현된 스택 

- 스택에 들어있는 요소들을 다음과 같은 형식으로 출력하는 함수 stack_print(StackType *s)를 작성한다.

예를 들어서 50, 60, 70 순으로 입력된 스택을 출력하면

70 <- top

60

50

 

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct StackNode {
    element data;
    struct StackNode *link;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedStackType;

void init(LinkedStackType *s)
{
    s->top = NULL;
}

int is_empty(LinkedStackType *s)
{
    return s->top == NULL;
}

int is_full(LinkedStackType *s)
{
    return 0;
}

void push(LinkedStackType *s, element data)
{
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    
    if (temp == NULL) {
        fprintf(stderr, "메모리 할당 에러\n");
        return;
    }
    else {
        temp->data = data;
        temp->link = s->top;
        s->top = temp;
    }
}

void stack_print(LinkedStackType *s)
{
    if (is_empty(s))
        printf("<empty>\n");
    
    for (StackNode *p = s->top; p != NULL; p = p->link) {
        printf("%d", p->data);
        if (p == s->top)
            printf(" <- top");
        printf("\n");
    }
    printf("--\n");
}

element pop(LinkedStackType *s)
{
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        element data = temp->data;
        s->top = s->top->link;
        free(temp);
        return data;
    }
}

element peek(LinkedStackType *s)
{
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->data;
    }
}

int main(void)
{
    LinkedStackType s;
    
    init(&s);
    stack_print(&s);
    push(&s, 10);
    stack_print(&s);
    push(&s, 20);
    stack_print(&s);
    push(&s, 30);
    stack_print(&s);
    push(&s, 40);
    stack_print(&s);
    
    pop(&s);
    stack_print(&s);
    push(&s, 50);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
}

 

연결리스트로 구현된 스택 (구조체 스택) 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STRING_SIZE 100

typedef struct {
    char str[MAX_STRING_SIZE];
    int num;
} element;

typedef struct StackNode {
    element item;
    struct StackNode *link;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedStackType;

void init(LinkedStackType *s)
{
    s->top = NULL;
}

int is_empty(LinkedStackType *s)
{
    return s->top == NULL;
}

int is_full(LinkedStackType *s)
{
    return 0;
}

void push(LinkedStackType *s, element data)
{
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    
    if (temp == NULL) {
        fprintf(stderr, "메모리 할당 에러\n");
        return;
    }
    else {
        temp->item = data;
        temp->link = s->top;
        s->top = temp;
    }
}

void stack_print(LinkedStackType *s)
{
    if (is_empty(s))
        printf("<empty>\n");
    
    for (StackNode *p = s->top; p != NULL; p = p->link) {
        printf("[%d, %s] ", p->item.num, p->item.str);
        if (p == s->top)
            printf(" <- top");
        printf("\n");
    }
    printf("--\n");
}

element pop(LinkedStackType *s)
{
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        element item = temp->item;
        s->top = s->top->link;
        free(temp);
        return item;
    }
}

element peek(LinkedStackType *s)
{
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->item;
    }
}

int main(void)
{
    LinkedStackType s;
    element item;
    
    init(&s);
    stack_print(&s);
    item.num = 10;
    strcpy(item.str, "ten");
    push(&s, item);
    stack_print(&s);
    
    item.num = 20;
    strcpy(item.str, "twenty");
    push(&s, item);
    stack_print(&s);
    
    item.num = 30;
    strcpy(item.str, "thirty");
    push(&s, item);
    stack_print(&s);
    
    item.num = 40;
    strcpy(item.str, "forty");
    push(&s, item);
    stack_print(&s);
    
    pop(&s);
    stack_print(&s);
    item.num = 50;
    strcpy(item.str, "fifty");
    push(&s, item);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
    pop(&s);
    stack_print(&s);
}

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] 큐(Queue)의 개념 정리와 구현  (0) 2022.01.12

관련글

댓글 0

티스토리툴바