2. Stack

스택은 데이터를 쌓아올리는 식의 자료구조이다.

사진 출처- https://www.geeksforgeeks.org/stack-data-structure/

Stack ADT의 기능을 표현하면 다음과 같다.

• push(데이터): 스택에 데이터를 삽입한다.
• pop(): 가장 마지막에 삽입한 데이터를 삭제한다.
• top(): 가장 마지막에 삽입된 데이터를 리턴한다.
• size(): 스택의 크기(담긴 데이터 수)를 리턴한다.
• empty(): 스택이 비었는지 안비었는지 판단한다.

top과 pop 함수에서는 예외 처리를 항상 해주어야한다.
단, 배열로 구현시에는 push시에도 예외처리를 해준다.

Built in 배열로 구현한 Stack

#include <iostream>
using namespace std;

class Stack {
private:
	int* arr;
	int top;
	int max_size;

public:
	Stack(int arraysize):max_size(arraysize){
		top = -1;
		arr = new int[max_size];
	}

	~Stack() {
		delete[] arr; // 할당받은 메모리 해제
	}

	int size() {
		return top+1;
	}
	
	bool empty() {
		return (top == -1);
	}
	int Top() {
		if (empty()) return -1; //예외 처리
		return arr[top];
	}
	void push(int data) {
		if (size() == max_size) {
			cout << "exception" << endl; //예외 처리
			return;
		}
		top = top + 1;
		arr[top] = data;
	}
	int pop() {
		if (empty()) return -1; //예외 처리
		return arr[top--];
	}

};
int main() {
	Stack st(10);
	st.push(10);
	st.push(5);
	cout << st.Top() << endl;
	cout << st.size() << endl;
	st.push(1000);
	cout << st.Top() << endl;
	cout << st.pop() << endl;
	cout << st.Top() << endl;
	
}

---

Linked List로 구현한 Stack

#include <iostream>
using namespace std;

class Node {
private:
	int data;
	Node* next;
public:
	Node(int n):data(n) {
		next = nullptr;
	}

	friend class Stack;
};

class Stack {
private:
	Node* top;
	int size;
	
public:
	Stack(){
		top = nullptr;
		size = 0;
	}

	bool empty() {
		return (size == 0);
	}

	int Size() {
		return size;
	}

	int Top() {
		if (empty()) return -1; //예외 처리
		return top->data;
	}

	void push(int d) {
		Node* newnode = new Node(d);
		if (empty()) {
			top = newnode;
		}
		else {
			newnode->next = top;
			top = newnode;
		}
		size++;
	}

	int pop() {
		if (empty()) return - 1; //예외 처리
		Node* old = top;
		top = top->next;
		int popped_data = old->data;
		size--;
		delete old;
		return popped_data;
	}

};

int main() {
	Stack st;
	st.push(10);
	st.push(20);
	cout << st.Top() << endl;
	st.push(1000);
	cout << st.Size() << endl;
	cout << st.pop() << endl;
	cout << st.Size() << endl;
}

위 그림 같은 형태로 구현된거라고 생각하면 된다. 새로운 값이 삽입될 때, 기존에 들어있던 노드의 앞에 새 노드가 들어오고, 기존 노드를 가리킨다고 생각하면 된다.