스택

스택

---

스택은 데이터를 FILO(First In Last Out) 원칙에 의해 삽입하거나 삭제하는 자료구조를 말합니다.

스택에 데이터가 삽입 되는 것을 push라 부르고, 삭제하는 것을 pop이라 부릅니다.

 

-push(value): 스택의 가장 위 빈 곳에 데이터를 삽입합니다.

-pop(): 스택의 가장 위에 저장 된 값을 리턴한다. 단, 스택이 비어있다면 스택이 비어있다는 메세지를 출력합니다.

 

또한 스택을 더욱 편리하게 관리하기 위해 기타 연산도 지원할 수 있어야 합니다.

 

-size(): 스택에 저장 된 데이터의 개수를 리턴합니다.

-isEmpty(): 스택이 비어있다면 true, 아니면 false를 리턴합니다.

-isFull(): 스택이 꽉 차있다면 true, 아니면 false를 리턴합니다.

-top(): 스택의 가장 위에 저장 된 값을 삭제하지 않고 리턴합니다. 단, 스택이 비어있다면 스택이 비어있다는 메세지를 출력합니다.

 

 

구현

---

#define S 1024
int top = -1;

int stack[S];

//현재 배열의 사이즈 리턴
int size() {
	return top + 1;
}

//배열이 비었는지 확인
bool isEmpty() {
	if (top < 0)
		return true;
	else
		return false;
}

//배열이 꽉 찼는지 확인
bool isFull() {
	if (top >= S)
		return true;
	else
		return false;
}

//push
void push(int v) {
	if (isFull()) 
		cout << "스택이 꽉 차있습니다.\n";
	
	else
		stack[++top] = v;
}

//pop
int pop() {
	if (isEmpty()) {
		cout << "스택에 값이 없습니다.\n";
		return -1;
	}
	else
		return stack[top--];
}

//맨 위에 있는 값 리턴
int Top() {
	if (isEmpty()) {
		cout << "스택에 값이 없습니다.\n";
		return -1;
	}
	else
		return stack[top];
}

int main(){
	int a[] = { 1,2,3,4,5,6 };
	int b[6];
	int sum;

	//스택에 a[]에 저장 된 값 push
	for (int i = 0; i < 6; i++)
		push(a[i]);

	//b[]에 스택에 저장 된 값 pop
	for (int i = 0; i < 6; i++)
		b[i] = pop();

	for (int i = 0; i < 6; i++) {
		cout << "a[" << i << "]: " << a[i] << "\n";
		cout << "b[" << i << "]: " << b[i] << "\n";
		cout << "\n";
	}
	cout << "Top:" << Top();

}

결과

 

스택 stack[S]을 구현하여 a[]에 저장 된 값을 stack[S]에 push하고 그 값들을 b[]에 pop하는 코드입니다.

 

그림으로 정리하면

Operation	stack	output
push(1)	(1)	-
push(2)	(1, 2)	-
push(3)	(1, 2, 3)	-
push(4)	(1, 2, 3, 4)	-
push(5)	(1, 2, 3, 4, 5)	-
push(6)	(1, 2, 3, 4, 5, 6)	-
pop()	(1, 2, 3, 4, 5)	6
pop()	(1, 2, 3, 4)	5
pop()	(1, 2, 3)	4
pop()	(1, 2)	3
pop()	(1)	2
pop()	(-)	1

와 같은 동작을 하게 됩니다.