[스택 1일차] 스택(stack)이란? - 문제7

▶ 스택이란?

  : 스택은 나중에 들어간 데이터가 먼저 나오는 구조이다

    (LIFO 구조 : Last Input First Output)

  ☞ 스택은 데이터를 저장할 스택 배열과 데이터를 저장할 위치를 알려 주는 스택 포인터 변수(sp)와 입력(push)과 출력(pop)을 담당하는 두 개의 함수로 구현된다.

 

▶ 스택 배열

  : 스택 배열은 저장할 데이터가 정수인가, 문자인가 등의 저장할 데이터의 종류에 따라 다르게 만들어야 한다.

예) 저장할 데이터가 정수인 경우     int stack[10]; 10개의 정수가 저장될 스택 배열을 만듬

예) 저장할 데이터가 문자인 경우       char stack[10]; 10개의 문자가 저장될 스택 배열을 만듬

 

▶ 스택 포인터

   : 스택은 여러 개의 데이터를 담아야 하므로 배열로 구현하지만 스택 포인터는 데이터를 저장할 위치를 알려주어야 하므로 보통 정수형 변수로 선언한다.

int sp;

 

▶ push 함수

  : 스택에 데이터를 넣는 역할을 하는 함수이다.

  - 데이터를 넣어야 하므로 넣어야 할 데이터를 전달 받을 변수로 인수로 갖는다.

void push(int data) {        stack[sp] = data;        sp++; }

 

▶ pop 함수

  : 스택에서 데이터를 꺼내는 꺼낼 데이터를 리턴하기 위해서 pop함수의 앞에는 형 지정자를 쓴다.

int pop() {         int pop_data;        sp--;        pop_data = stack[sp];        return pop_data; }

 

•  스택에서 데이터를 꺼내면 이론상으로는 스택 배열에서 데이터가 사라져야 하지만 살제로는 데이터는 그대로 있고 단지 스택 포인터의 값만 1 감소한다.
• 데이터를 스택에 넣으려면 현재 스택 포인터가 가리키는 배열 방에 스택 포인터(sp)를 1 증가시켜 주고 스택의 데이터 항목을 저장한다. 데이터 항목을 삽입하기 전에 새로운 항목을 저장할 빈 공간이 있는지 검사해야 한다. 만약 스택 포인터(sp)가 주어진 스택 크기보다 크면 오버플로우(overflow)가 발생한다.
• 데이터 항목을 삭제하려면 스택에 있는 데이터 항목을 제거하고 스택 포인터를 하나만큼 감소시켜 준다. 데이터 항목을 삭제하기 전에 스택이 비어있는지 검사해야 한다. 만약 스택 포인터(sp)가 주어지 스택 크기보다  적으면 언더플로우가 발생한다.
  
  

 

 

[ 문제 1 ] www.acmicpc.net/problem/10828

10828번: 스택

 

[ 문제 2 ] www.acmicpc.net/problem/9012

9012번: 괄호

 

[ 문제 3 ] www.acmicpc.net/problem/1874

1874번: 스택 수열

[ 문제 4 ] www.acmicpc.net/problem/9093

9093번: 단어 뒤집기

[ 문제 5 ] www.acmicpc.net/problem/1406

1406번: 에디터

 

[ 문제 6 ] www.acmicpc.net/problem/10773

10773번: 제로

 

[ 문제 7 ] www.acmicpc.net/problem/2606

2606번: 바이러스

[ 스택을 1차원 배열로 구현해서 풀이 ↓ ]

edukoi.tistory.com/132?category=917269

1. 백준 2606 - 바이러스

 

 

 

★ 이제부터 스택 + pair에 대해 알아 보도록 하겠습니다.

edukoi.tistory.com/28?category=841618

4. C++ stack 컨테이너 + pair() - 5문제