Stack

Stack

• Stack이란?
  • LIFO: Last In First Out
  • top(top of pointer)를 활용하여 구현되며, stack이 비어있다면 top의 값은 -1로 되어있다
  • 후입 선출로 값을 뒤집어야 하는 상황에서 사용한다
  • 재귀 함수, 명령을 내렸다 취소(ctrl z, ctrl y), 함수나 클래스의 스택 프레임, 지역변수 등에서 사용할 수 있다

    

  • 스택프레임: 함수를 스택 영역에 차례대로 저장되는 함수의 호출 정보

    

  • 콜스택: 함수를 콜하면서 생긴 스택
  • Caller: 함수 A에서 생성된 스택프레임
  • Callee: 함수 B에서 생성된 스택프레임
  • 스택 프레임을 살펴보면 호출한 함수인 B의 return될 주소-> 파라미터 값 a, Jump뛸 주소 B순으로 Callee에 스택 프레임이 만들어지고, Jump뛸 주소를 꺼내 Jump를 뛴 뒤 a값을 꺼낸 뒤 b에 저장한 뒤 스택에 담는다
  • 그 후 c변수에 b값을 넣고 c역시 스택에 담고, return을 만나 복사생성자에 의해 c 값을 복사해 따로 들고있는다
  • }를 만나 c,b순으로 스택에서 꺼내고, return될 주소를 꺼내면서 복사된 c값을 담아 넘겨주면 B(a)가 c의 값으로 대채될 수 있는 것이다
• 구현

#pragma once
#include <memory.h>
#include <assert.h>

#define MAX_STACK_COUNT 20

template<typename T>
class Stack
{
public:
	Stack()
	{
		memset(values, 0, sizeof(T) * MAX_STACK_COUNT);
	}

	void Push(T value)
	{
		assert(top + 1 < MAX_STACK_COUNT);

		values[++top] = value;
	}

	T Pop()
	{
		bool b = Empty();
		assert(b == false);//정의로 가보면 assert 가 NDEBUG 상황(Release모드)일땐 void(0)으로 assert를 채크하지 않는다
		if (b == true)
			return -1;

		T val = values[top--];

		return val;
	}

	T Front()
	{
		return values[top];
	}

	T Back()
	{
		assert(top > -1);
		if (top <= -1)
			return -1;

		return values[0];
	}

	bool Empty()
	{
		return top < 0 ? true : false;
	}
private:
	int top = -1;

	T values[MAX_STACK_COUNT];
};

#include <iostream>
#include "Stack.h"

int main()
{
	Stack<int> stack{};

	stack.Push(10);
	stack.Push(20);
	stack.Push(30);

	stack.Pop();
	stack.Push(40);
	stack.Push(50);

	while (stack.Empty() == false)
		printf("%d\n", stack.Pop());
	return 0;
}