자료구조 (2) 썸네일형 리스트형 [자료구조] Stack과 Queue 오늘은 선형 자료구조인 Stack과 Queue에 대해 알아보자 Stack 이란? 입력과 출력이 한 곳으로만 이루어지는 자료구조의 형태이다. LIFO정책을 따르고 있다.(Last In First Out) 따라서 나중에 들어온 것이 먼저 나간다. 뷔페의 접시가 쌓여있는 것을 생각하면 쉽다!! 그렇다면 Stack은 언제 사용될까? 1. 함수의 콜스택에 사용된다. 2. 문자열을 역순 출력할때에도 하나하나씩 넣고 빼면 역순으로 출력된다. 3. 후위 표기법을 연산할때 ex) 234*+ = 14 5. 브라우저 방문기록 6. 실행 취소(undo) Stack은 배열과 달리 index로 접근할 수 없다. 또한 삽입과 삭제는 O(1)의 시간 복잡도 이다.(값을 넣고 빼기만 하면 되므로) 하지만 탐색시에는 O(n)이 걸린다... [자료구조] Array와 List CS스터디를 시작하면서 한동안 못썼던 블로그를 자주 써볼려고 합니다!! 예전 개발자들이 개발을 시작하면서 데이터를 다룰때 하나의 데이터만 다루는 것은 아니겠죠? 여러가지 데이터가 모인 집합을 형성하게 되는데 먼저 Array라는 녀석부터 살펴봅시다. Array란? 순차적으로 데이터를 저장하는 형태로 물리적주소도 순차적으로 저장된다.(크기를 미리 지정해줘야 한다.) index라는 것이 존재해 빠르게 값을 찾아낼때 유용하다.(원하는 데이터 한번에 접근가능O(1)) 하지만 삽입과 삭제에는 취약하다. (해당 위치에 접근하고O(1), shift O(n)해주는 작업까지 걸려 O(n)이 걸린다.) 예를 들어 중간녀석을 삭제하려면 배열의 연속성이 깨져 이후 뒤에것들을 모두 앞으로 땡겨줘야 한다. 그렇다면 어떻게 저런 시.. 이전 1 다음
