54일차. Stack, Linkedlist_Stack

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;
}