스택, STL stack

시간 복잡도

1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택 관련 주요 연산/함수

push(a) : top에 원소를 추기
pop() : top에 있는 원소를 삭제
top() : top에 있는 원소 값을 조회
full() : 스택이 가득 찼는지를 검사 (배열인 경우)
empty() : 스택이 비어있으면 true, 아니면 false를 리턴
size() : 스택 사이즈를 리턴
swap(s2) : 스택 s2 와 요소를 바꿈

구현1 - 배열

#include <iostream>
using namespace std;

const int MAX_NUM = 100;

class Stack{
public:
  int data[MAX_NUM];
  int _top; // 마지막 원소를 가리키는 인덱스
  
  Stack()
  {
    _top = -1; // 초기화
  }

  // 데이터 추가
  void push(int value)
  {
    if(full())
    {
        cout << "stack overflow 에러 발생" << endl;
        exit(-1);
    }
    else
    {
      _top++;
      data[_top] = value;
    }
  }

  // top에 있는 데이터 삭제
  int pop()
  {
    if(empty())
    {
        cout << "stack overflow 에러 발생" << endl;
        exit(-1);
    }
    else
    { // data = {1,2,3,4,5}인 경우 top=4이므로 x = 5 가 저장됨
      // top 을 1 감소키키면 실제 배열 data[4] 메모리에 들어있는 값 5가 
      // 삭제되진 않지만, 어차피 나중에 data[4]에 데이터를 push 하면 
      // 기존에 들어있던 값 5는 새로 들어온 값으로 바뀜   
      int x = data[_top];
      _top--; //  
      return x; // 인덱스 top에 들어있던 데이터 값을 리턴
    }
  }

  // top에 있는 데이터 값을 조회
  int top()
  {
    if(empty())
    {
      cout << "stack overflow 에러 발생" << endl;
      exit(-1);
    }
    else
    {
      return(data[_top]);  
    }
  }
  
  // 스택이 가득찼는지 판별
  bool full()
  {
    // 마지막 원소를 가리키는 인덱스 변수 top의 값이 실제 마지막 인덱스 값 MAX_NUM -1
    // 과 동일하다면 원소가 가득찬 것이다. 
    // 인덱스는 0~99 까지이므로 -1 을 해준다.
    if(_top == MAX_NUM -1)
      return true;
    else
      return false;
  }
  
  // 스택이 비어있는지 판별
  bool empty()
  {
    // 마지막 원소를 가리키는 인덱스 값 top이 -1 이라면 스택이 비어있다는뜻
    if(_top == -1) 
      return true;
    else
      return false;
  }

  // 스택 출력. 스택의 특성에 따라서, top 원소부터 출력한다
  void printStack()
  {
    for(int i = _top; i >= 0; i--)
    {
      cout << data[i] << " ";
    }
    cout << '\n';
  }
};

int main(void)
{
  Stack mystack;

  mystack.push(100);
  mystack.printStack(); // 100 출력

  mystack.pop();
  mystack.printStack(); // x

  mystack.push(200); // 200
  mystack.push(300); // 200 300
  mystack.printStack(); // 300 200 출력

  int key = mystack.pop();  // 200
  mystack.printStack(); // 200 출력

  mystack.push(400); // 200 400 출력
  mystack.printStack(); // 400 200 출력
}

• pop() 함수 부가설명

ex) dat배열에 {13,21,30,12} 가 저장되있고 가장 상단에 위치한 데이터 12 를 pop() 으로 삭제하는 경우,
그냥 pos을 1 줄이면 된다. ( pos는 4 => 3으로 변경될 것이다.)
이때 dat 3번지에 있는 값 12 자체는 굳이 변경하지 않아도 된다.
왜냐하면, 나중에 push가 발생하면 어차피 그때 들어올 값으로 덮어써질것이다.
(저 12라는 값은 아무 의미가 없고, 굳이 값을 변경하는 추가적인 연산을 하는게 시간낭비가 된다.)

구현 2 - 링크드 리스트

#include <iostream>
using namespace std;

const int MAX_NUM = 100;

class Stack{
public:
  int data[MAX_NUM];
  int _top; // 마지막 원소를 가리키는 인덱스
  
  Stack()
  {
    _top = -1; // 초기화
  }

  // 데이터 추가
  void push(int value)
  {
    if(full())
    {
        cout << "stack overflow 에러 발생" << endl;
        exit(-1);
    }
    else
    {
      _top++;
      data[_top] = value;
    }
  }

  // top에 있는 데이터 삭제
  int pop()
  {
    if(empty())
    {
        cout << "stack overflow 에러 발생" << endl;
        exit(-1);
    }
    else
    { // data = {1,2,3,4,5}인 경우 top=4이므로 x = 5 가 저장됨
      // top 을 1 감소키키면 실제 배열 data[4] 메모리에 들어있는 값 5가 
      // 삭제되진 않지만, 어차피 나중에 data[4]에 데이터를 push 하면 
      // 기존에 들어있던 값 5는 새로 들어온 값으로 바뀜   
      int x = data[_top];
      _top--; //  
      return x; // 인덱스 top에 들어있던 데이터 값을 리턴
    }
  }

  // top에 있는 데이터 값을 조회
  int top()
  {
    if(empty())
    {
      cout << "stack overflow 에러 발생" << endl;
      exit(-1);
    }
    else
    {
      return(data[_top]);  
    }
  }
  
  // 스택이 가득찼는지 판별
  bool full()
  {
    // 마지막 원소를 가리키는 인덱스 변수 top의 값이 실제 마지막 인덱스 값 MAX_NUM -1
    // 과 동일하다면 원소가 가득찬 것이다. 
    // 인덱스는 0~99 까지이므로 -1 을 해준다.
    if(_top == MAX_NUM -1)
      return true;
    else
      return false;
  }
  
  // 스택이 비어있는지 판별
  bool empty()
  {
    // 마지막 원소를 가리키는 인덱스 값 top이 -1 이라면 스택이 비어있다는뜻
    if(_top == -1) 
      return true;
    else
      return false;
  }

  // 스택 출력. 스택의 특성에 따라서, top 원소부터 출력한다
  void printStack()
  {
    for(int i = _top; i >= 0; i--)
    {
      cout << data[i] << " ";
    }
    cout << '\n';
  }
};

int main(void)
{
  Stack mystack;

  mystack.push(100);
  mystack.printStack(); // 100 출력

  mystack.pop();
  mystack.printStack(); // x

  mystack.push(200); // 200
  mystack.push(300); // 200 300
  mystack.printStack(); // 300 200 출력

  int key = mystack.pop();  // 200
  mystack.printStack(); // 200 출력

  mystack.push(400); // 200 400 출력
  mystack.printStack(); // 400 200 출력
}

STL stack

스택 선언

#include < stack >
stack< int > s;
stack< char > s;

메소드

push(a) : top에 원소를 추기
pop() : top에 있는 원소를 삭제
top() : top에 있는 원소를 리턴
empty() : 스택이 비어있으면 true, 아니면 false를 리턴
size() : 스택 사이즈를 리턴
swap(s2) : 스택 s2 와 요소를 바꿈

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
  stack{int> S;
  S.push(10);
  S.push(20);
  S.push(30);
  if(S.empty()) // empty()
  {
    cout << S.size() << "S is empty\n"; // size()
  }
  else
  {
    cout << "S is not empty\n";
  }
  
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  
  // stack이 비어있는데 pop() 또는 top() 을 호출하면 runtime error가 발생한다
  S.pop();
  cout << S.top() << '\n'; // runtime error 
}