1. 스택의 개념
스택이란 후입선출(LIFO - List In First Out) 형태의 자료구조이다. 스택의 원리는 접시를 쌓아올리는 것과 같다. 접시를 순서대로 쌓아올리게 되면 가장 마지막에 쌓은 접시가 접시 더미의 가장 위에 위치하게 된다. 따라서 접시더미에서 접시를 하나 집어들면, 맨 마지막에 쌓은 접시를 집어들게 된다. 이처럼 후입선출의 형태로 만든 자료구조를 스택이라고 한다.
2. 스택의 구현
스택을 구현하는 방법은 많지만, 이 글에서는 연결 리스트로 스택을 만드는 방법만을 다룬다. 스택을 구성하는 연결 리스트의 노드 구조체는 두 개의 멤버변수를 가진다. 하나는 노드의 자료를 저장 할 변수이고, 하나는 자신보다 먼저 저장된 노드를 가리키는 링크이다. 가장 처음 저장된 노드는 자신보다 먼저 저장된 노드가 없으므로, 링크가 NULL이다.
3. 스택의 연산
1) 삽입(PUSH)
스택에서 삽입은 항상 마지막에서 일어난다. 삽입할 노드의 링크를 가장 마지막에 삽입된 노드로 설정해주기만 하면 된다.
2) 삭제(POP)
스택의 삭제는 항상 마지막에서 일어난다. 맨 마지막 노드를 삭제해주기만 하면 된다.