상위문서 : 자료구조
필수참고문서 : 빅오표기법 , 연결리스트
목차
1. 개요
2. 설명
3. 구현
3.1. JAVA로 구현
3.2. C#으로 구현
3.2. C#으로 구현
1.개요
스택은 데이터를 쌓는 구조의 후입선출(나중에 들어온 것이 먼저 나간다) 혹은 선입후출(먼저 들어온 것이 나중에 나간다.) 자료구조이다.
스택은 다음과 같은 ADT를 가지고 있다.
스택은 다음과 같은 ADT를 가지고 있다.
- 스택 생성
- Push
- pop
- peek or Top
2.설명
스택은 무언가를 담아 놓는 상자를 생각하면 된다. 상자에 책을 차곡차곡 쌓으면 맨 나중에 넣은 책을 나중에 꺼낼때 첫번째로 꺼내게 된다. 스택에는 여러 종류가 있는데 아래서부터 데이터를 쌓는 Ascending stack과 위에서부터 데이터를 쌓는 Descending stack이 있다.
3. 구현
스택의 구현은 크게 두가지로 구현할 수 있다. 배열로 구현하는 것과 단일연결리스트로 구현하는 것이다. 여기서 중요한것은 연결리스트로 구현할 때인데 연결리스트의 특성상 head부분에도 새로운 노드를 붙힐 수 있고 tail에도 붙힐 수 있다. 이 때 새로운 노드의 접합은 둘다 O(1)의 시간복잡도이지만 tail을 만약 새노드를 넣거나 빼는 곳으로 만들면 peek이나 pop을 할 때 head부터 tail까지 가야하는 참사가 생기므로 Top을 구현하기 위해서 head와 tail중 어디 부분을 Top으로 할지 정해야한다. 이 때 무조건 head쪽으로 Top을 구현해야하는데
