[자료구조] 스택(Stack) - 코딩기록

자료구조

자료구조에 대해 간단히만 짚고 넘어가겠다.

자료구조의 정의는 컴퓨터과학에서 효율적인 접근과 수정을 가능하게 해주는 자료의 조직, 관리, 저장을 의미한다. 자료구조를 통해 데이터를 효율적으로 저장, 관리할 수 있고 메모리를 절약하거나 시간을 단축할 수 있다. 우리가 흔히 말하는 알고리즘과는 약간의 차이가 있다. 자료구조는 이름처럼 데이터를 저장하기 위한 구조이고 알고리즘은 자료구조에 있는 데이터를 활용해 문제를 해결하는 방법이라고 할 수 있다. 즉, 자료구조를 잘 익혀두면 문제를 더 효율적으로 해결할 수 있을 것이다. 이 포스팅에서 다룰 것은 자료구조에서 선형구조 중 하나인 스택이다.

스택

스택은 '쌓다'라는 뜻을 가지고 있다. 이 말처럼 스택을 이해할 때 탑을 상상하면 편하다.

다음과 같은 탑이 있다. 탑에 써 있는 숫자는 들어온 순서를 의미한다. 우리는 탑을 쌓을 때 당연히 밑에서부터 쌓아야 한다. 1번, 2번, 3번, 4번 이렇게 차례로 탑을 쌓았다.

 

5번 사각형을 이 탑에 추가하려면 어떻게 해야 할까? 당연히 4번 사각형 위에 쌓아야 할 것이다. 이것이 바로 스택에서 원소를 추가하는 삽입 연산(push)이다.

 

그렇다면 저 탑에서 사각형을 삭제하려면 어떻게 해야 할까? 가장 위에 있는 4번 원소를 빼면 될 것이다. 가장 최근에 들어온 원소를 나가게 하는 것이 삭제 연산(pop)이다. 

 

위에서 얘기한 것이 스택이 작동하는 방식이다. 정리하자면,

스택은 가장 먼저(예전에) 들어온 데이터가 맨 아래로 가고 그 후 입력되는 데이터들이 위에 쌓이는 구조를 가진 자료구조이다. 스택의 가장 큰 특징은 LIFO 형태라는 것이다. LIFO란 후입선출(Last - In - First - Out)을 의미하고 가장 최근에 들어온 데이터가 가장 먼저 나간다는 뜻이다.

 

스택의 기능

이제 스택STL을 활용해 스택의 기능들을 살펴보겠다.

• push(x) : 원소 x를 추가
• pop() : 스택에 원소가 있다면 제일 위에 있는 원소를 삭제하고 반환
• empty() : 스택이 비어있으면 1, 비어있지 않으면 0을 반환
• top() : 가장 위에 있는 원소를 반환
• size() : 스택의 원소 개수 반환

이렇게만 보면 크게 와닿지 않을 것이다. 코드와 함께 다시 살펴보겠다.

#include <iostream>
#include <stack> //스택의 헤더파일
using namespace std;

//st라는 int형 스택을 선언하는 방법.
stack <int> st;

int main()
{
    st.push(1);
    st.push(2);
    st.push(3);//스택에 1,2,3을 차례로 삽입
    
    cout<<st.size()<<"\n";//스택의 사이즈 출력
    
    st.pop();//가장 위 원소 삭제 및 반환
    
    cout<<st.size()<<"\n";//스택의 사이즈 출력
    
    cout<<st.empty()<<"\n";//스택이 비어있지 않다면 0출력
    
    cout<<st.top()<<"\n";//스택의 맨 위 원소 출력
    return 0;
}

다음과 같은 코드를 실행하면 

3

2

0

2

다음과 같이 출력된다.

 

스택을 활용한 간단한 문제로 스택을 이해하는 데 도움을 줄 수 있다.

https://www.acmicpc.net/problem/10828

10828번: 스택

https://www.acmicpc.net/problem/10773

10773번: 제로

[백준 문제풀이] - [백준] 10773번 제로(c++) 문제풀이

제로의 문제풀이다.

[백준] 10773번 제로(c++) 문제풀이