[바킹독 강의]스택 정리

스택

스택이란 한쪽 끝에서만 넣고 뺄 수 있는 자료구조

구조적으로 먼저 들어온 원소가 나중에 나오게 된다.

참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있습니다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다.

 

스택은 특정 위치에서만 원소를 넣거나 뺄 수 있게 제한을 둔 대신에 원소의 추가와 제거가 모두 O(1)입니다. 나중에 구현을 같이 해보겠지만 우리가 배열의 끝에서 원소를 추가/제거할 때 시간복잡도가 O(1)이었던 것과 완전 상황이 똑같습니다. 그리고 제일 상단의 원소 확인 또한 O(1)입니다.

 

대신 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능합니다. -> 그렇지만 응용을 통해서 해당 기능이 가능하도록 할 수 있다.

 

배열을 이용한 스택 구현하기

const int MX = 1000005;
int dat[MX];
int pos=0;

스택을 배열로 구현할 때에는 단지 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요

{13, 21, 30}이 담겨있는 스택을 나타내기 위해 dat[0], dat[1], dat[2] 각각에 13, 21, 30을 썼고 pos는 3이라는 값을 가집니다. 이와 같이 스택의 값들은 dat의 0번지부터 저장되고 pos는 다음에 원소가 추가될 때 삽입해야하는 곳을 가리키고 있습니다. 그리고 잘 생각해보면 pos의 값이 곧 스택의 길이, 즉 스택 내의 원소의 수를 의미한다는 것을 알 수 있습니다.

 

 

 

 

 

스택 직접 구현해보기

push 함수는 스택에 x를 추가하는 함수이고, pop 함수는 스택의 꼭대기에 위치한 원소를 제거하는 함수이고, top 함수는 스택의 꼭대기에 위치한 원소의 값을 확인하는 함수입니다. 

시도하기

내가 구현한 부분

#include <iostream>
using namespace std;

const int MX = 10000005;
int dat[MX]; // 배열 인덱스는 0부터 채워진다.
int pos = 0; // pos는 다음에 추가할 원소의 인덱스

void push(int x) {
	dat[pos] = x;
	pos++; // 길이 늘려주기
}

void pop() { // 꺼내는 거
	// 꺼내는 것을 어떻게 표현해요?
	// 어차피 쓰레기값이든 뭐든 채워지는데
	// 나중에 넣게 됨
	// pos는 변함
	pos--;
}

int top() { // 확인하는 거
	int a = dat[pos - 1]; // 제일 끝에 있는 원소는
	return a;
}

void test() {
	push(13);
	push(21);
	push(30);
	push(12);
	pop();
	// index는 0부터 pos-1
	for (int i = 0; i < pos; i++) {
		cout << dat[i] << '\n'; // 13 21 30이 나오는지 테스트
	}
	// cout test
}

int main(void) {
	test();
}

pop해서 데이터를 erase 하는 부분이 고민이었다.

바킹독님도 나처럼 굳이 pop해야 될 부분의 값을 pop 할 때, 지우지는 않았다.

"그냥 pos를 1 줄이면 됩니다. 이 때 dat의 3번지에 있는 값 12 자체는 굳이 변경하지 않아도 괜찮습니다. 왜냐하면 나중에 push가 발생하면 어차피 그 때 들어올 값으로 덮어써질거라 더 이상 저 12라는 값은 아무 의미가 없고, 이런 상황이면 굳이 값을 변경하는 추가적인 연산을 하는게 시간낭비니 내버려두면 될 것입니다. 이를 코드로 표현하면 pos--; "

 

바킹독님 깃허브 링크를 참고해서 보면 큰 차이가 없음을 알 수 있다.

 

STL 스택을 쓴 경우

STL stack에서는 주로 push, pop, top, empty, size 멤버 함수를 쓰게 될 것

 

그리고 18번째 줄을 보면 알겠지만 스택이 비어있는데 top을 호출하면 런타임 에러가 발생합니다. 스택이 비어있는데 pop을 호출해도 마찬가지입니다. 그렇기 때문에 스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 해야합니다.

 

BOJ 풀기

STL 사용 풀이

 

문자열 비교는 "push"를 이용해서 push를 포함하는지 확인해준다! (굳이 split 이런 거 안 해도 된다.)

그러고 cin을 통해서 숫자를 받아준다.

 

직접 쓴 경우

#include <iostream>
using namespace std;

const int MX = 10000005;
int dat[MX];
int pos;

void push(int val) {
	dat[pos++] = val;
}

void pop() {
	pos--;
}

int top() {
	return dat[pos - 1];
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	while(n--) { // n번 반복
		string c;
		cin >> c;
		if (c == "push") {
			int t;
			cin >> t;
			push(t);
		}
		else if (c == "pop") {
			if (pos == 0)
				cout << -1 << '\n';
			else {
				cout << top() << '\n';
				pop();
			}
		}
		else if (c == "size")
			cout << pos << '\n';
		else if (c == "empty")
			cout << (int)(pos == 0) << '\n';
		else{ // top
			if (pos == 0)
				cout << -1 << '\n';
		else cout << top() <<'\n';
		}
	}
}

 

출처) https://blog.encrypted.gg/933

[실전 알고리즘] 0x05강 - 스택