[C / C++] 백준 10828번 - 스택(Stack)

백준 10828번 : https://www.acmicpc.net/problem/10828

10828번: 스택

✅ 문제 설명

말그대로 스택을 구현하는 문제이다.

 

⚡ 스택이란?

간단하게 설명하자면 입구와 출구가 같은 구조!

LIFO (Last In First Out) 로, 

접시를 쌓으면 맨 위에 놓인(맨 마지막에 놓은) 접시부터 빼는 것처럼

가장 나중에 넣은 정보를 먼저 꺼내는 구조이다.

예를 들어 a -> b -> c 순서대로 넣었다면, 뺄 때는 c -> b -> a 순서로 꺼내게 된다는 것이다.

여기서 넣는 것은 ‘push’, 빼는 것은 ‘pop’이라고 칭한다.

 

1. 초기 상태 (아무것도 없는 공백 상태)

2. push(a) -> push(b) -> push(c)

3. pop() -> pop() -> pop()

1. push X : 정수 X를 스택에 넣는다.

2. pop : 스택에서 가장 위에 있는 정수(맨 마지막에 넣은 정수)를 빼고 그 수를 출력, 만약 비어있으면 –1 출력

3. size : 스택에 들어있는 정수의 개수 출력

4. empty : 스택이 비어있으면 1, 아니면 0 출력

5. top : 스택 가장 위에 있는 정수 출력, 비어있으면 –1 출력

---

✅ 알고리즘 설명

1. 전역변수 idx를 사용

-1) 인덱스는 0부터 시작하기 때문에 0이 아니라 –1이 비어있는 상태임

-2) 따라서 초기상태는 –1로 시작하도록 설정

 

2. top()

-1) idx가 –1이면 공백이므로 –1 반환

-2) 아니면 stack[idx] (맨 위에 있는 값) 반환

 

3. push(int x)

-1) idx가 –1부터 시작했기 때문에 먼저 idx++을 하여 0으로 만들고,

-2) stack[idx]에 x 저장

 

4. pop()

-1) idx가 –1이면 공백이므로 –1 반환

-2) pop()을 하면 맨 위 정수 하나를 없애는 것이므로 idx--

-3) 없애기 전 정수를 반환해야 하므로 stack[idx+1] 반환

 

5. size()

-1) idx는 –1부터 시작하기 때문에 +1한 값이 현재 스택에 들어있는 정수의 개수

 

6. empty()

-1) idx == -1 공백

-2) idx > -1 공백 X

---

✅ 코드 [C언어]

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

int stack[10001];

/* 인덱스는 0부터 시작하기 때문에 공백은 -1 */
int idx = -1;

/* top */
// idx가 -1이면 공백, 아니면 가장 최근에 넣은 값 반환
int top() {
	if (idx == -1)return -1;
	return stack[idx];
}

/* push */
// 인덱스 +1 한 후 stack 배열에 x 넣기
void push(int x) {
	idx++;
	stack[idx] = x;
}

/* pop */
// 배열이 공백 상태면 -1 반환, 아니면 인덱스 -1 한 후 값 반환
int pop() {
	if (idx == -1) return -1;
	idx--;
	return stack[idx + 1]; // idx-- 하기 전 값을 반환해야 하므로 idx+1
}

/* size */
// 인덱스는 0부터 시작하기 때문에 +1 한 값 반환
int size() {
	return (idx + 1);
}

/* empty */
// -1이면 공백, 아니면 0반환
int empty() {
	if (idx == -1) return 1;
	else return 0;
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		char word[6];
		scanf("%s", word);
		if (strcmp(word, "push") == 0) {
			int x;
			scanf("%d", &x);
			push(x);
		}
		else if (strcmp(word, "pop") == 0)
			printf("%d\n", pop());

		else if (strcmp(word, "size") == 0)
			printf("%d\n", size());

		else if (strcmp(word, "empty") == 0)
			printf("%d\n", empty());

		else if (strcmp(word, "top") == 0)
			printf("%d\n", top());
	}
	return 0;
}

https://github.com/2hyunjinn/Baekjoon/blob/5de6d97106efeab2a84bb5180c268dac01d2115e/Baekjoon_10828.c

GitHub - 2hyunjinn/Baekjoon

위 코드는 stack의 정확한 알고리즘을 공부하기 위해서 풀어서 구현해보았다.

만약 C++을 통해 쉽게 구현하고 싶다면 이미 stack을 구현해놓은 C++의 내장함수를 사용하면 된다.

---

✅ 코드 [C++ 내장함수]

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	
	stack<int> stack;
	for (int i = 0; i < n; i++) {
		string word;
		cin >> word;
		if (word == "push") {
			int x;
			cin >> x;
			stack.push(x);
		}
		else if (word == "pop") {
			if (stack.empty()) cout << -1 << '\n';
			else {
				cout << stack.top() << '\n';
				stack.pop();
			}
		}
		else if (word == "size") {
			cout << stack.size() << '\n';
		}
		else if (word == "empty") {
			cout << stack.empty() << '\n';
		}
		else if (word == "top") {
			if (stack.empty()) cout << -1 << '\n';
			else cout << stack.top() << '\n';
		}
	}

	return 0;
}

 

https://github.com/2hyunjinn/Baekjoon/blob/7601643deb85a3f83e69779bf15ddef03a9508e7/Baekjoon_10828(2).cpp 

GitHub - 2hyunjinn/Baekjoon