• 삽입과 제거를 LIFO 에 따라서 한다. 즉 마지막에 넣은 object를 먼저 제거한다. Last Input First Out에 따른다는 것.
• JAVA interface definition는 Java에 내장된 java.util.Stack과 조금 다르다.

public interfaceStack
{	publicint size()
	public boolean isEmpty()
	public Object top() throws EmptyStackException
	public void push (Object o) throws FullStackException
	public Object pop()
		throws EmptyStackException
}

• 당연한 말이지만, 이 interface를 implement해서 Stack class를 만들어야 한다.
• Exceptions : stack이 empty 한 상태에서 pop() or top() 연산을 하면 EmtpyStackException을 throw하도록 한다.

Array- based Stack

• 배열을 사용해 stack을 구현하는 simple한 방법이다.
• 변수 t를 사용해서, top element의 index를 쫓아가야 한다.
• 문제는 이런 배열 기반의 Stack은 "full"이 될 수 있다는 것이다. --> push()연산은 FullStackException을 throw할 수 있다.

  성능 :
  - space : O(n)
  - 각 연산 : O(1)
  - 단점.
  1. size limit을 갖는다. stack의 max size가 predefined되어있으며 바뀔 수 없다.
  2. array의 특징으로, 메모리 낭비를 하게 된다.

• Growable array로 구현하는 Stack이 필요하다.

💥Stack이 사용되는 곳‼

• Web browser에서 방문 page history (최근 방문한 순서대로 위에서부터 쌓여있다)
• text 편집기에서 Undo 시퀀스 ( 최근 do 한 것부터 Undo를 할 수 있다) (do하기 이전의 state를 그런식으로 쌓아놓은것)
• JVM 에서 "chain of methods" <JVM뿐만아님>
  • method가 호출되면, JVM은 해당 method를 containing하고 있는 frame을 push한다.< Frame에는 간단히 말하면, local변수, PC정보(Program Counter 변수(Linux에서 배울 때는 register에 저장되는 값으로 본 적 있다)(현재 실행중인 statement 를 쫓는 값) 을 담고 있다>
  • method가 return하면, active frame은 stack에서 popped되고 컨트롤은 stack의 가장 top에 있는 method frame에게로 passed된다.
• Parentheses(괄호) Matching. (예를들어서 "여는 괄호"가 "닫는 괄호"와 적절하게 매칭이 되었는지 검사할 수 있다.

백준 10828번

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

출력
2
2
0
2
1
-1
0
1
-1
0
3

• 그냥 array-based의 stack으로 대충 구현했다.
• 그런데 명령문을 입력받아서 함수를 호출하는 것에서 막혔다.
  if else문 or switch문으로 하려다가 for문을 쓰고 싶어서 함수포인터를 사용했다.

#include <iostream>
#include <string>

using namespace std; 

class my_stack {
private:	
	int v[10001]; 
	int f_t; 
	int f_size;
	int (my_stack::*p_arr[4])(void) = { &my_stack::pop,&my_stack::top,&my_stack::size,&my_stack::empty };
public:
	my_stack() {
		f_t = -1; 
	}
	int push(int a);
	int pop();
	int size();
	int empty();
	int top();
	int execute(int n);
};

int N;
my_stack m_stack;
string func_arr[4] = { std::string("pop"),std::string("top"),std::string("size"),std::string("empty") };


int my_stack::push(int a)
{
	//std::cout << "push()\n";
	v[f_size] = a;
	f_t++;
	f_size++;
	return 0;
}

int my_stack::pop()
{
	//std::cout << "pop()\n";

	if (empty()) return -1;
	else {
		int temp = v[f_t];
		f_t--;
		f_size--;
		return temp;
	}
}

int my_stack::size()
{
	return f_size;
}

int my_stack::empty()
{
	return (f_t == -1); 
}

int my_stack::top()
{
	if (empty()) return -1;
	else return v[f_size-1];
}

int my_stack::execute(int n)
{
	int result =(this->*p_arr[n])();
	return result;
}


int main()
{
	char c; 
	std::cin >> N;
	cin.get(c);
	
	std::string func;
	std::string deli = " ";
	for (int i = 0; i < N; i++)
	{
		std::getline(std::cin,func);
		//std::cout << "func : " + func << std::endl;
		int pos = func.find(deli);
		int result;
		if (pos == -1) {
			
			for (int i = 0; i < 4; i++) {
				if (func_arr[i] == func) { //  std에 string 인자들에 대한  == operator가 오버라이딩 되어있다. 
					int check = m_stack.execute(i);
					cout <<check << endl;
					break;
				}
				
			}
		}
		else {
			
			string function = func.substr(0, pos);
			string data = func.substr(pos+1, func.length());
			m_stack.push(stoi(data));
		}
	}
	
	
}

입력 받기 (std::string)

여러 줄 읽기

쉽게는 getline() 함수 사용 : '\n' 이나 /end of file이나 /사용자가 지정한 delimeter에/ 도달할 때 까지 read한다.

• std::string 에 대해서도 overriding 되어 있다.

c++에서 cin 이후 getline호출

int N;
string temp;
cin >> N ; 
for(int i=0;i<3;i++){
	std::getline(std::cin, temp); 
} 
	

입력 : 3
push 5
pop
push
첫 번째 getline : "\n" 을 입력받는다.
두 번째 getline : push 5
세 번째 getline : pop

💥이렇게 되는 이유

• 3은 변수 N에 들어가지만 newline character는 input stream(istream.즉 cin객체)에 남아있게 된다.
• 이 상태에서 다시 한 번 cin을 쓴다면 이 newline은 그저 whitespace로 여겨져서 무시되지만,
• 이 상태에서 getline()을 쓰게 된다면 이 getline()의 호출에서는 newline을 읽게 되는 것이다.

🔑 해결방법

• 해결방법 0 : getline() 전에 std::ws(cin); 을해서 whitespace를 skip하기. : 이는 '\n' 에 이어 오는 whitespace들도 skip을 하게 된다는 것에 유의해야 한다.
• 해결방법 1 : cin>>N; 이후 getline()전에 cin.getc(char c); 를 호출하기
• 해결방법 2 : getline을 사용하지 않고 cin >> string ; 하기
  - 해결방법 2에서 "push"의 경우, data를 받기 위한 cin>> int data; 를 한 번 더 해야한다.

member function pointer 을 array에 담아서 사용하기

• 이 문제를 풀면서, 그냥 for문을 사용하고 싶었다. 그래서 함수 포인터를 사용해 보고 싶었다.
• C에서 함수 포인터는 여러 번 사용해 봤는데, C++에서 member function인 함수를 함수포인터로 사용하려니 당혹스러웠다.
• 이 경우 아래와 같이 하면 된다.

my_stack m_stack;
int (my_stack::*p)(void) = &my_stack::pop; 
int data = (m_stack.*p)();

• member function은 호출 될 때, "이 member function이 속한 객체의 주소"가 자동으로 member function의 인자로 넘어가 instance * this 로 사용되(보이지는 않지만)기에, 단순한 함수 포인터와 "선언 형식"도 다르다.
• 즉, 이 넘어가는 인자의 자료형을 결정하기 위해, 이 함수에 대한 함수포인터 선언 시, 해당 함수가 소속된 class의 이름을 scope연산자로 적어줘야 한다.

int (my_stack::*p)(void) = &mystack::pop; 

• 그런데 함수포인터 배열로 만들어서 사용하려니 또, 어떤식으로 선언하고 사용할지 당혹스러웠다.
  - 선언은 일반 , 함수 포인터 배열과 비슷하게 선언했다.

int (my_stack::*p_arr[4])(void) = 
		{ &my_stack::pop,&my_stack::top,
        &my_stack::size,&my_stack::empty };

• 사용은 위와 같이 하는 방법과
• class 외부에 함수포인터 배열을 선언하고 사용하는 방법이 있다.

class my_stack{
.....
}
int (my_stack::*p_arr[4])(void) = { &my_stack::pop,&my_stack::top,&my_stack::size,&my_stack::empty };
int main()
{
	my_stack m_stack;
	......
    int i=3;
    int check = (m_stack.*p_arr[i])();
    ..
}    

• 즉 사용 시에는

클래스 외부에 선언된 포인터 배열을 클래스 외부에서 사용시.
m_stack.*p_arr[i])();
클래스 내부에서 선언된 포인터 배열을 클래스 내부에서 사용시.
(this->*p_arr[n])();