9일차

스택

∙ 스택이란?

- stack : 물건을 쌓아 올린 더미 또는 쌓는 행위

- 자료 구조에서 스택은 데이터를 쌓아 올리듯이 저장하는 선형 자료 구조로서, 후입선출 원리에 따라 삽입과 삭제가 수행됨

- 후입선출 (LIFO, Last-in First-out)  : 나중에 들어온 데이터가 먼저 출력됨 

- 데이터의 입출력이 한쪽 방향에서만 수행되는 리스트

ex) 텍스트 편집기의 실행 취소 가능, 웹 브라우저에서 뒤로 가기, 함수 호출 시 복귀 주소 기억

 

∙ 스택의 주요 연산

- push(e) : 스택의 맨 위에 원소 e를 추가

- pop() : 스택의 맨 위에 있는 원소를 삭제

- top() : 스택의 맨 위에 있는 원소를 참조. peek()

- empty() : 스택이 비어 있으면 true를 반환

- size() : 스택의 원소 개수를 반환

 

∙ 배열을 이용한 스택의 구현

- 미리 정해진 크기의 배열을 할당하고, 가장 최근에 입력된 자료 위치를 가리키는 t 변수를 사용

> pus(e) : t 값을 1 증가시키고, 해당 위치에 e를 대입

> pop() : t 값을 1 감소

> top() : arr[t] 값을 반환 

- 장점 : 구현이 간단하고, 삽입이나 삭제가 빠르게 동작

- 단점 : 미리 정해진 크기보다 많은 데이터를 삽입할 경우, 스택 오버플로우(stack overflow) 에러가 발생

 

 

∙ 연결 리스트를 이용하여 스택의 구현

- 단순 연결 리스트를 이용하여, 새로 추가한 데이터를 연결 리스트 맨 앞에 삽입하는 방식

> push(e) : push_first(e)

> pop() : pop_first()

> top() : head -> next 값을 반환

- 장점 : 크기가 제한되지 않음

- 단점 : 구현이 복잡하고, 삽입이나 삭제 시간이 오래 걸림

 

∙ 스택 구현 코드

#include <iostream>
#include <vector>

// vector을 이용하여 구현한 스택 자료구조
template <typename T>
class Stack
{
public:
    Stack() {}
    
    void push(const T& e) { v.push_back(e); }
    void pop() { v.pop_back(); }
    const T& top() const { return v.back(); }
    
    bool empty() const { return v.empty(); }
    int size() const { return v.size(); }
    
private:
    std::vector<T> v;
};

using namespace std;

int main()
{
    // 스택 생성
    Stack<int> stk;

    // 스택에 데이터 넣기
    stk.push(10); // 10
    stk.push(20); //20, 10
    stk.push(30); // 30, 20, 10
    
    // 맨 위에 있는 데이터 꺼내기
    stk.pop(); // 20, 30
    
    // 맨 위에 있는 데이터 참조하여 보여주기
    cout << stk.top() << endl;  // 20
    
    stk.push(40);
    
    // 스택에 저장된 데이터 확인
    while (!stk.empty()){
        auto& e = stk.top(); // 데이터를 참조형 변수로 받아오는 코드
        cout << e << ", ";
        stk.pop();
    }
    cout << endl;
    
}

 

 

∙ std::stack

- LIFO(Last-In First-Out) 방식의 스택 자료 구조를 구현한 컨테이너 어댑터

- 템플릿 매개변수 T는 스택에 저장할 타입을 지정하고, Container에는 내부에서 사용할 컨테이너를 지정

- Container에는 deque, vector, list를 지정할 수 있음

- <stack>에 정의되어 있음

 

∙ stack 예제코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<int> stk;
    
    // 스택에 데이터 넣기
    stk.push(10); // 10
    stk.push(20); //20, 10
    stk.push(30); // 30, 20, 10
    
    // 맨 위에 있는 데이터 꺼내기
    stk.pop(); // 20, 30
    
    // 맨 위에 있는 데이터 참조하여 보여주기
    cout << stk.top() << endl;  // 20
    
    stk.push(40);
    
    // 스택에 저장된 데이터 확인
    while (!stk.empty()){
        auto& e = stk.top(); // 데이터를 참조형 변수로 받아오는 코드
        cout << e << ", ";
        stk.pop();
    }
    cout << endl;
}