728x90
Stack
스텍은 데이터를 후입선출(FIFO) 방식으로 관리하는 자료구조 로, 데이터를 저장하고 검색작업을 수행하는데 사용된다.
스텍의 특징
- 삽입과 삭제가 제한적이다.
- 한쪽끝에서만 삽입 삭제가 가능한데, 이것은FIFO구조로 관리하기 때문이다. 스택은 맨위에 추가되며, 가장 위의 요소만을 제거할 수 있다.
- 접근이 제한적이다.
- 스택은 가장 위에있는 요소에만 접근, 추가, 삭제 할 수 있다.
스텍의 장점
- 구조가 직관적이고 단순하다.
- 메모리를 효율적으로 활용할 수 있다.
- 재귀 알고리즘을 구현하는데 사용할 수 있다.
- 재귀호출 상태를 스택에 저장하여, 알고리즘의 진행과 복귀를 관리할 수 있다.
스텍의 단점
- 고정된 크기를 가지고 있어, 데이터의 개수가 스텍의 크기를 초과하면, 오버플로우가 발생한다.
- 중간요소에 접근하기가 힘들다.
Stack의 알고리즘 구현,
#include <iostream>
#include <memory.h>
#include <cassert>
using namespace std;
#define MAXSTACKCOUNT 20
template<typename T>
class Stack
{
private:
int top = -1;
T values[MAXSTACKCOUNT];
public:
Stack()
{
memset(values, 0, sizeof(T) * MAXSTACKCOUNT);
// 메모리 초기화 해주는 함수.
// 메모리 시작 주소 기입,
// 메모리 사이즈 기입한다.
// 0으로 모든 메모리를 초기화해주는 함수,
}
void Push(T value)
{
assert(top + 1 < MAXSTACKCOUNT);
// Stack이 가득차지 않았다면,
values[++top] = value; // values라는 배열에 1씩 더해주면서 올려준다.
}
T Pop()
{
assert(Empty() == false);
T val = values[top--];
return val; // 맨 위의 요소를 제거하고 그 요소를 반환해준다.
}
T Front()
{
return values[top]; // 맨 위의 값을 반환해준다.
}
T back()
{
assert(top > -1);
return values[0]; // 배열의 가장 뒤의 값을 반환한다.
// 배열이 비어있는지 또한 확인한다.
}
bool Empty()
{ // 배열이 비어있는지, top이 0보다 작으면 비어있다는 의미 이기 때문에,
return top < 0 ? true : false;
}
};
int main()
{
Stack<int> stack;
stack.Push(10);
stack.Push(20);
stack.Push(30);
stack.Pop();
stack.Push(40);
stack.Push(50);
cout << stack.back() << endl << endl;
cout << stack.Front() << endl << endl;
while (stack.Empty() == false)
cout << stack.Pop() << endl;
return 0;
}
Linkedlist_Stack
일반적으로, 스텍은 데이터의 저장공간이 한정적이다.
그러나, 리스트배열 방식으로 스텍을 관리하여, 저장공간을 유동적으로 바꾸어 줄 수 있다.
#include <iostream>
using namespace std;
struct Node
{
int Data;
Node* NextNode;
};
class Stack
{
private:
Node* list = NULL; // 스텍의 배열을 가리킴
Node* top = NULL; // 스텍의 제일위 요소 가리키게 만듬
public:
Stack();
~Stack();
void Push(Node* node);
Node* Pop();
int Size();
bool IsEmpty();
static Node* CreateNode(int data);
static void DestoryNode(Node** node);
};
Stack::Stack()
{}
Stack::~Stack()
{
// pop을 계속 호출함으로써 모든 스텍을 제거하도록 만든다.
while (IsEmpty() == false)
{
Node* node = Pop();
DestoryNode(&node);
}
list = NULL;
top = NULL;
}
void Stack::Push(Node * node)
{
if (list != NULL) // 현재 스텍이 비어있지 않다면,
{
Node* tail = list; // 스텍의 끝 까지 이동할 포인터.
// 마지막에서 끝부분에 값을 넣는다.
while (tail->NextNode != NULL)
tail = tail->NextNode;
tail->NextNode = node;
// tail 의 마지막 NULL에 node를 연결한다.
}
else // 스텍이 비어있다면
{
list = node;
}
}
Node* Stack::Pop()
{
// 데이터를 반환하고 날리면 된다.
if (list == top) // 배열이 한개뿐 이라면,
{
list = NULL;
top = NULL;
}
else
{
Node* tail = list;
while (tail != NULL && tail->NextNode != top)
{
tail = tail->NextNode;
}
top = tail;
// 맨위 노드와의 연결을 분리하고,
// 맨 위 노드를 반환한다.
tail->NextNode = NULL;
}
return top;
}
int Stack::Size()
{
int count = 0;
Node* node = list;
while (node != NULL)
{
node = node->NextNode;
count++;
}
return count;
}
bool Stack::IsEmpty()
{
return list == NULL;
}
Node* Stack::CreateNode(int data)
{
Node* node = new Node();
node->Data = data;
node->NextNode = NULL;
// 만들어졌을 때는 다음 노드가 없음으로 NULL로 처리
return node;
}
void Stack::DestoryNode(Node** node)
{
delete* node;
*node = NULL;
// 데이터를 해제하기 위해서 이중포인터로 가져와야 한다.
}
int main()
{
Stack stack;
stack.Push(Stack::CreateNode(10));
stack.Push(Stack::CreateNode(20));
stack.Push(Stack::CreateNode(30));
stack.Push(Stack::CreateNode(40));
int count = stack.Size();
cout << "Size : " << count << endl;
for (int i = 0; i < count; i++)
{
if (stack.IsEmpty() == true)
break;
Node* temp = stack.Pop();
cout << "pop : " << temp->Data << endl;
Stack::DestoryNode(&temp);
}
return 0;
}
728x90
'서울게임아카데미 교육과정 6개월 C++ ~ DirectX2D' 카테고리의 다른 글
56일차. DirectX11_2D시작, DirectX11_2D[Graphics] (0) | 2023.07.13 |
---|---|
55일차. Queue_by_linkedlist, Tree (0) | 2023.07.10 |
53일차. Breadth_First_Search (0) | 2023.07.05 |
52일차. BruteForce, Depth_first_search (0) | 2023.07.04 |
51일차. 충돌처리, 자료구조 - Sort (0) | 2023.06.30 |