Algorithm2 Stack(스택) (2) 이번 포스팅에서는 저번 포스팅에 이어서 Stack에 대한 소스코드 및 시간복잡도에 알아보고자 한다. 이를 배열과 연결리스트일 때로 나누어서 설명하겠다. (1) 배열 시간복잡도 : Stack이 배열로 구현된 경우 탐색이 없고, top의 위치에만 삽입과 삭제를 하기 때문에 top의 위치만 알고 있으면 되는데, top을 변수로 놓고 위치를 체크할 수 있으므로 top으로 바로 접근이 가능하다. 따라서, 삽입과 삭제의 시간복잡도만 따져주면 되므로 배열로 구현된 Stack의 시간복잡도는 O(1)이다. 삽입 : 삽입은 쉽다. top을 +1 시켜주면서 그 자리에 데이터를 삽입하면 된다. 삭제 : 원래 구현하려고 했던 것은 연결리스트처럼 실제로 데이터를 삭제하는 방향으로 하려고 했는데 C언어로 하려다보니 생각보다 배열의.. 2020. 9. 24. Stack(스택) (1) Stack은 사전적 의미는 "쌓다" 이다. 또한 무언가가 쌓여있으면 꺼낼 때 위에서부터 꺼내게 되는데 그게 딱 Stack에 대한 이야기이다. 그림으로 보면 이렇게 데이터가 들어올 때 밑에서부터 위로 차곡차곡 쌓이게 되고 (push), 나갈 때는 위에서부터 나가게 되는 (pop) 구조이다. 그래서, 이를 LIFO (Last In First Out)라고 부르고, 이 Stack은 배열이나 연결리스트 둘 다 구현이 가능하지만, 각각의 상황에 맞게 구현해주면 된다. (1) 배열로 구현 - 장점 : 구현이 쉽고, Stack의 최대 크기를 알고 있을 때 사용하기 좋다. - 단점 : Stack의 크기가 제한적이고, Stack 크기를 모두 사용하지 않으면 메모리 낭비가 발생한다. (2) 연결리스트로 구현 - 장점 : S.. 2020. 9. 24. 이전 1 다음
