C언어로 구현하는 자료구조(stack)

이번에 알아볼 자료구조 stack이라는 자료구조이다

스택이란

한쪽끝에서만 자료를 넣고 뺴는 기능이 있는 Last In First Out(LIFO) 자료구조 이다

스택의 기능

스택에서는 주로 4개정도의 메서드가 사용된다.

push(): 스택의 가장 윗 부분에 자료를 넣는다

pop(): 스택에서 가장 위에 있는 항목을 반환과 동시에 제거한다

peek(): 스택에서 가장 위에 있는 항목을 반환한다.

isEmpty(): 스택이 비어있는지 아닌지 확인한다.

스택 구현 해보기

typedef struct array{
    int arr[500002];
	int idx;
}Stack;

Stack stack;
  
void Initiallize(Stack* stack){stack->idx = -1;}
  
bool empty(Stack*stack) {return stack->idx==-1;}
  
void Spush(Stack* stack,int data){stack->arr[++stack->idx] = data;}
  
int Spop(Stack* stack) {return stack->arr[stack->idx--];}
  
int Speek(Stack* stack) {return stack->arr[stack->idx];}

연결리스트 대신 배열로 구현한 코드이다.

스택을 이용하여 알고리즘 문제 해결해보기

외계인의 기타연주(백준 2841)

개인적으로 스택을 정말 잘 나타낸 문제이며 문제를 보면 바로 스택을 쓴다고 알수있다.

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

해결법

이 문제를 해석하면 지금 누르고 있는것보다 작은 프렛이 들어올경우 그것보다 높은 프렛을 모두 떼야 그 멜로디를 소리낼수가 있다. 그러므로 스택을 이용하여 내가 누르고 있는거보다 작은 프렛이 나오거나 아무것도 안누르고 있을때 그 음을 연주하는 식으로 구현하면 된다.

#include<stdio.h>
typedef struct array
{
	int arr[500002];
	int idx;
}Stack;

Stack stack[7];

void Initiallize(Stack* stack) {
	stack->idx = -1;
}
int empty(Stack* stack) {
	if (stack->idx == -1)return 1;
	else return 0;
}
void Spush(Stack* stack, int data) {
	stack->arr[++stack->idx] = data;
}
int Spop(Stack* stack) {
	return stack->arr[stack->idx--];
}
int Speek(Stack* stack) {
	return stack->arr[stack->idx];
}

int main()
{
  for (int i = 1;i <= 6;i++) 
     Initiallize(&stack[i]);
  int n, p, count = 0, n1, p1;
  scanf("%d%d", &n, &p);
  for (int i = 0;i < n;i++) {
      scanf("%d%d", &n1, &p1);
          while (!empty(&stack[n1]) && Speek(&stack[n1]) > p1) {
          Spop(&stack[n1]);
          count++;
      }
      if (empty(&stack[n1]) || Speek(&stack[n1]) < p1) {
          Spush(&stack[n1], p1);
          count++;
      }
  }
  printf("%d", count);
  return 0;
}

최대 6개의 줄이니까 6개의 스택을 만들어 준뒤 주어지는 줄 입력에따라서 push,pop을 반복하면 쉽게 구할수있다.