일반적으로 추상데이터 타입을 자료구조로 구현할 때는 사용되는 자료구조의 단점들을 개선하여 확장적인 구현을 하는데, 스택과 큐는 추상 데이터타입의 기능을 축소하는 것을 통해 특정 상황에서 효율적인 작동을 하게 만든 추상데이터 타입이다.
스택
21.3.24. 수정
스택은 후입선출의 기능을 가지는 추상 데이터타입이다. 이런 기능을 여러 자료구조에서 구현하고 있다.
스택은 일반적으로 배열 자료구조를 이용해 구현하며, 이 이유는 메모리의 연속성이 있기 때문에, 일반적으로 스택의 특성 상 push pop이 지역적으로 가까이서 일어나게 되고, 캐시에서 이를 효율적으로 사용할 가능성이 높기 때문이다.
스택은 사전적 의미가 쌓여 있는 더미를 뜻한다.
자료구조 형태도 비슷하다.
층층이 쌓이면 밑을 꺼낼 수 없다. 그래서 위에서부터 꺼내게 된다.
때문에 선입 후출의 방식을 가지고, 맨 뒤에서 삽입과 제거가 일어나기 때문에,
삽입과 삭제의 시간복잡도가 O(1) 이다.
단점
스택을 검색할 시 여러 부작용을 막기 위해 push(), pop() 메소드만 허용하는 경우가 많다. 스택이라는 추상 데이터 타입이 push(), pop() 의 기능만 만들어져 있다.
그러므로 검색을 할 때 원소를 전부 다 찾아야 한다. O(n) 스택 추상 데이터타입에는 검색 메소드가 없기 때문에 검색 못 한다. 이를 통해 만들어진 자료구조에서 추가적인 구현을 해 검색을 할 수 있지만, 이것은 리스트의 메소드이지 스택의 메소드가 아니다.
원소를 찾을 때까지 원소를 pop 해야 하므로 새로운 빈 스택을 만들어 이 행위를 구현할 수 있음.
용도
자료를 뒤집는데 유용함.
연산식을 처리할 때 유용 -> 특히 후위 연산자로 작성된 식
2*(4+5)- 15/3 은 후위 연산식으로 변형할 경우
245+*153/- 가 된다.
스택에 순서대로 집어넣으면서 연산자를 만날때 마다 지금까지 스택에 들어왔던 값들을 해당 연산자로 계산만 해주면 된다.
재귀함수를 재귀없이 구현할 수 있음
큐
스택과 마찬가지로 ENQUEUE 와 DEQUEUE 만 메소드로 가지는 추상데이터 타입이다.
의미는 줄을 세웠다라는 뜻이다.
놀이공원에서 줄을 오래 기다린 사람이 먼저 놀이기구를 타듯 먼저 들어온 데이터가 가장 먼저 나가게 된다.
선입선출이라고 한다.
삭제
삭제의 경우 일반 배열을 사용해서 큐를 구현하면 비효율적일 수 있다.
삽입은 뒤에서 하기 때문에 상관없지만, 삭제를 앞에서 할 경우 모든 인덱스를 다 밀어주어야 하기 때문에 O(n) 의 시간복잡도가 생긴다.
때문에 내부적으로 배열을 사용하되, 원형 버퍼의 개념을 이용하면 삭제도 O(1) 시간복잡도가 가능하다.
또한 링크드리스트를 사용해도 인덱스가 따로 없으므로 원소 삭제를 O(1) 의 시간복잡도로 구현이 가능하다.
원형버퍼의 경우 front 와 rear 의 포인터로 구현하는데, 삽입을 할 때, rear 만 뒤로 옮겨주고 삭제할 때 front를 뒤로 옮겨줌으로써 메모리 공간을 계속 이용할 수 있도록 한다.
다만 rear == front 의 경우를 버퍼가 빈 것인지, 꽉 찬것인지 잘 구분해서 처리해주어야한다.
삽입, 탐색
스택과 똑같다.
