써니 노트 써니 노트

Until now, our discussion around data structures has focused primarily on how they affect the performance of various operations. However, having a variety of data structures in your programming arsenal also allows you to create code that is simpler and easier to read. In this chapter, you’re going to discover two new data structures: stacks and queues. The truth is that these two structures are ..

배열(Array)이란 ? -데이터를 나열하고, 각 데이터에 인덱스를 부여해서 관리하는 데이터 구조 -파이썬에서는 리스트 자료구조가 배열에 해당 배열의 사용 이유, 장점과 단점 -배열은 같은 종류의 데이터를 순차적으로 저장해서 효율적으로 관리하려는 목적 ! -배열의 장점 : 인덱스를 알면 해당 구조로 빠른 접근이 가능하다 (배열을 생성할때 배열의 첫번째 위치의 메모리 address를 함께 저장하기때문에, 나머지 요소들의 인덱스만 알면 간단한 덧셈으로 다른메모리 address를 바로 알수있으므로 O(1)에 접근 가능 - 즉 다시한번 이게 가능하려면 순차적으로 저장되었을때 가능하다는 점!) => 해쉬테이블과 자주 비교해서 언급되므로 제대로 알아두기 -배열의 단점: 데이터의 추가와 삭제시 자리를 만들거나/ 자리..

스택 데이터 구조는 이름 그대로 데이터가 쌓여있는 구조이다. 따라서 층층이 쌓여있는 구조의 데이터를 다룰때 스택을 사용하면 적합하다 -가장 흔한 application은 recursive 알고리즘에서 쓰이는 콜스택이 있다. LIFO policy : last in, first out 이라는 정책을 따른다. 즉 마지막에 들어간(last in) 데이터가 먼저 추출 (fist out)되는 구조이다. 스택 데이터 구조는 pop(), push(item), peek(), isEmpty() 네가지의 operation을 지원한다. 스택은 배열처럼 i번째 요소에 constant한 접근(read)을 할 수는 없지만, 데이터를 넣고 추출하는데에는 constant한 속도로 가능하다. (배열의 경우는 shift가 필요하다)