C++/ Stack 자료구조 정리

Stack의 정의

 

- 마지막에 입력된 자료가 가장 먼저 출력되는 LIFO(Last In First Out) 방식의 자료구조

- top 이라는 인덱스 위치를 통해 push와 pop이 이루어지며, 초기상태의 top은 0 또는 -1이 된다

- top의 최대 크기 = 스택의 크기

 

Stack의 응용 분야

 

- 서브루틴 호출시 복귀 주소(Return Address) 저장

- Recursive Program(재귀 함수) 수행 시 사용

- 인터럽트 발생 시 상태 저장

- 후위식 변환

- 버퍼

- 트리 운행 시(preorder, postorder, inorder)

- DFS

- Quick Sort

 

배열로 구현해본 Stack

 

C++ STL에서 stack을 제공하지만 직접 구현부터 해봐야 할 것 같아서 배열을 이용해 코드를 짜봤다

 

#include <stdio.h>

using namespace std;

#define STACK_SIZE 100
int top=-1;
int a[STACK_SIZE];

void push(int n){
    if(top>=STACK_SIZE-1){
        return STACK_FULL();
    }
    else
    {
        a[++top]=n;
    }
}

void pop(){
    if(top==-1){
        return STACK_EMPTY();
    }
    else a[top--];
}

void STACK_FULL(){
    printf("Stack is full");
}

void STACK_EMPTY(){
    printf("Stack is empty");
}

 

Stack에 새로운 아이템을 push 할 시에, top (현재 인덱스)의 크기가 스택의 크기보다 작지 않으면

스택에 공간이 없다는 뜻이므로 STACK_FULL()을 호출해준다

그게 아니라면 인덱스 증가 후 아이템 삽입

 

마찬가지로 top의 크기가 -1이라면 아이템을 추가하지 않은 상태이므로 STACK_EMPTY()를 호출해준다.

그렇지 않다면 인덱스 감소 (삭제)

 

C++ STL Stack

cplusplus에 따른 stack의 정의는 아래와 같다

stacks are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the "back" of the specific container, which is known as the top of the stack.

 

- empty

- top

- push_back

- pop_back

- size

 

기능이 기본 기능이며, swap과 replace 함수도 있다고 한다. 따로 정리하지는 않을 것이다

 

stack::empty

 

stack의 사이즈가 0이면 1을, 그렇지 않으면 0을 return하는 함수.

쓰임새는 아래 예시와 같다

stack에서 pop 연산을 수행할 때 사용.

// stack::empty
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;
  int sum (0);

  for (int i=1;i<=10;i++) mystack.push(i);

  while (!mystack.empty())
  {
     sum += mystack.top();
     mystack.pop();
  }

  std::cout << "total: " << sum << '\n';

  return 0;
}

 

stack::size

 

stack 사이즈를 리턴해주는 멤버 함수

 

// stack::size
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.pop();
  std::cout << "2. size: " << myints.size() << '\n';

  return 0;
}

 

stack::top

 

stack의 top 엘리먼트를 리턴해주는 함수. LIFO 구조이기 때문에 top 엘리먼트는 마지막에 저장된 엘리먼트가 된다.

 

// stack::top
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  mystack.push(10);
  mystack.push(20);

  mystack.top() -= 5;

  std::cout << "mystack.top() is now " << mystack.top() << '\n';

  return 0;
}

 

top의 원소를 고쳐쓰기도 가능.

 

 

push, pop은 뻔하기 때문에 정리를 하지 않겠다.

나중에 DFS 공부할 때 빡시게 정리를 해야겠다.