스택(stack)

스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하다
top 의 위치에서만 원소를 삽입하기에 먼저 삽입한 원소는 밑에 쌓이고 나중에 삽입한 원소는 위에 쌓이는 구조이다.
마지막에 삽입(Last in) 한 원소는 맨 위에 쌓여있다가 가장 먼저 삭제(First-Out) 구조를 Last in First Out ,LIFO 구조라고한다.

위 사진은 이해를 위한 그림으로 먼저 삽입시킨 과자들은 밑에서 쌓이게 되고 후에 우리가 과자를 먹을때는 가장 top, 마지막에 들어간 과자를 먼저먹게되는구조가 stack과 유사하다고 할수있다.

스택의 연산

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

스택에서의 원소 삽입/삭제 과정

스택에서의 Insert과정을 보면 D를 삽입시 stack의 top 은 D가되게되고 마찬가지로 E를 넣으면 E가 탑이 되며 , 탑을 삭제할경우 D가 top이 되는것으로보아
스택의 top에서만 삽입및 삭제과정의 변화가 일어나고 그 외의 부분에는 변화가 없는것을 확인할수가있다 .

코드 구현

이제 스택에 대해 어느정도 다루어보았으니 코드로 구현을 해보도록 하겠다

배열을 통한 코드 구현

#include<iostream>
using namespace std;
#define SIZE 10
template <typename T>
class Stack
{
private:
	int top;
	T buffer[SIZE];

public:
	Stack()
	{
		for (int i = 0; i < SIZE; i++) //배열 초기화 및 top=-1
		{
			buffer[i] = NULL;
		}
		top = -1;
	}
	~Stack() // 배열이기에 동적해제할것이 없음 
	{
		
	}
	void Push(T  data) //원소 삽입 
	{
		if (IsFull())
		{
			cout << "Stack is Full" << '\n';
			return;
		}
		else
		{
			buffer[++top] = data;
		}
	}
	T Pop() //원소 top 삭제 
	{
		if (Empty())
		{
			cout << "Stack is Empty" << '\n';
			return 0;
		}
		else
		{
			return buffer[top--];
		}
	}
	bool Empty() //비어있는지 확인 
	{
		if (top <= -1)
		{
			return true;
		}
		else
		{
			return false;
		}
	} 
	bool IsFull()  //stack 이 가득찼는지 확인 
	{
		if (top >= SIZE - 1)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Top()
	{
		
		return buffer[top];
	}
	
};
int main()
{
	Stack <int> stack;

	for (int i = 1; i <= SIZE; i++)
	{
		stack.Push(i * 10);
	}

	while (stack.Empty() != true)
	{
		cout << "|" << stack.Top() << "|" << endl;
		stack.Pop();
	}
	
	return 0;
}

리스트를 이용한 구현

배열을 통해 stack 을구현하게 되면 쉽게 구현이 가능하지만
배열은 크기를 정해주어야하는 점이 있다.
이에 대한 문제를 해결하기위해 리스트를 통해 stack 을 구현해보았다.

#include<iostream>
using namespace std;

template <typename T>
class Stack
{
private:
	struct stackNode //stackNode 를 구조체 로 표현 
	{
		T data;
		stackNode* link;
	};
	stackNode* top; // top 노드 지정을위함 포인터 top
	int size; //stack 사이즈 계산 
public:
	Stack()
	{
		top = nullptr; //초기화
		size = 0; // 스택 안의 개수를 세기 위함 
	}
	void Push(T data) // 삽입 
	{
		stackNode* currentNode = new stackNode;
		currentNode->data = data;
		currentNode->link = top; //삽입노드를  삽입전 top의 위에 연결 
		top = currentNode; // 이제 top은 삽입노드 
		size++; //사이즈 늘려줌 
	}
	T pop() //top에서 원소 삭제하는 연산 
	{
		T data;
		stackNode* curretnNode = top;
		if (top == NULL) //스택이 공백일경우 
		{
			cout << "***Stack is Empty***\n";
		
		}
		else //stack 이 공백이 아닐경우
		{
			data = curretnNode->data;
			size--;
			top = curretnNode->link; //top위치 한칸을 낮춤
			delete curretnNode;
			return data;
		}
	}
	bool Empty()
	{
		if (top == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Top()
	{
		if (Empty())
		{
			cout << "***Stack is Empty***\n";
			
			
		}
		else
		{
			return top->data;
		}
	}
	int Size()
	{
		return size;
	}
	void Print() //모든 원소 출력 
	{
		stackNode* printNode = top;
		cout << "Stack[ ";
		while (printNode)
		{
			cout << printNode->data << " ";
			printNode = printNode->link;
		}
		cout << "]\n";
	}
	~Stack()
	{
		while (!Empty())
		{
			pop();
		}
		cout << "Release Stack" << '\n';
	}
};
int main()
{
	Stack<int> stack;
	for (int i = 0; i < 3; i++)
	{
		stack.Push(i + 1);
		stack.Print();
	}
	for (int i = 0; i < 2; i++)
	{
		cout << "stack top : "<<stack.Top() << '\n';
		stack.pop();
		cout << "stack 사이즈 : "<<stack.Size() << '\n';
	}
	

	return 0;
}

괄호 검사

stack 과 관련된 문제에 대표적인 문제로 괄호검사가 있다 .
괄호검사란 [],{} ,()의 괄호들이 문장내에서 짝이맞는지 확인하는 문제이다 .
구현 해놓은 리스트stack 에서 추가로 bool CheckBracket 함수를 만들어 코드를 구현해보았다.

#include<iostream>
using namespace std;

template <typename T>
class Stack
{
private:
	struct stackNode //stackNode 를 구조체 로 표현 
	{
		T data;
		stackNode* link;
	};
	stackNode* top; // top 노드 지정을위함 포인터 top
	int size; //stack 사이즈 계산 
public:
	Stack()
	{
		top = nullptr; //초기화
		size = 0; // 스택 안의 개수를 세기 위함 
	}
	void Push(T data) // 삽입 
	{
		stackNode* currentNode = new stackNode;
		currentNode->data = data;
		currentNode->link = top; //삽입노드를  삽입전 top의 위에 연결 
		top = currentNode; // 이제 top은 삽입노드 
		size++; //사이즈 늘려줌 
	}
	T pop() //top에서 원소 삭제하는 연산 
	{
		T data;
		stackNode* curretnNode = top;
		if (top == NULL) //스택이 공백일경우 
		{
			cout << "***Stack is Empty***\n";
		
		}
		else //stack 이 공백이 아닐경우
		{
			data = curretnNode->data;
			size--;
			top = curretnNode->link; //top위치 한칸을 낮춤
			delete curretnNode;
			return data;
		}
	}
	bool Empty()
	{
		if (top == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Top()
	{
		if (Empty())
		{
			cout << "***Stack is Empty***\n";
			
			
		}
		else
		{
			return top->data;
		}
	}
	int Size()
	{
		return size;
	}
	void Print() //모든 원소 출력 
	{
		stackNode* printNode = top;
		cout << "Stack[ ";
		while (printNode)
		{
			cout << printNode->data << " ";
			printNode = printNode->link;
		}
		cout << "]\n";
	}
	~Stack()
	{
		while (!Empty())
		{
			pop();
		}
		cout << "Release Stack" << '\n';
	}
};
bool CheckBracket(string content)
{
	Stack<char> stack; 
	for (int i = 0; i < content.length(); i++)
	{
		if (content[i] == '(' || content[i] == '{' || content[i] == '[')
		{
			stack.Push(content[i]);
		}
		if (content[i] == ')' || content[i] == '}' || content[i] == ']')
		{
			if (stack.Top() == '(' && content[i] == ')') //짝맞으면 pop 해주는 구간
			{
				stack.pop();
			}
			else if (stack.Top() == '{' && content[i] == '}')
			{
				stack.pop();
			}
			else if (stack.Top() == '[' && content[i] == ']')
			{
				stack.pop();
			}
			else
			{
				return false;
			}
		}
	}
	if (stack.Empty()) //stack 안에 괄호들이 짝이 다맞아 pop이 되었으면
	{
		return true;
	}
	else //안됬으면 
	{
		return false; 
	}
}
int main()
{
	
	string flag = "[{(stack flag)}]";
	if (CheckBracket(flag))
	{
		cout << flag << " : " << "true";
	}
	else
	{
		cout << flag << " : " << "false";
	}

	return 0;
}