개요
스택 알고리즘 풀이 하는 김에 좀 더 공부해봤다.
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
개념
불연속적인 메모리로 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 처럼)
롤에서 상점에서 구매했던 것이나 팔았던 행위를 되돌릴 수 있는 것처럼!
또 다른 이용은 아직 데이터를 뒤집을때 편할듯 하다.
스택 프레임이란 개념도 있는데
함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위하여 생성되는 공간이라 한다.
그렇기에 함수 호출시에 생성되고 함수가 종료되면서 소멸한다.
이 공간에는 함수와 관계되는 지역 변수가 저장된다고 한다.
암튼 그렇다 ㅋㅋ
'코딩 테스트 > 자료구조' 카테고리의 다른 글
| 힙 [Heap] (0) | 2022.07.29 |
|---|---|
| Linked List (0) | 2022.01.26 |
| Vector (0) | 2022.01.25 |
