스택 C++

 처음 들어간 데이터가 가장 마지막으로 출력되는 자료구조

---

 자료구조를 따지면 가장 먼저 나오는 구조라고 불러도 이상하지 않을만큼 익숙한 자료구조이다.

 

스택

 Last In First Out이란 단어로 설명이 가능하겠다. 스택은 두 개의 필수 명령이 있다.

• push
• pop

 입력을 할 때[# 스택에 값을 넣을 때]는 push, 출력할 때[# 스택에서 값을 뺄 때]는 pop으로, 이 명령을 이용해 다음과 같은 작업을 수행한다고 가정하면

1. push 1
2. push 5
3. push 3
4. pop
5. push 5
6. push 7
7. pop

 스택은 다음과 같은 순서로 데이터를 관리한다.

진행방향 →

 

 

구현

 기본적으로 스택은 배열을 이용하며, 배열을 어떻게 이용하는가에 대한 방식을 설명한다고 볼 수 있다. 다음은 C++에서 스택을 구현한 클래스 코드이다.

# 코드

#include <iostream>
#include <iomanip>

class Stack {
	int* data;
	size_t capacity;
	size_t length;

public:
	void print() {
		using namespace std;
		cout << setw(7) << "stack: ";
		for (size_t i = 0; i < length; ++i) {
			cout << setw(3) << data[i];
		}
		cout << endl;
	}
	bool Push(int value) {
		using namespace std;
		cout << setw(7) <<  "push: " << setw(3) << value << endl;
		if (capacity == length) {
			capacity *= 2;
			int* temp = data;
			data = new int[capacity];
			for (size_t i = 0; i < length; ++i) {
				data[i] = temp[i];
			}
		}
		data[length++] = value;
		print();
		return true;
	}

	bool Pop(int* ref) {
		using namespace std;
		cout << setw(7) << "pop: ";
		if (length > 0) {
			*ref = data[--length];
			cout << setw(3) << *ref << endl;
			print();
			return true;
		}
		cout << "error" << endl;
		return false;
	}
public:
	Stack() : Stack{10} {};
	Stack(size_t capacity) : data{}, capacity{capacity}, length{}{
		if (capacity > 0) {
			data = new int[capacity] {};
		}
		else {
			throw "SizeIsZero";
		}
	}

};

int main() {
	Stack st{10};
	int temp;
	st.Push(1);
	st.Push(5);
	st.Push(3);

	st.Pop(&temp);
	st.Push(5);
	st.Push(7);
	st.Pop(&temp);

	return 0;
}

 

 push와 pop 메서드의 반환 자료형 및 파라미터의 경우 구현한 사람에 따라 다르므로 다른 사람의 코드를 사용할 때는 매뉴얼을 확인해야한다.[# 여느 코드를 사용하던 이는 마찬가지지만..] 위 코드의 경우에는 반환 자료형을 bool타입으로 두어서 해당 메서드의 성공 여부를 반환한다.

 

용례

 수식 계산에 앞서 괄호가 올바르게 작성되었는가에 대한 검사를 진행할 때, 후위 표기로 계산을 하는 프로그램을 만들 때 사용하곤 한다. 또한 웹브라우저의 방문기록이나 문자열을 반전시킬 때 사용하기도 한다.

 

# index