스택과 큐와 덱 차이?

안녕하세요! 저도 평소에 생각하지 못했던 부분인데 흥미로운 마음에 답변 드립니다. 말씀하신대로 Deque 의 경우 양쪽 삽입, 삭제가 가능하기 때문에 Stack 이나 Queue 대신 사용이 가능합니다. 기능상 FIFO(선입선출), 혹은 LIFO(후입선출) 만 사용하면 되거나 혹은 그렇게 데이터가 처리되도록 강제해야하는 상황이라면 Deque 대신 Stack 이나 Queue 를 쓰는게 좀 더 명확하게 느껴질것 같습니다만 Deque 를 관리하는 모듈에서 API Interface 를 요구사항에 맞춰 명확하게만 정의하면 이부분도 이슈가 아닐수도 있을거 같네요. 모든 언어가 동일하진 않겠습니다만, Java 를 기준으로 말씀드리자면, Java 에서는 Stack 을 레거시 class 로 정의하고 있고 Stack 보다는 Deque 를 쓰는것을 권장하고 있습니다. - JDK20 Stack 공식 문서: https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/Stack.html) - JDK20 Deque 공식 문서: https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/Deque.html 그 이유로는 Stack 구현상 성능 저하가 발생할 수 있고, 초기 용량 설정이 없어 데이터가 많아지면 메모리 이슈가 발생할 수 있습니다. Stack 과 달리 Queue 의 경우 Deque 가 Queue 를 상속받는 구조여서 성능적인 부분에서 크게 차이는 없어보이고 interface 의 차이 정도만 있다고 생각되네요. 저의 짧은 지식이 부디 도움이 되시길 바랍니다.

이미 좋은 답변이 있지만, 부연 설명합니다. 어떤 자료구조나, 도구나, 라이브러리나 기능 셋 등에, 더 포괄적인 기능이 있더라도, 최소한의 간략한 기능만이 더 나은 경우도 있습니다. 스택을 쓸만한 상황에서, 덱을 활용해도 되지만, 겉으로 드러나는 인터페이스 자체를 덱으로 노출해버리면, 의도치않게, (스택 상황에서는 해서는 안되는) 바닥에 새 요소를 넣는다거나 하는 실수를 할 수도 있지요. API나 라이브러리 입장에서도 반드시 지켜야하는 최소한의 기능만을 노출하고 허용하면, 사용자가 실수할 여지도 줄고, 나중에 내부 구현을 더 낫게 교체하기도 쉽습니다. 수업에서는 특히, 직접 만들어보는 일을 할 텐데, 처음부터 덱을 만드는 것 보다는, 제일 쉬운 스택부터 만들어보는 게 쉬울 테구요.

안녕하세요, 저도 대학교 학부생으로서 자료구조에 대해 배우고 있는 학생입니다. 저도 잘은 모르지만 제 생각을 말씀 드리자면, 1. 규칙 위반. 스택 혹은 큐를 사용해도 됨에도 덱을 쓰면 스택과 큐의 규칙을 위반하게 되는 경우가 생길 것 같습니다. 이 경우 예외처리를 잘 해주면 괜찮겠지만, 굳이 위험 감수를 할 필요는 없을 것 같습니다. 2. 메모리 사용량 증가. 스택과 큐를 linked list로 구현하게 되면 head 포인터와 각 노드에는 데이터, 다음 노드의 포인터 값만을 가지고 활용을 할 수 있겠지만, 덱을 linked list로 구현을 하면 각 노드에 next 포인터 값 외에 prev 포인터 값을 넣을 공간과 tail 포인터 값이 추가로 필요하게 되어 메모리의 사용량이 증가함으로 스택만을 필요로 할 때에는 덱을 쓸 필요가 없어 보입니다. 스택의 경우에는 헤드 포인터를 계속해서 새로운 값으로 업데이트만 해주면 되고, 큐는 순서대로 헤드 와 그 다음 노드를 채워서 둘 다 헤드 값부터 배출하면 될 것 같습니다. 3. 코드의 가독성. 코드의 가독성 측면에도 구현에서 필요한 각 자료구조들을 확인할 때 덱을 큐와 스택으로 만들어서 사용하는것을 알아보는것 보다는 스택과 큐를 사용해 직관적으로 알아볼 수 있는것이 편해 보이기에 각 상황에 맞는 자료구조를 사용하는게 좋아 보입니다. 아직 부족한 점이 많은 학부생으로서 답변이 만족스러울지는 모르겠지만, 잘 부탁드립니다!!😁

기본설명을 앞에서 잘해주셔서 조금 다른 관점에서 설명을 해보겠습니다. 스택을 먼저설명드리면 a->b->c 와 같이 함수의존 호출했다고 가정해봅시다. a(){ return b(); } b(){ return c(); } a(); 이것의 진입은 a-b-c로 작동되지만 완료는 c-b-a로 작동됩니다. 함수호출이 작동되는 구조가 스택구조를 사용하기때문에 콜스택이라고 합니다. 우리가 함수로 디버깅을 할수 있는 이유가 이러한 스택구조로 정보가 전달될수 있기때문이며 재귀호출을 만들다보면 무한대로 진입하는 실수를 할때도 있는데 이때 스택오버플로우에러를 유발하게 됩니다. 스택이 최대한도 까지 쌓인 오류입니다. 우리가 만드는 기능이 접시쌓기를 한후 설거지를 제일마지막에 쌓은것부터 할수있고 제일처음에 쌓은것은 가장 마지막남은 작업이다라고 하면 이알고리즘을 이용할수 있습니다. 이전으로 돌아갈수 있는 메뉴기능을 만든다고하면 스택구조를 이용할수 있습니다. 큐의 경우 일반적으로 작업의 입력과 출력이 선형적으로 양끝에 하나씩만 있는것으로 순차성 대기열 처리를 할때 이용이됩니다. 먼저요청된 이벤트가 먼저 처리됨으로 가장 심플하며 카프카는 이 큐개념을 클러스터화된 네트워크로 고성능으로 이용할수 있는 대표적인 장치입니다. 디큐의 경우 입력과 출력이 양끝에 모두있어 스택처럼 큐처럼 사용할수도 있지만 특수한 목적으로 이용이될수있습니다. 예를 들면 스택과/큐 단점은 우선순위역전을 할수가 없습니다. 스택과 큐에서 우선순위 역전을하려면 자료구조를 모두 복제하고 재구성해야하는 성능자체에 문제가 될수 있습니다. 즉 반대의 경우도 스택기능만을 필요로한데 불필요한 작동이될수 있기때문에 이 역시 성능(불필요한 메모리+속도)의 저하가 될수 있습니다. 요약해서 다음과 같이 정리해봅니다. 스택: 이전으로 돌아가는 기능이 필요할때 / 처음입력된 이벤트가 가장 마지막에 수행될때 큐: 대기열을 순차적으로 처리할때 / 무한의 소비자가 있을때(스트림 처리) 디큐: 우선순위역전을 처리할수 있거나, 입력을 양방향으로 처리하는 특수목적의 자료구조

알고리즘을 처음 배우시는 분들에게 자주 나오는 질문입니다. 스택, 큐, 덱의 차이를 이해하기 위해서는 각자의 특성과 사용 상황을 알아야 합니다. - 스택(Stack): 스택은 LIFO(Last In First Out) 구조를 가지고 있습니다. 즉, 마지막에 들어온 데이터가 가장 먼저 나갑니다. 이 특성 때문에 어떤 작업을 역순으로 뒤집어야 할 때, 혹은 실행 취소 기능, 브라우저의 뒤로 가기 기능 등에 주로 사용됩니다. - 큐(Queue): 큐는 FIFO(First In First Out) 구조를 가지고 있습니다. 즉, 먼저 들어온 데이터가 먼저 나갑니다. 이 특성 때문에 작업의 순서를 보장해야 할 때, 혹은 너비 우선 탐색(BFS) 등에 주로 사용됩니다. - 덱(Deque): 덱은 양쪽 끝에서 삽입과 삭제가 가능합니다. 이로 인해 덱은 스택과 큐의 역할을 모두 수행할 수 있습니다. 그러나 스택과 큐를 따로 사용하는 이유는 다음과 같습니다: 1. 문제 상황에 따른 선택: 스택과 큐가 각자 잘 맞는 상황이 있습니다. 예를 들어, 괄호 짝 맞추기 문제는 스택을, 프린터 큐 문제는 큐를 사용하는 것이 더 자연스럽습니다. 덱을 사용하면 구현이 복잡해질 수 있습니다. 2. 가독성과 유지 보수: 스택과 큐는 각각의 역할이 명확하므로, 코드의 가독성을 높이고 유지 보수를 용이하게 합니다. 덱을 사용하면 코드가 복잡해지고 오류 발생 가능성이 높아질 수 있습니다. 3. 효율성: 스택과 큐는 각각의 목적에 맞게 최적화된 연산을 제공합니다. 반면에 덱은 양쪽 끝에서의 연산을 모두 지원하므로, 특정 상황에서는 스택이나 큐보다 덜 효율적일 수 있습니다. 따라서, 상황에 따라 적절한 자료 구조를 선택하는 것이 중요합니다.