스택과 큐
스택과 큐 자료구조는 데이터의 입력 - 출력간의 순서가 중요한 자료구조이다. 스택과 큐 자료구조를 구현하는데 다른 방법을 사용(연결리스트 등) 하기도 하지만 이미 프로그래밍 언어내에 구현되어 있는 자료구조인 배열을 사용하여 구현한다. 스택과 큐 자료구조에서 제일 중요한 것은 입력 - 출력간의 관계이며 이는 배열로 충분히 해결할 수 있기 때문이다. 그리고 이 입력-출력간의 순서는 한 번 정해지면 중간에 변경하지 않는다.
스택 (Stack)
스택 자료구조는 일종의 데이터가 쌓여진 더미(stack)라고 생각하면 좋다. 어떠한 더미를 만들 때 우리는 무언가를 쌓고 그 위에서부터 필요한 것을 빼낸다. 이와 같이 스택 자료구조는 후입선출(Last In First Out)의 입력-출력 규칙을 가진다. 배열로 생각해보았을 때, 데이터를 push 메소드를 통해 삽입하고 pop 메소드를 통해 빼내야 한다.
스택의 규칙이 이러한 특징을 지니고 있기 때문에 가장 첫 번째로 삽입된 데이터는 제일 마지막에 반환되며 가장 마지막으로 삽입된 데이터가 항상 첫 번째 순서로 반환된다. 이러한 스택의 특징을 활용한 예시로 콜스택(Call stack)을 들 수 있으며 브라우저의 히스토리 또한 이 예시로 꼽을 수 있다. 대개, 최신의 순서를 계속해서 저장해야할 필요가 있을 때 스택 자료구조를 사용하면 좋다.
스택의 Big O
스택 자료구조는 배열의 자료구조와 동일한 특징을 지니고 있다.
- 삽입(Insertion) : O(1)
스택 자료구조는 반드시 자료구조의 맨 마지막 순서에 삽입한다. - 제거(Removal) : O(1)
스택 자료구조는 반드시 자료구조의 맨 마지막 순서에서 제거한다. - 탐색(Searching): O(N)
스택 자료구조는 무엇인가를 찾기 위해서 순회를 해야만 한다. - 접근(Accessing): O(N)
스택 자료구조는 값에 접근하기 위해서 순회를 해야만 한다. (배열일 경우 index로 접근할 수 있다)
큐 (Queue)
큐 자료구조는 스택과 반대의 규칙을 따른다. 스택이 무언가를 쌓아놓은 더미라고 한다면, 큐는 무엇인가를 기다
리기위해 줄(queue)을 길게 늘어서있는 상황을 떠올리면 좋다. 줄을 서있는 상황에서 가장 먼저 온 사람은 가장 먼저 줄을 빠져나갈 수 있다. 이와 같이 큐는 선입선출(First In First Out)의 규칙을 따르는 자료구조이다. 배열로 생각해보았을 때, 큐의 데이터 삽입에는 unshift, 출력에는 shift 를 메소드를 사용할 수 있다.
큐의 이러한 특징은 첫 번째 데이터가 첫 번째로 반환되고, 마지막 데이터가 언제나 마지막으로 반환되도록 한다. 큐 자료구조는 작업의 시작 순서가 중요할 경우에 활용되기 적당한데, 예를 들어 매칭시스템, 다운로드 시스템, 프린트 순서 등이 존재한다.
큐의 Big O
큐 자료구조는 스택과 동일하게 배열의 자료구조와 동일한 특징을 지니고 있다.
- 삽입(Insertion) : O(1)
큐 자료구조는 반드시 자료구조의 맨 마지막 순서에 삽입한다. - 제거(Removal) : O(1)
큐 자료구조는 반드시 자료구조의 맨 마지막 순서에서 제거한다. - 탐색(Searching): O(N)
큐 자료구조는 무엇인가를 찾기 위해서 순회를 해야만 한다. - 접근(Accessing): O(N)
큐 자료구조는 값에 접근하기 위해서 순회를 해야만 한다. (배열일 경우 index로 접근할 수 있다)
브라우저 히스토리가 스택의 예시라니 뭔가 이해가 확 됩니당