[스택] Stack 이란?

Stack 이란?

스택 (Stack) 특징을 가장 잘 나타내는 표현은 후입선출(Last In First Out, LIFO) 이다.

▶ 스택(Stack)은 삽입(push)과 삭제(pop)이 한쪽 끝에서만 일어나는 구조

    가장 상단에 위치한 원소를 가리키는 용어로 "top" 이라고 사용하기도 한다.

 

예제

- 재귀(Recursive) 함수

- 상자에 물건을 놓으면 맨 밑부터 쌓고, 위에서 부터 차례대로 꺼내는 형태이다.

- 웹 서핑에 있어서 뒤로가기를 하면 가장 최근에 방문한 페이지부터 보여준다.

- 역순 문자열 만들기

- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

    ex) 올바른 괄호 문자열 (VPS, Valid Parenthesis String)

- 후위 표기법

 

Stack 구현은 "자료구조" 과목에서도 서두에 다룰 정도로 기초가 되는 개념이다.

배열 Array 로 구현하는 형태부터 연결리스트를 이용한 방식이 존재한다.

 

또한, 알고리즘 문제에서도 유용하게 사용되는 자료구조이다.

※ C++ STL로 구현한 Stack 글 참고

[C++] [STL] Stack

 

구현

해당 게시글에서는 배열 Array로 구현한 형태를 다룬다.

#include <stdio.h>

const int SIZE = 10;

struct Stack
{
    int top = -1;
    int arr[SIZE];

    void push(int data)
    {
        arr[++top] = data;
    }

    int pop()
    {
        return arr[top--];
    }
}stack;


int main()
{
    int data[] = { 3, 2, 5, 4, 1 };
    for (int i = 0; i < 5; ++i)
    {
        stack.push(data[i]);
    }

    for (int i = 0; i < 5; ++i)
    {
        printf("%d\n", stack.pop());
    }
}

 

직접 구현시 고려사항

- Stack 크기 (Size)

  (정적할당하는 경우에는 초기에 배열 크기 설정 필요)

- Stack이 비워져(Empty) 있는데 pop 하는 경우

- Stack이 가득 찬 상태(Full)에서 push 하는 경우

- Stack에서 Start Index (0  or  1)

 

Reference

- [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교  

- [스택] Stack (동적할당, 연결리스트 구현)

- [스택] Stack (Memory Pool 방식 구현) 

 

관련 문제

- [BOJ] 10828 스택

- [SWEA] 1218 괄호 짝짓기 

- [Jungol] 1102 스택(stack) 

- [Jungol] 3690 stack api 

- [Jungol] 1328 빌딩 

- [Jungol] 2538 PATRIK 

- [BOJ] 6549 히스토그램에서 가장 큰 직사각형 

- [BOJ] 2504 괄호의값 

- [Jungol] 1141 불쾌한 날(Bad Hair Day)