Data Structure

[자료구조] 스택(Stack)

lumana 2023. 12. 31. 23:48

스택

  • LIFO(Last-In First-Out)

    • in Korean, 후입 선출

  • 가장 최근에 들어온 object가 가장 위에 있어 먼저 나가게 된다.

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

    • 스택 상단(stack top) : 스택에서 입출력이 이루어지는 부분

    • 스택 하단(stack bottom) : 스택 상단의 반대쪽인 바닥부분

    • 요소(element) : 스택에 저장되는 것

    • 공백 스택(empty stack) : 스택에 요소가 하나도 없을 때 그러한 스택

  • 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다.

    • ex. Undo(되돌리기) 기능

    • ex. 함수 호출

      • 함수가 실행히 끝나면 자신을 호출한 함수로 되돌아간다.

      • 시스템 스택에는 함수가 호출될 때 마다 활성 레코드가 만들어지며, 여기에 복귀 주소가 저장된다.

      • 활성 레코드에는 프로그램 카운터 뿐만 아니라 호출 시 매개변수와 함수 안에서 선언된 지역 변수들이 같이 생성된다. (자세한 내용은 프로세스 메모리 구조를 참조)

추상 자료형 스택 (ADT : Stack)

  • 객체 : 0개 이상의 원소를 가지는 유한 선형 리스트

  • 연산 :

    create(size) ::= 최대 크기가 size인 공백 스택을 생성
is_full(s) ::=
  if(스택의 원소 수 == size) return True;
  else return False;
is_empty(s) ::=
  if(스택의 원소 수 == 0) return True;
  else return False;
push(s, item) ::=
  if (is_full(s)) return ERROR_STACKFULL;
  else 스택의 맨 위에 item을 추가
pop(s) ::=
  if (is_empty(s)) return ERROR_STACKEMPTY;
  else 스택의 맨 위의 원소를 제거해서 반환한다.
peek(s) ::=
  if (is_empty(s)) return ERROR_STACKEMPTY;
  else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

스택의 구현 - 배열

  • 스택을 구현하는 방법에는 배열의 이용하는 방법과 연결리스트를 이용하는 방법이 존재 (연결리스트를 이용하는 방법은 추후에)

  • 배열을 이용하여 구현하는 방법

    • int 형 타입 가정

    • 1차원 배열 stack[MAX_STACK_SIZE]가 필요함

    • 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수 필요

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

      • top 변수는 스택이 비어 있으면 -1의 값을 가짐 (0을 가지게 되면 데이터를 가지고 있음을 의미하므로 -1을 사용)

  • 의사코드로 스택 연산 구현

    // 스택의 is_empty 연산
is_empty(S):
    if top == -1
        then return TRUE
        else return FALSE
    • 스택이 비어 있는 지를 검사하기 위하여 top를 -1과 비교
    • top가 -1이면 TRUE반환
    // 스택의 is_full 연산
is_full(S):
  if top >= (MAX_STACK_SIZE -1)
    then return TRUE
    else return FALSE
    • 스택이 가득 차있는지를 검사하기 위하여 top와 MAX_STACK_SIZE -1을 비교
    • top == MAX_STACK_SIZE-1이면 더 이상 삽입은 불가능
    // 스택의 push 연산
push(S, x):
  if is_full(S)
    then error "overflow"
    else top += 1, stack[top] = x
    • 스택이 가득 차 있는지 확인하고 가득 차 있지 않다면 top를 먼저 증가시키고 삽입
    // 스택의 pop 연산
pop(S, x):
  if is_empty(S)
    then error "underflow"
    else e = stack[top], top -= 1, return e
    • 스택이 비어있는지 확인한 후 비어있지 않다면 top가 가리키는 값을 반환하고 top를 하나 감소시킨다

전역 변수로 스택 구현하는 방법

  • 배열과 top 변수가 전역 변수로 구현되기 때문에 top 변수를 함수의 매개 변수로 전달할 필요가 없음

  • 스택의 데이터 타입은 typedef를 이용하여 element로 정의

    #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;
}

스택의 요소를 구조체로 하기

  • 스택에 저장되어야 하는 값이 정수나 문자가 아니고 더 복잡한 구조를 갖는 요소라면?

    • 스택에 구조체를 저장하면 된다

    • element를 저장하고자 하는 구조체로 선언

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100


typedef struct {
    int student_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
} element;
element  stack[MAX_STACK_SIZE];
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)
{
    element ie = {     20190001,
            "Hong",
            "Soeul"    };
    element oe;

    push(ie);
    oe = pop();

    printf("학번: %d\n", oe.student_no);
    printf("이름: %s\n", oe.name);
    printf("주소: %s\n", oe.address);
    return 0;
}

관련된 데이터를 함수의 매개변수로 전달하는 방법

  • 전역변수로 스택과 top 변수를 선언하게 되면 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어려워짐

  • C++ 이나 Java에서는 객체지향의 개념을 이용하여 해결

  • C에서도 함수의 매개변수로 Stack 타입 구조체 포인터를 전달하여 해결할 수 있다.

  • 일반적인 배열 스택 프로그램

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

// 차후에 스택이 필요하면 여기만 복사하여 붙인다. 
// ===== 스택 코드의 시작 ===== 
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
    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, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 


int main(void)
{
    StackType s;

    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));

  /* 스택을 동적 메모리 할당으로 생성 */
  /*
  StackType *s;
  s = (StackType*)malloc(sizeof(StackType));
  init_stack(s);
  push(s, 1);
  push(s, 2);
  push(s, 3);
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
  free(s);
}

동적 배열 스택

  • 위에서 다룬 스택 구현 방법들은 모두 컴파일 시간에 크기가 결정되는 1차원 배열을 사용함

  • 컴파일 시간에 필요한 스택의 크기를 알아야 하는데 이는 실제로 아주 어려움

  • malloc()을 호출하여 실행 시간에 메모리를 할당 받자

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
    element *data;        // data은 포인터로 정의된다. 
    int capacity;        // 현재 크기
    int top;
} StackType;

// 스택 생성 함수
void init_stack(StackType *s)
{
    s->top = -1;
    s->capacity = 1;
    s->data = (element *)malloc(s->capacity * sizeof(element));
}

// 공백 상태 검출 함수
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)) {
        s->capacity *= 2;
        s->data =
            (element *)realloc(s->data, s->capacity * sizeof(element));
    }
    s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
int main(void)
{
    StackType s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d \n", pop(&s));
    printf("%d \n", pop(&s));
    printf("%d \n", pop(&s));
    free(s.data);
    return 0;
}

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)

'Data Structure' 카테고리의 다른 글

[자료구조] 스택의 응용 - 괄호 검사 문제  (0) 2024.01.15
[자료구조] 배열의 응용 : 희소행렬  (0) 2023.12.26
[자료구조] 배열의 응용 : 다항식  (0) 2023.12.26
[자료구조] 순차리스트  (0) 2023.12.24
[자료구조] 배열을 이용한 리스트 구현  (0) 2023.12.24

'Data Structure'의 다른글

  • 현재글[자료구조] 스택(Stack)

관련글

티스토리툴바