이근둥
근둥이의 블로그
이근둥
전체 방문자
910,179
오늘
319
어제
625

공지사항

  • 전체보기 (110)
    • 웹 (9)
    • 언어 & 프레임워크 (53)
      • JavaScript (7)
      • TypeScript (0)
      • Node.js (11)
      • Vue.js (3)
      • React (0)
      • React Native (0)
      • C & C++ (19)
      • Java & JSP (9)
      • Python (4)
    • 컴퓨터 과학 (3)
      • 알고리즘 (0)
      • 자료구조 (3)
    • 기타 (9)
      • Linux (1)
      • Git (2)
      • DialogFlow (4)
    • 일상 (13)
      • 게임 (13)
    • 칼럼 (11)
      • 회고 (2)
      • 나만의 글 (0)
      • 제품 리뷰 (9)
    • __Dev__ (9)
      • Release (9)
반응형

인기 글

  • 웹 푸시 알림(Web Push Notification)
    2022.06.13
    웹 푸시 알림(Web Push Notification)
  • [C/C++] 콘솔게임 프로그래밍 (1) - 프로젝트 생성⋯
    2017.12.19
    [C/C++] 콘솔게임 프로그래밍 (1) - 프로젝트 생성⋯
  • [Node.js] 실시간 채팅 서비스 만들기(5) - 채팅⋯
    2018.05.31
    [Node.js] 실시간 채팅 서비스 만들기(5) - 채팅⋯
  • [C/C++] 콘솔게임 프로그래밍 (2) - 메뉴 선택기능
    2017.12.19
    [C/C++] 콘솔게임 프로그래밍 (2) - 메뉴 선택기능
  • [Tomcat] 아파치 톰캣 서버 포트 변경하기
    2018.08.24
    [Tomcat] 아파치 톰캣 서버 포트 변경하기

태그

  • 자바
  • 웹 확장
  • vue
  • WWDC
  • Java FX
  • composition-api
  • WWDC20
  • 성장
  • Composition API
  • java
  • Deemo
  • Vue 3
  • ES6
  • 전개 구문
  • 프로그레시브 웹 앱
  • vue3
  • 자바 프로젝트
  • 사이드 프로젝트
  • Up
  • 자기계발
  • vuex
  • 회고
  • AstroWar
  • vue.js
  • 출간
  • pwa
  • javascript
  • spread syntax
  • vue-next
  • 이클립스

최근 댓글

  • 말씀해주신 책 사려고 하는데요, 환경 설치부터 자세하게 습⋯
    신기준
  • 늦게 답변드려 죄송합니다. iOS Safari 의 경우 웹⋯
    이근둥
  • 안녕하세요 혹시 전체 방문자는 어떻게 구현하셨나요?
    jj123
  • 안녕하세요. 아래 익명 댓글 작성자인데 암호를 잘못 입력했⋯
    이재원
  • 선생님 잘배우고 있습니다. 저는 LINUX 환경에서 작⋯
    전마머꼬

최근 글

  • Up 개발기 그리고 회고 - 3
    2023.05.31
    Up 개발기 그리고 회고 - 3
  • Up 개발기 그리고 회고 - 2
    2023.05.31
    Up 개발기 그리고 회고 - 2
  • Up 개발기 그리고 회고 - 1
    2023.05.31
    Up 개발기 그리고 회고 - 1
  • 웹 푸시 알림(Web Push Notification)
    2022.06.13
    웹 푸시 알림(Web Push Notification)
  • 스택(Stack)
    2022.05.26
    스택(Stack)

블로그 메뉴

  • 홈
  • 미디어로그
  • 방명록
hELLO · Designed By 정상우.
이근둥

근둥이의 블로그

스택(Stack)
컴퓨터 과학/자료구조

스택(Stack)

2022. 5. 26. 00:49
반응형

 


💡 정의

스택은 한쪽으로만 데이터를 넣고 뺄 수 있는 형태의 데이터 구조로, 후입 선출(Last In First Out, LIFO)이라는 특성을 지니고 있다.

차곡차곡 쌓여 있는 형태의 데이터 구조라고 보면 된다.

🌱 ADT

스택(Stack)


스택은 그림과 같이 한쪽으로만 데이터를 넣고(push), 뺄(pop) 수 있다. 스택은 일반적으로 자료를 넣고 빼는 것뿐만 아니라 가장 위에 있는 자료를 확인(peek)하거나, 스택이 비어(isEmpty)있는지 확인할 수 있다.

스택에 필요한 기능들이 어느 정도 나열되었는데, 추상 자료형을 간략하게 코드로 표현해보자.

Stack<T> {
  push(T);
  pop();
  peek();
  isEmpty();
}

어느 정도 정리되었으니 이를 C언어로 구현해보자.

👀 스택 살펴보기

스택을 구현할 수 있는 방법은 여러 가지가 있지만 이번 글에서는 배열(Array)을 활용하여 스택을 구현하려고 한다. 아래 예제 코드를 확인해보자.

#define STACK_SIZE 10

int top = -1;
int stack[STACK_SIZE];

STACK_SIZE 라는 매크로를 정의했다.

스택의 크기를 10으로 정의할 것이기 때문에 10이라는 값으로 지정해주었다.

top 이라는 정수형 변수와 stack 이라는 이름의 배열이 선언되어있다. 용도는 아래와 같다.

  • top: 스택 최상단 자료의 위치를 나타내는 변수
  • stack: 자료를 저장할 배열 (스택 공간)


top 의 초기 값이 -1인 이유는 아직 스택이 비어있기 때문이다. 즉 -1은 비어있다(empty)라는 의미로 받아들이려고 한다. 먼저 기본적으로 데이터를 넣고, 뺄 수 있는 기능을 구현해보자.

void push(int);
int pop(void);

void push(int data)
{
  // 배열 인덱스는 0부터 시작이므로, STACK_SIZE - 1
  if (top >= STACK_SIZE - 1)
  {
    printf("꽉 찼다!");
    return;
  }
  stack[++top] = data;
}

int pop(void)
{
  if (isEmpty())
  {
    printf("텅 비어있네");
    return 0;
  }
  return stack[top--];
}

데이터를 넣고 뺄 때 스택이 가득 찼는지, 아니면 비어있는지 확인할 수 있도록 조건이 추가되어있다.

여기서 주의 깊게 봐야 할 부분은 top 변수 값의 변화이다.
push 함수에서는 선위 증가되고 있고, pop 에서는 후위 감소되고 있다.

자료를 넣기 위해선 미리 위치가 정해져 있어야 하고, 반대로 뺄 때에는 자료가 나온 후 최상위 위치가 다시 계산되어야 한다.

우리 일상에서 새로운 집으로 이사간다고 생각하면 이해하기 쉬울 것이다. (먼저 집을 구한 뒤 들어가고, 나올 때에는 정리 먼저 한 후 방을 뺀다)

자료를 넣고 빼는 기능을 구현했으니, 이번에는 나머지 두 기능(peek, isEmpty)을 구현해보자.

int peek(void):
int isEmpty(void);

int peek(void)
{
  if (isEmpty())
  {
    printf("스택이 비어있어요");
    return 0;
  }
  return stack[top];
}

int isEmpty(void)
{
  return top == -1 ? 1 : 0;
}

peek은 현재 스택 최상단에 어떤 값이 있는지 확인하는 기능을 제공한다. 스택이 비어있는지 확인하고, 비어있지 않을 경우 stack[top] 위치에 있는 값을 전달해주기만 하면 된다.

isEmpty는 스택이 비어있는지 확인하는 기능을 제공한다.
우리는 top 값이 -1 일 때 스택이 비어있다고 판단하기로 했으니 이에 맞게 조건을 추가했다.

-1인 경우 1(참)을 반환하고, -1이 아닌 경우 0(거짓)을 반환하도록 했다.

 

이렇게 스택의 기본 기능을 모두 구현해보았다.

스택에 담겨져있는 값을 확인할 수 있도록 아래와 같은 함수를 추가로 구현하고,  직접 스택을 사용해보며 동작하는 모습을 확인해보자.

void printStack(void);

// 스택 값 확인을 위한 함수
void printStack(void) {
  if (isEmpty())
  {
    printf("[]\n");
    return;
  }

  printf("[ ");
  for (int i = 0; i < STACK_SIZE; i++)
  {
    if (i <= top)
    {
      printf("%d ", stack[i]);
    }
    else
    {
      printf("- ");
    }
  }
  printf("]\n");
}

 

#include <stdio.h>

#define STACK_SIZE 10

int top = -1;
int stack[STACK_SIZE];

void push(int);
int pop(void);
int peek(void);
int isEmpty(void);
void printStack(void);

void push(int data)
{
  // 배열 인덱스는 0부터 시작이므로, STACK_SIZE - 1
  if (top >= STACK_SIZE - 1)
  {
    printf("꽉 찼다!");
    return;
  }
  stack[++top] = data;
}

int pop(void)
{
  if (isEmpty())
  {
    printf("텅 비어있네");
    return 0;
  }
  return stack[top--];
}

int peek(void)
{
  if (isEmpty())
  {
    printf("스택이 비어있어요");
    return 0;
  }
  return stack[top];
}

int isEmpty(void)
{
  return top == -1 ? 1 : 0;
}

// 스택 값 확인을 위한 함수
void printStack(void) {
  if (isEmpty())
  {
    printf("[]\n");
    return;
  }

  printf("[ ");
  for (int i = 0; i < STACK_SIZE; i++)
  {
    if (i <= top)
    {
      printf("%d ", stack[i]);
    }
    else
    {
      printf("- ");
    }
  }
  printf("]\n");
}

int main(void)
{
  push(4);
  push(-102);
  push(23);
  push(9);
  push(10);
  printStack();

  int popValue = pop();
  printf("pop: %d\n", popValue);

  int peekValue = peek();
  printf("peek: %d\n", peekValue);

  pop();
  pop();
  printStack();

  return 0;
}

/*
Result
[ 4 -102 23 9 10 - - - - - ]
pop: 10
peek: 9
[ 4 -102 - - - - - - - - ]
*/

메인 함수를 살펴보면 스택에 4, -102, 23, 9, 10 값을 넣은 후 스택 값을 출력하니 차례대로 값이 스택에 들어가 있는 것을 볼 수 있다.

 

이후 값을 꺼낸 후 해당 값을 출력해보고 있다. 가장 마지막에 push 한 값은 10이기 때문에 해당 값이 먼저 꺼내졌다. (후입선출)

 

값이 꺼내진 상태에서 가장 위에 있는 값을 출력(peek)해보면 이전에 넣었던 값인 9를 확인할 수 있다.

 

마지막으로 값을 2개 더 스택에서 꺼낸 뒤 스택 내부를 보면 나머지 두 개의 값을 확인할 수 있다.


지금까지 스택에 대해 알아보았다.

 

스택 자료구조는 재귀 알고리즘에서 널리 사용하기도 하고, 몇몇 프로그래밍 언어의 동작을 살펴보면 콜 스택(Call stack)이라는 개념이 존재하기도 한다.

 

스택이라는 개념을 잘 숙지하도록 하자.

반응형
저작자표시 비영리 동일조건
    '컴퓨터 과학/자료구조' 카테고리의 다른 글
    • 배열(Array)
    • C언어로 배우는 자료구조
    이근둥
    이근둥
    새로운 것을 좋아하는 프론트엔드 개발자 ✨
    댓글쓰기

    티스토리툴바