스택

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능

• top의 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 구조

• 마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제 (First-Out)됨

☞ 후입선출 구조 (LIFO, Last-In-First-Out)

스택의 이해 : 스택의 개념과 구조

스택의 연산

ƒ 스택에서의 삽입 연산 : push

ƒ 스택에서의 삭제 연산 : pop

 

스택의 push() 알고리즘

①top ← top+1;

− 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입 하려면 먼저 top의 위치를 하나 증가

− 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우 (overflow)상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료

② S(top) ← x;

− 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입

push(S,x)
1) top <- top +1;
if( top >stack_SIZE) then overflow;
else
2) S(top)<-x;

end push()

스택의 pop() 알고리즘

① return S(top);

− 공백 스택이 아니면 top에 있는 원소를 삭제하고 반환

② top ← top-1;

− 스택의 마지막 원소가 삭제되면 그 아래 원소, 즉 스택에 남아 있는 원소 중에서 가장 위에 있는 원소가 top이 되어야 하므로 top 위치 를 하나 감소

pop(S)
if(top=0) then underflow;
else{
	return S(top);
    top<- top -1;
    }
end pop()

순차 자료구조를 이용한 스택의 구현

ƒ 순차 자료구조인 1차원 배열을 이용하여 구현

• 스택의 크기 : 배열의 크기

• 스택에 저장된 원소의 순서 : 배열 원소의 인덱스

− 인덱스 0번 : 스택의 첫번째 원소

− 인덱스 n-1번 : 스택의 n번째 원소

• 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장

− 공백 상태 : top = -1 (초기값)

− 포화 상태 : top = n-1

 

ƒ순차 자료구조로 구현한 스택의 장점

• 순차 자료구조인 1차원 배열을 사용하여 쉽게 구현 ƒ순차 자료구조로 구현한 스택의 단점

• 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움

• 순차 자료구조의 단점을 그대로 가짐

 

™ 연결 자료구조를 이용한 스택의 구현

ƒ 단순 연결 리스트를 이용하여 구현

• 스택의 원소 : 단순 연결 리스트의 노드

− 스택 원소의 순서 : 노드의 링크 포인터로 연결

− push : 리스트의 마지막에 노드 삽입

− pop : 리스트의 마지막 노드 삭제

• 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수

− 초기 상태 : top = null

 

역순 문자열 만들기

ƒ 스택의 후입선출(LIFO) 성질을 이용

① 문자열을 순서대로 스택에 삽입

 

시스템 스택

ƒ 프로그램에서의 호출과 복귀에 따른 수행 순서를 관리

• 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로,

후입선출 구조의 스택을 이용하여 수행순서 관리

• 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수,

매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임(stack frame)에 저장하여 시스템 스택에 삽입

• 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop) 하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀

• 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백스택이 됨

 

™ 수식의 괄호 검사

ƒ 수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어있으므로, 후입선출 구조의 스택을 이용하여 괄호를 검사한다.

ƒ 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사

 

① 왼쪽 괄호를 만나면 스택에 push

② 오른쪽 괄호를 만나면 스택을 pop하여 마지막에 저장한 괄호와 같은 종류 인지를 확인

수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨

 

수식의 표기법

ƒ 전위표기법(prefix notation)

• 연산자를 피연산자의 앞에 표기하는 방법 예) +AB

ƒ 중위표기법(infix notation)

• 연산자를 피연산자의 가운데 표기하는 방법 예) A+B

ƒ 후위표기법(postfix notation)

• 연산자를 피연산자 뒤에 표기하는 방법 예) AB+

 

컴퓨터 내부에서 스택을 사용해 중위 표기법을 후위 표기법 으로 바꾸는 방법

infix_to_postfix(exp)
	while(true)do{
    	symbol <- getSymbol(exp);
        case{
        	symbol = operand : // 피연산자 처리 : 출력
            			print(symbol);
            symbol = operator : // 연산자 처리 : 스택에 push
            			push(stack,symbol);
            symbol = ")" :
            			print(pop(stack)); //오른쪽 괄호 처리 : 스택을 pop하여 출력
            symbol = null:    // 수식의 끝 처리
            			while(top> -1) do //스택이 공백이 될때까지 pop하여 출력 (stack 탑이 -1 이 처음)
                        	print(pop(stack));
            else :
            }
       }
   }
end infix_to_postfix()

( 는 무시

 

™ 스택을 이용한 후위 표기법 수식의 연산

ƒ 스택을 사용해 후위 표기법 수식을 계산하는 방법

 evalPostfix(exp)
 	while(true) do{
    symbol <- getSymbol(exp);
    case{
    	symbol = operand : // 피연산자 처리
        			push(Stack,symbol);
        symbol = operator : // 연산자 처리
        			opr2 <- pop(Stack);
                    opr1 <- pop(stack);
                    result <- opr1 op(symbol) opr2;
                    push(Stack, result);
        symbol = null:
        			print(pop(Stack));
        }
    }
end evalPostfix()

 

백준 스택 문제 한문제라도 풀기 

10828 번

#include <iostream>
using namespace std;

int main() {
  // 명령의 수 N 입력받기
  int N;

  cin >> N;
  for ( int i=0; i<N; i++){
    
  }
}

void push(){

}

int pop(){

}

int size(){

}

bool empty(){

}

int top(){

}

음.. push 1 을 입력받으면

push 라는 함수에 1을 집어넣어야 하는건데

이걸 push 인걸

str로 입력받아야 하는거야?

어케해..ㅜ포인터써야하나..