[자료구조] Stack 스택

글의 요약 

 

목차

 

---

Stack 스택

스택은 데이터를 쌓아 올리는 자료구조이다. 스택에서 데이터의 입력과 출력은 오직 꼭대기에서만 이루어진다. 

LIFO(Last-In-First-Out) 후입선출

FILO(First-In-Last-Out) 선입후출

 

스택이 사용되는 예시

- 지역 변수는 스택에 할당된다. (변수 선언 후 수명주기가 끝나면 자동 제거 = 자동 메모리(= 스택))

- 자동 메모리, 대다수의 네트워크 프로토콜, 컴파일러 구문 분석기, 편집 되돌리기 기능

 

---

Array Stack 배열 기반의 스택 

스택 생성 초기에 프로그래머가 설정한 용량만큼의 노드를 생성한다. 최상위 노드의 위치를 가리키는 변수를 두고 삽입/삭제를 한다.

 

배열 기반의 스택 3요소

1. 용량
2. 최상위 노드의 위치
3. 노드 배열

 

 

---

 

Linked List Stack 링크드 리스트 기반 스택

링크드 리스트 기반의 스택을 만드려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 가지고 있어야 한다. 헤드와 테일에 대한 포인터가 필요하다.

 

링크드 리스트 기반의 스택의 특징

• 스택 용량에 제한을 두지 않아도 된다.
• 스택의 용량(X), 최상위 노드의 인덱스(X). Array Stack과 달리 해당 두 가지가 없다. 있어도 쓸 데가 없다.
• 배열과 달리 인덱스를 통해 노드에 접근할 수 없다.

 

 

---

 

코드 예시

#include <iostream>
#include <stack>
using namespace std;
 
int main()
{
    stack<int> s;
 
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
 
    // 비었나?
    while (s.empty() == false)
    {
        // 최상위 원소
        int data = s.top();
        // 최상위 원소 삭제
        s.pop();
 
        cout << data << endl;
    }
    
    int size = s.size();
}

---

list를 사용한 경우

#include <iostream>
#include <stack>
#include <list>
using namespace std;
 
template<typename T>
class Stack
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }
 
    void pop()
    {
        _container.pop_back();
    }
 
    T& top()
    {
        return _container.back();
    }
 
    bool empty() { return _container.empty(); }
    int size() { return _container.size(); }
 
private:
    list<T> _container;
};
 
 
int main()
{
    Stack<int> s;
 
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
 
    // 비었나?
    while (s.empty() == false)
    {
        // 최상위 원소
        int data = s.top();
        // 최상위 원소 삭제
        s.pop();
 
        cout << data << endl;
    }
    
    int size = s.size();
}

 

vector를 사용한 경우

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
 
template<typename T>
class Stack
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }
 
    void pop()
    {
        _container.pop_back();
    }
 
    T& top()
    {
        return _container.back(); // 맨 마지막에 있는 데이터의 레퍼런스를 뱉어준다.
    }
 
    bool empty() { return _container.empty(); }
    int size() { return _container.size(); }
 
private:
    vector<T> _container;
};
 
 
int main()
{
    Stack<int> s;
 
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
 
    // 비었나?
    while (s.empty() == false)
    {
        // 최상위 원소
        int data = s.top();
        // 최상위 원소 삭제
        s.pop();
 
        cout << data << endl;
    }
    
    int size = s.size();
}

결과는 같다.

 

 

---

 

#include <iostream>
#include <stack>
#include <vector>
#include <list>
using namespace std;
 
template<typename T, typename Container = vector<T>>
class Stack
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }
 
    void pop()
    {
        _container.pop_back();
    }
 
    T& top()
    {
        return _container.back();
    }
 
    bool empty() { return _container.empty(); }
    int size() { return _container.size(); }
 
private:
    Container _container;
};
 
int main()
{
    Stack<int, list<int>> s;
 
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
 
    // 비었나?
    while (s.empty() == false)
    {
        // 최상위 원소
        int data = s.top();
        // 최상위 원소 삭제
        s.pop();
 
        cout << data << endl;
    }
    
    int size = s.size();
}