[자료구조] 스택 (Stack)

Stack - 스택

• 데이터를 아래서부터 위로 쌓아 올린 것
• 후입선출 (LIFO)

흔히 게임에서 '?? 버프 스택을 쌓는다'라고 얘기하는 경우가 있습니다.

Stack을 사전에 검색하면 무더기, 더미 혹은 쌓다, 포개지다는 뜻을 찾아볼 수 있습니다.

자료구조에서도 스택은 데이터들을 아래서부터 하나씩 쌓아둔 것을 말한다.

가장 먼저 들어온 데이터가 가장 밑에 깔리고 그 다음으로 들어오는 데이터가 점점 위로 쌓이는 구조이다.

스택의 아래는 막혀있고, 위로만 데이터가 들어오거나 나갈 수 있다.

 

스택 구조는 프링글스통에 비유되는 경우가 많다.

일반적인 경우 과자는 맨 위에 놓여있는 것부터 꺼내먹으며 (삭제, 팝),

꺼내놓은 과자를 다시 통에 넣어두려면 미리 들어있던 과자 위에 쌓아야 한다. (삽입, 푸시)

관련 용어 정리

탑(Top) - 스택의 맨 위 데이터

푸시(Push) - 스택의 탑 위에 데이터를 삽입

팝(Pop) - 스택의 탑의 데이터 1개를 삭제

---

특징

1. 스택의 맨 위(top)에서만 데이터의 삭제와 삽입이 일어난다. 
2. 후입선출 (LIFO)

1. 데이터를 넣고 빼는 입출구가 스택의 상단이기 때문에 중간의 데이터를 삽입하거나 삭제할 수 없다. 따라서 스택의 데이터는 스택의 탑에서만 이루어진다.

2. 특징 1로 인해 데이터가 삭제되는 데에 데이터가 삽입된 순서가 영향을 끼치게 된다. 먼저 들어온 데이터는 스택의 아래쪽에 깔리기 때문에 위쪽에 쌓여있는 나중에 입력된 데이터가 먼저 삭제되게 된다. 이를 나중에 들어온 데이터가 먼저 나가는 '후입선출'이라고 부르며 영어로는 Last In First Out을 줄여 LIFO라고 부른다.

장점

1. 데이터의 삽입과 삭제 연산의 실행시간이 짧다.
2. 입력된 데이터의 순서를 변경시키지 않는다.

1. 데이터를 삽입, 삭제할 때 다른 데이터의 간섭 없이 가장 위의 데이터(탑)에만 연산을 진행하기 때문에 연산이 간단하고 실행시간이 짧다.

2. 위와 마찬가지로 다른 데이터의 간섭이 없기에 스택의 탑 외의 데이터들의 순서를 변경시키지 않는다.

 

단점

1. 크기가 정해진 스택의 경우 데이터 삽입에 제약이 있다.

1. 크기가 유동적인 스택의 경우에는 문제가 되지 않지만, 실제 스택 메모리에는 정해진 크기가 있다. 이를 이용한 스택 오버플로우 공격 방법도 있으며, 방지하기 위해 데이터의 삽입에 제약조건을 잘 마련해야 한다.

---

데이터 다루기

스택의 데이터 연산은 다른 자료구조에 비하여 매우 간단하다.

---

탐색

스택에서는 전체 데이터를 탐색할 수 없고, 단지 맨 위의 데이터(탑)를 조회하는 것이다.

스택 연산에서 탑 조회는 Peek라고 한다.

---

삽입

데이터를 스택의 탑 위에 집어넣는다.

---

삭제

스택의 탑 데이터를 팝 연산으로 삭제한다.

---

구현

C++에서는 STL의 Stack을 활용하여 별도의 구현 없이 간단하게 스택 구조를 사용할 수 있다.

Python에서는 내장 list 함수를 활영하여 구현할 수 있고, Java에서도 java.util.Stack을 import 하여 사용할 수 있다.

해당 글에서는 연결 리스트에서 사용했던 노드 구조체를 선언하여 스택을 구현하였다.

※ 자료구조의 구현 방법은 코드 제작자에 따라 다르기 때문에 참고용으로만 봐주시기 바랍니다.

#include<bits/stdc++.h>
using namespace std;
struct node{
    char data;
    node *before=NULL;
};
node *Top=NULL;

// 스택이 비어있는지 여부를 조회
bool Empty(){ return Top==NULL; }

// 스택의 탑 데이터를 조회
void Peek(){
    if(Empty()) cout<<"Empty\n";
    else cout<<Top->data<<'\n';
}

// 스택에 문자 c를 푸시
void Push(char c){
    node *New=(node*)malloc(sizeof(node));
    New->data=c;
    if(Top!=NULL) New->before=Top;
    Top=New;
}

// 스택의 탑 데이터를 팝
void Pop(){
    if(Empty()){
        cout<<"Empty\n";
        return;
    }
    node *Del=Top;
    Top=Top->before;
    free(Del);
}

int main(){
    // A,B,C를 스택에 삽입
    for(int i=0; i<3; i++)
        Push('A'+i);
    Peek();
    
    // Pop
    Pop();
    Peek();
    
    // D를 Push
    Push('D');
    Peek();
    
    // 스택이 빌 때까지 Pop 연산
    while(!Empty()) Pop();
    Peek();
    Pop();
}

 

코드의 실행 결과

C
B
D
Empty
Empty

 

---

맺음말

스택은 컴퓨터의 실행 취소(Ctrl+Z)나 웹 페이지 뒤로 가기 등 자료구조 그 자체로 여러 곳에 사용된다.

실제 문제풀이에도 스택을 활용하는 경우가 많기 때문에 특징과 연산을 잘 알아두어야 합니다.

다음 글에서는 큐(Queue)에 대하여 알아보겠습니다.