[자료구조]스택(Stack)

정의

• 스택은 top 이라고 하는 한쪽 위치에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 입니다.
• 후입선출(Last In First Out : LIFO) 의 특징을 가지고 있습니다.

  

 

스택에 원소 삽입 및 삭제

• top 위치는 다음 데이터를 넣을 수 있는 위치를 가르킨다.
• push() 에서 top의 위치에 데이터를 입력 후 다음 데이터를 넣을 수 있는 위치로 이동한다.
• pop() 에서는 top의 위치를 이전의 위치로 먼저 이동 후에 그 위치의 값을 반환한다.

 

 

스택의 ADT(추상데이터타입)

structure Stack 
  objects: 0개 이상의 원소를 가진 유한 순서 리스트 
  functions: 
     모든 stack∈ Stack, item∈ element, max_stack_size∈ positive integer 
     Boolean IsFull(stack, max_stack_size) ::= 
              if (stack의 원소수 == max_stack_size) return TRUE 
              else return FALSE 
     Stack Push(stack, item) ::= 
             if (IsFull(stack)) stackFull 
             else stack의 Top에 item을 삽입하고 return 
     Boolean IsEmpty(stack) ::= 
             if (stack의 원소수 == 0)) return TRUE 
             else return FALSE 
     Element Pop(stack) ::= 
             if (IsEmpty(stack)) return 
             else 스택 Top 의 item을 제거해서 반환

 

 

스택 구현

•일차원 배열 stack[MAX_STACK_SIZE] 사용 •i 번째 원소는 stack[i-1]에 저장 •변수 top은 항상 스택의 최상위 원소를 가리키도록 함 (초기화: top = 0; 공백 스택을 의미함)

     int top = 0;
     Element stack[max_stack_size];
     
     
     Boolean isFull() 
     {
              if (top == max_stack_size) return TRUE 
              else return FALSE 
     }
     void push(Element item) 
     {
     	stack[top++]=item;
     }
     
     Boolean isEmpty()
     {     
             if (top == 0)) return TRUE 
             else return FALSE 
     }
     Element pop(){
     {
		return stack[--top];
     }

 

STL stack 사용법

• 스택 변수 생성

  stack <자료형> 변수명​

• 스택에 데이터 추가하기

  stack.push(element)​

• 스택에 데이터 삭제하기

  stack.pop()​

• 스택에서 가장 마지막 데이터 반환

  stack.top()​

• 스택의 크기 반환

  stack.size()​

• 스택이 비어있는지 확인

  stack.empty()​

 

스택을 활용한 문제

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

입력 예를 살펴 보면

8
4
3
6
8
7
5
2
1

1부터 8까지의 수 중에서 4 가 맨 처음 출력 되기 위해서는 1,2,3,4 를 push 한 다음 pop 을 하면 4가 출력 된다.

그 다음 pop을 하면 3이 출력 되며 스택에 1,2 가 남아 있다.

6이 출력 되기 위해서는 5,6을 스택에 넣은 후 pop을 한다.

8이 출력 되기 위해서는 7,8을 스택에 넣은 후 pop을 한다.

이때 스택에 남아 있는 수는 1,2,5,7 이다.

연속으로 4번 pop 을 하면 7,5,2,1 이 빠져 나온다.

따라서 나오는 숫자까지 스택에 push 후 해당 데이터를 pop 하는 형식으로 프로그램을 해 주면 되는데 순서가 맞지 않는다면 NO를 출력하면 됩니다.

 

int main()
{
    int n;
    int pushnum=0; //마지막 입력된 숫자.
    int rescnt=0;
    char resarr[200001];
    stack <int> st;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        int num;
        scanf("%d",&num);
        if(pushnum < num)
        {
            while(pushnum < num) {
                st.push(++pushnum);
                resarr[rescnt++]='+';
            }
        }
        if(st.top()!=num)
        {
            cout << "NO\n";
            return 0;
        }
        st.pop();
        resarr[rescnt++]='-';

    }
    for(int i=0;i<rescnt;i++) printf("%c\n",resarr[i]);

    return 0;
}