STACK

STACK의 개념

STACK은 입구가 하나라 처음에 들어온 것이 가장 마지막에 나간다는 개념이다. 그렇기 때문에 STACK을 LIFO라고도 한다. 스택은 중간의 자료에 접근할 수 없으며 오직 마지막 자료에만 접근이 가능하다.
LIFO : Last In First Out

대표적인 스택의 기능

• push : 스택에 자료를 넣는다.

• pop : 스택의 자료를 뺀다.

• top : 입구 가장 가까운 자료에 대한 정보이다.

• empty : 스택이 비어있는지 여부이다.

• size : 스택의 크기를 나타낸다.

  push

  

  pop

  

STACK 구현 & 라이브러리

C언어에서는 스택라이브러리가 존재하지 않아 구현하여 사용한다. 하지만 연습할때나 스택을 구현해보는 것이지 실제로 스택을 구현하는 일은 거의 없다고 보면된다.
특히 C++이나 Java에서는 스택 라이브러리를 제공하기 때문에 라이브러리를 자유롭게 사용하면 된다. Python같은 경우는 list가 스택의 기능을 대신하고 있다.

c에서의 스택

int stack[9999];
int size = 0;

void push(int data){
    stack[size] = data;
    size++;
    }
    
void pop(){
    stack[size - 1] = 0;
    size--;
    }
    
int top(){
    return stack[size - 1];
    }
    
int empty(){
    if( size == 0 )
    	return true;
    return false;
    }

int size(){
    return size;
    }

C++에서의 스택

#include<iostream>
#include<stack>
int main(){
    stack<int> s;
    s.push(10);
    s.push(9);
    s.pop();
    s.empty();
    s.pop();
}
    

STACK을 사용하는 문제

1. 마지막에 나오는 자료가 의미가 있는 경우.
2. 주로 뒤집기 문제에서 활용됨.

문제

단어뒤집기 문제

풀이
0. 입력된 sentence의 원소 하나하나에 접근하여 판단한다.
1. 단어를 구분할때 띄워쓰기와 엔터로 구분한다.
2. 만약 원소가 ' ' 와 '\n'이 아닌경우는 알파벳인 경우이므로 스택에 넣어준다.
3. 만약 원소가 ' ' 나 '\n'인 경우는 한 단어가 끝난 경우이므로 스택에 저장되어 있던 모든 자료를 pop을 해준다.

SUDO CODE

GET sentence
FOR sentence in ch
	IF (ch == ' ') OR (ch == '\n') THAN
    	WHILE stack is not empty
        	SHOW STACK TOP
    		STACK POP
        ENDWHILE
        SHOW ch
    ELSE 
    	STACK PUSH ch
    ENDWIF-ELSE
ENDFOR

괄호 문제

풀이
0. 입력된 bracket의 원소 하나하나에 접근하여 판단한다.
1. 원소가 '('인 경우 stack에 '('를 push한다.
2. 원소가 ')'인 경우 stack pop을 한다.
3. 만약 원소가 ')'이고 stack이 비어있는 경우 False인 경우이다.
4. 입력된 bracket이 소진되었는데 stack이 비어있지 않은 경우 False인 경우이다.

SUDO CODE

GET bracket
FOR bracket in ch
	IF (ch == '(') THAN
    	STACK PUSH
    ELSE 
    	IF (stack is empty) THEN
        	RETURN FALSE
            BREAK
        ENDIF
        STACK POP
    ENDWIF-ELSE
ENDFOR
IF (stack is not empty) THEN
	RETURN FALSE
ENDWIF
RETURN TRUE

스택수열 문제
풀이
0. 입력된 sequence 원소 하나하나에 접근한다. (count값은 스택에 들어갈 숫자이다.)
1. count가 sequence보다 작은 경우 count가 sequence보다 커질 때까지 스택에 count값을 push하고 count값을 증가시킨다.
2. 스택의 top과 sequence가 같은경우 pop을 실행.
3. 스택의 top이 sequence다 큰 경우 수열이 성립이 되지 않는다. -> 프로그램 종료
4. 위의 과정을 수열이 끝날때까지 반복.
5. 정상적으로 모든 수열이 끝난 경우 수열이 성립되는 경우이다.

GET sequence // 수열 원소

WHILE (count <= sequence)
	STACK PUSH count
    count++
ENDWHILE

IF (STACK TOP == sequence)
	STACK POP
ELSE IF (STACK TOP > sequence)
	RETURN False
ENDIF_ELSE

에디터 문제
풀이