자료 구조: 스택

스택은 데이터를 한쪽 끝에서만 삽입과 삭제가 일어나는 선형 자료구조이다. 순차적 할당에서, "top" 포인터는 스택의 꼭대기를 가리킨다. 삽입은 "top"을 증가시키고 새로운 값을 삽입하는 것을 포함하며, 삭제는 "top"을 감소시키고 값을 회수하는 것을 포함한다. 두 연산 모두 O(1)의 시간 복잡도를 가진다. 연결 할당에서, 꼭대기는 단순 연결 리스트의 첫 번째 노드이다. 삽입은 새로운 노드를 할당하고 값을 삽입하고, 이를 꼭대기에 연결하는 것을 포함한다. 삭제는 꼭대기의 값을 회수하고, 꼭대기를 다음 노드로 이동시키고, 삭제된 노드를 할당 해제하는 것을 포함한다. 다시 말해, 연산은 O(1)의 시간 복잡도를 가진다. 스택 연산, 즉 삽입과 삭제는 구조의 한쪽 끝에서 수행되므로, 연산은 효율적이고 상수 시간 복잡도를 보장한다.