스택 및 큐, 왜?

Question

왜 배열 및 목록 대신 스택 또는 큐 데이터 구조를 사용해야합니까? 스택이나 대기열을 사용한다면 주 (state)에 대한 예제를 보여 주시겠습니까?

Answer 1

배열 및 목록보다 특정 방식으로 데이터를 관리하기 때문에 도움이됩니다.

큐는

스택 첫째, (LIFO)

배열과리스트는 랜덤 액세스있는 마지막 밖으로 (FIFO) 먼저, 첫 번째 아웃입니다. 그들은 매우 유연하고 또한 쉽게 부패 할 수 있습니다. 데이터를 FIFO 또는 LIFO로 관리하려는 경우 이미 구현 된 컬렉션을 사용하는 것이 가장 좋습니다.

Answer 2

데이터 구조에 특정 사용 패턴을 적용하려는 경우. 즉, 문제를 디버깅 할 때 임의의 요소가 목록의 중간에 임의로 삽입되어 일부 불변량을 엉망으로 만들지는 않을 것입니다.

Answer 3

1. 당신은 당신이에 넣어 순서대로 일을 나가 할 때 큐를 사용합니다.
2. 당신은 당신이에 넣어보다 반대 순서로 일을 나가 할 때 스택을 사용합니다.
3. 목록을 넣을 때와 관계없이 (그리고 자동으로 제거하지 않으려는 경우) 아무 것도 나오지 않을 때 목록을 사용하십시오.

Answer 4

의도적 인 문제입니다. 스택 및 대기열은 종종 배열 및 목록을 사용하여 구현되지만 요소의 추가 및 삭제가보다 엄격하게 정의됩니다.

Answer 5

스택 또는 큐는 논리적 인 데이터 구조입니다.

원한다면 "roll your own"을 원하거나 이미 구현 된 추상화를 이용할 수 있습니다.

Answer 6

다른 사람들이 이미 언급 한 사용 권한 외에도 성능 문제가 있습니다. 배열이나 List (ArrayList)의 시작 부분에서 무언가를 제거하고 싶다면 일반적으로 O (n) 시간이 걸리지 만 큐의 경우 O (1) 시간이 걸립니다. 많은 요소가 있다면 그것은 큰 차이를 만들 수 있습니다.

Answer 7

배열이나 연결된 데이터 구조를 사용하여 스택 또는 큐의 추상 데이터 형식을 나타낼 수 있으므로 질문이 모호합니다.

스택 또는 큐의 링크 된 목록 구현과 배열 구현 간의 차이점은 동적 데이터 구조와 모든 배열의 기본 절충 관계가 동일하다는 것입니다.

링크 된 대기열/연결된 스택은 합리적인 구현으로 유연하고 고속 삽입/삭제되지만 배열보다 많은 저장 공간이 필요합니다. 삽입/삭제는 공간이 부족할 때까지 배열의 끝에서 저렴합니다. 대기열 또는 스택의 배열 구현에서는 원본을 더 큰 구조로 복사해야하거나 오버플로 오류와 함께 실패해야하므로 크기를 조정하려면 더 많은 작업이 필요합니다.

Answer 8

배열/목록과 스택/대기열은 상호 배타적 인 개념이 아닙니다. 실제로 스택이나 대기열 구현은 거의 확실히 어레이 또는 목록을 사용하고 있습니다.

배열 및 목록 구조는 데이터 저장 방법에 대한 설명을 제공하며 구조에 대한 기본 작업이 복잡하다는 것을 보장합니다.

스택 및 대기열은 요소 삽입 또는 제거 방법에 대한 높은 수준의 설명을 제공합니다. 대기열 용 FIFO, 스택 용 FILO.

예를 들면. 메시지 대기열을 구현하는 경우 대기열을 사용합니다. 그러나 큐 자체는 각 메시지를 목록에 저장할 수 있습니다. 목록의 맨 앞에 "추가"메시지가 추가되면 목록의 끝에서 가져온 메시지가 "팝업"됩니다.

Answer 9

스택 및 대기열은 배열 자체가 컬렉션 내에서 작동하는 방식에서 순서를 설정하지 않는 컬렉션을 처리하는 고급 방법입니다.

스택 (LIFO - 선입 선출)과 대기열 (FIFO - 선입 선출)은 요소를 삽입하고 컬렉션에서 제거하는 순서를 지정합니다.

스택 또는 대기열 패턴을 구현하기 위해 스토리지 구조로 배열 또는 링크 된 목록을 사용할 수 있습니다. 또는 기본 구조를 사용하여 이진 트리 또는 우선 순위 대기열과 같은 더 복잡한 패턴을 만들 수도 있습니다.이 패턴은 요소 삽입 및 제거뿐 아니라 컬렉션 내부에서의 정렬도 가져올 수 있습니다.

Answer 10

당신은 카페테리아에 가봤습니까? 접시 더미가 보입니까? 깨끗한 플레이트가 스택에 추가되면 상단에 놓입니다. 플레이트가 제거되면 상단에서 제거됩니다. 따라서 LIFO (Last-In-First-Out)라고합니다. 숫자가 들어있는 것을 제외하면 컴퓨터 스택은 비슷하지만 원하는 경우 배열이나 목록에서 하나를 만들 수 있습니다. (접시 더미에 아래쪽에 스프링이 있으면 맨 위에 "밀어 넣으십시오"라고 말하면 하나를 꺼내면 "튀어 나와"그 단어가 나오는 곳입니다.)

카페테리아에서, 그들이 어디서 씻어서 돌아가는 지. 그들은 한쪽 끝에서 씻을 판을 넣는 컨베이어 벨트를 가지고 있고, 다른 쪽 끝은 같은 순서로 나옵니다. 큐 또는 FIFO (First-In-First-Out)입니다. 원한다면 배열이나리스트에서 그 중 하나를 만들 수도 있습니다.

무엇에 좋은가요? 글쎄, 당신이 나무의 데이터 구조를 가지고 있다고 가정하면 (예를 들어 거꾸로 된 나무를 제외하고는 나무로 만든 실제 나무와 같습니다), 모든 잎을 인쇄하기 위해 완전히 걸을 수있는 프로그램을 작성하려고합니다.

편도는 깊이 우선 보행을 수행하는 것입니다. 트렁크에서 시작하여 첫 번째 지점으로 이동 한 다음 해당 지점의 첫 번째 지점으로 이동하는 등 잎을 얻을 때까지 계속합니다. 그런데 어떻게 다음 지점으로 올라갈 수 있습니까? 글쎄, 당신이 지점을 내려갈 때마다, 당신은 스택의 정보를 "밀어 넣을"수 있고, 당신이 "pop"할 때 다시 되돌려 놓을 것입니다. 그것이 각 지점에서 다음에 수행 할 지점을 추적하는 방법입니다.

또 다른 방법은 폭 우선 도보입니다. 트렁크부터 시작하여 트렁크에서 모든 브랜치 번호를 매기고 그 번호를 대기열에 넣습니다. 그런 다음 상대방에게 전화 번호를 가져다가 해당 지점으로 이동하여 의 각 지점에 대해 번호를 다시 매기고 (첫 번째와 연속적으로) 번호를 매기십시오. 당신이 이것을 계속할 때 당신은 먼저 트렁크에서 1 개의 지점 인 지점들을 방문 할 것입니다. 그런 다음 트렁크에서 멀리 떨어진 두 지점 인 모든 지점을 방문하게됩니다. 결국 잎사귀에 도착하게되고 인쇄 할 수 있습니다.

이들은 프로그래밍의 두 가지 매우 기본적인 개념입니다.

Answer 11

저는 스택과 대기열 모두 응용 프로그램 요구에 따라 사용되는 메모리 액세스 개념이라고 생각합니다. 반면에 배열과 목록은 두 개의 메모리 액세스 기술이며 스택 (LIFO) 및 대기열 (FIFO) 개념을 구현하는 데 사용됩니다.