스택 [Stack]

개요

스택 알고리즘 풀이 하는 김에 좀 더 공부해봤다.

10828번: 스택

 

---

개념

불연속적인 메모리로 Last in first out 을 가진다.

[Top of pointer을 가지고있음]

 

---

구현

array형식으로도 구현가능하고 linked list로도 구현 가능하여 각 장,단점을 생각해 보았다.

---

array로 구현시

● 추가 메모리가 요구 되지 않는다.

 

● 먼저 array의 강력한 장점인 인덱스로 값을 찾는것이 stack에서는 그렇게 필요하지 않다고 느꼈다

어차피 맨 위의 데이터만 사용하려고 하는 것이기 때문이다.

 

● 크기에 대한 번거로운 과정이 있을 것이다(새로 할당받고 복사하고 원 메모리 반환)

그에 딸려오는 단편화 문제

 

Linked list로 구현시

● 임의의 위치에 데이터를 추가,삭제 하는 기능이 없기 때문에 이러한 장점을 살릴 수 없다.

 

● 크기에 제약이 없다!

 

● 옆의 노드의 주소를 저장 할 공간이 추가 요구 됨

 

● 맨 위의 데이터만을 참고 한다는 스택의 특징이 랜덤 액세스가 불가능한 연결리스트의 단점을 커버 해줌

---

나는 무난한 배열로 구현을 해보겠다.

---

생성 & 소멸 & 멤버 변수

#include <iostream>
using namespace std;
#define INIT_STACK_SIZE 10

template<typename T>
class Stack
{
public:

	Stack()
	{
		data = new T[INIT_STACK_SIZE];
		capacity = INIT_STACK_SIZE;
		topIndex = -1;
	}
	~Stack()
	{
		delete[] data;
		data = nullptr;
	}
    
    
/************생략************/
                                        

private:
	//스택에 넣을 데이터를 담을 포인터 형
	T * data;
	//맨 위의 인덱스
	int topIndex;
	//스택의 총 메모리 양
	int capacity;
};

---

데이터 삽입 (Push)

	void Push(T input)
	{
		++topIndex;
		if (capacity <= topIndex)
		{
			T * temp = new T[capacity * 2];
			memcpy(temp, data, sizeof(int) * capacity);
			delete[] data;
			data = temp;
			capacity *= 2;
		}
		data[topIndex] = input;
	}

배열이기 때문에 크기에 대한 처리를 따로 해주었다.

---

데이터 삭제 (Pop)

	void Pop()
	{
		if (IsEmpty() == true) return;
		--topIndex;
	}

---

맨 위의 데이터 꺼내기 (Top)

	T Top()
	{
		if (IsEmpty() == true) return -1;
		return data[topIndex];
	}

여기서 예외설정을 안해서 알고리즘에서 틀렸었다 😂

---

결과

 

---

사용처

 

맨 위의 데이터를 다룬다는 것에 대하여 게임의 네비게이션에서 사용 할 수 있을거 같다.

 

이는 여태 시도하는 경로를 스택에 쌓아둠과 동시에 틀릴 경우 맨위부터 다시 돌아가 다른 경로를 탐색함에 있어서

LIFO인 스택과 같아 잘 맞는다.

[나중에 깊이 우선 탐색이라는 알고리즘이 이와 같다고한다?]

 

또한 상점에서 거래를 이전으로 돌리는 기능을 구현 할 수 있을 것 같다.(ctrl + z 처럼)

롤에서 상점에서 구매했던 것이나 팔았던 행위를 되돌릴 수 있는 것처럼!

 

또 다른 이용은 아직 데이터를 뒤집을때 편할듯 하다.

 

스택 프레임이란 개념도 있는데

함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위하여 생성되는 공간이라 한다.

그렇기에 함수 호출시에 생성되고 함수가 종료되면서 소멸한다.

이 공간에는 함수와 관계되는 지역 변수가 저장된다고 한다.

 

암튼 그렇다 ㅋㅋ