Stack

Stack : 무언가를 쌓는다는 의미를 갖는 자료구조, 후입선출 (LIFO)의 자료구조

1. stack 이해하기

• 바닥이 막힌 상자를 연상하자
• 가장 먼저 넣은 것이 맨 밑에 가고 최근에 넣은 것이 맨 위에 온다 -> 가장 최근의 넣은 자료를 가장 먼저 빼낼 수 있음
• stack의 의미: 힙 영역 메모리에서 일반적인 데이터를 저장하는 것으로 스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택
• 최근정보를 얻었을 때 유리함.

2. stack를 어떨 때 사용하는가?

• 최근 정보를 얻었을 때 유리
  (그만큼 최근 정보를 손쉽게 빼낼 수 있기 때문)

3. stack에 적용하는 두 가지 연산

• push : stack에 한 개 원소를 저장

• pop : stack로부터 한 개 원소를 취함

  +) empty (stack이 비어있는지 원소를 빼낼 때 체크), full (stack이 가득 차 있는지 원소를 넣을 때 체크)를 판별하는 것도 필요함.

4. 스택구현 (백준 10828번)
   예) 배열을 이용하여 구현할 때
   1) 스택을 위한 배열 하나 잡아두기
   2) index값을 0으로 잡기
   3) index = 0 이면 스택이 비어있는 것, 스택에 어떤 것을 집어넣을 때는 index자리에 집어넣고 index++
   4) index가 초기 배열크기 이상이면 스택이 가득 찬것(stack_full)
   5) 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.
   +) 백준 문제 풀이
   

#include <stdio.h>
#include <string.h>

int num[10001];
int count = 0;

void push(int x){
num[count] = x;
count ++;
}

void pop(){
if (count != 0){
count --;
printf ("%d\n", num[count]);
}
else printf ("-1\n");
}

void size(){
printf ("%d\n", count);
}

void empty(){
if (count != 0) printf ("0\n");
else printf ("1\n");
}

void top(){
if (count != 0) printf ("%d\n", num[count-1]);
//count-1 은 배열의 특성
else printf ("-1\n");
}

int main(void) {
int n; //명령의 수
int x = 0;
char command[10];

scanf ("%d", &n);

for (int i=0; i<n; i++){
scanf ("%s", command);
if (strcmp (command, "push") == 0){
scanf ("%d", &x);
push(x);
}
else if (strcmp (command, "pop") == 0) pop();
else if (strcmp (command, "size") == 0) size();
else if (strcmp (command, "empty") == 0) empty();
else if (strcmp (command, "top") == 0) top();
}

return 0;
}