소개
데이터 구조를 구성하는 저장소에서 컴퓨터 그래서 우리가 할 수 있는 효율적으로 액세스하고 데이터 변경. 스택 및 대기열은 컴퓨터 과학에서 정의 된 초기 데이터 구조 중 일부입니다.
간단하게 배우고 구현하기 쉬운,그들의 사용은 일반적이고 당신은 대부분을 찾아 자신이 그들을 통합 소프트웨어에서 다양한 작업입니다.
스택과 큐가 배열 또는 링크 된 목록으로 구현되는 것이 일반적입니다. 스택과 큐를 모두 수용하기 위해List데이터 구조에 의존 할 것입니다.
어떻게 작동합니까?
스택
스택은 이름에서 알 수 있듯이 Last-in-First-Out(LIFO)원칙을 따릅니다. 로 겹쳐 쌓이는 경우는 동전 중 하나는 다른 상단에,마지막 우리는 동전에 최고입니다 하나는 첫 번째 스택에서 제거됩니다.
을 구현하는 스택에서,우리는 두 가지 간단한 조작:
push-추가 요소의 정상에 스택:
pop-원소를 제거에서 최고의 스택:
큐
큐, 같은 이름에서 알 수 있듯이,따라 First-in-First-Out(FIFO)원칙으로 합니다. 으면 기다리는 큐에 영화에 대한 티켓은,첫 번째 줄을 서서 첫 번째 중 하나의 티켓을 구입하고 즐길 수 있는 영화.
을 구현하는 큐에서,우리는 두 가지 간단한 조작:
enqueue-추가 요소의 끝에 큐:
dequeue-는 요소를 제거합 시작 부분에서의 큐:
스택과 큐 목록을 사용하여
Python 의 내장에서List데이터 구조와 함께 제공되는 방법을 시뮬레이션 모두에 스택과 큐 작업입니다.문자 스택을 생각해 봅시다.
우리는 동일한 함수를 사용하여 큐를 구현할 수 있습니다. pop함수는 선택적으로 검색하려는 항목의 인덱스를 인수로 사용합니다.
그래서 우리가 사용할 수 있는pop0을 얻기 위해,큐합니다.
“고려하십시오 큐”의 과일:
또,여기서 우리가 사용하는appendpopoperations 의 목록을 시뮬레이션 core operations 의합니다.
스택과 큐 시스 도서관
파이썬은deque(발음’갑’)라이브러리 제공하는 순서 효율적인 방법으로 작업하택 또는 바다입니다.
deque에 대한 짧은 두 종료 큐-일반화된 큐를 얻을 수 있는 첫 번째 또는 마지막 요소가 저장된다.
경우에 당신은 더 많은 것을 배우고 싶어에 대해deque라이브러리와 다른 유형의 컬렉션을 제공하는 파이썬,읽을 수 있습니다 우리의 소개하는 파이썬’s 컬렉션 모듈 문서입니다.
엄격한 구현에서는 파이썬
경우 필요한 코드 스택을 제공하는Listinsertremove이나 기타 목록하는 기능에 영향을 미칠 것이기 위해 귀하의 스택! 이것은 더 이상해야 할 방식으로 기능하지 않기 때문에 스택을 정의하는 요점을 근본적으로 망칩니다.데이터에서 유효한 작업 만 수행 할 수 있도록 보장하려는 경우가 있습니다.각 데이터 구조에 필요한 메소드 만 노출하는 클래스를 만들 수 있습니다.
이렇게 만들어 보겠 라는 파일을 새로stack_queue.py고 정의하는 두 개의 클래스:
를 사용하는 프로그래머의StackQueue은 지금 사용하는 것이 좋은 방법을 제공된 데이터를 조작 대신 합니다.
예제
당신이 새로운 워드 프로세서에서 일하는 개발자라고 상상해보십시오. 사용자가 세션이 시작될 때까지 작업을 역 추적 할 수 있도록 실행 취소 기능을 만드는 임무가 주어집니다.
스택은이 시나리오에 이상적인 적합입니다. 우리는 사용자가 스택에 밀어서 취하는 모든 작업을 기록 할 수 있습니다. 사용자가 작업을 실행 취소하고 싶을 때 스택에서 팝업됩니다. 우리는 다음과 같은 기능을 신속하게 시뮬레이션 할 수 있습니다.
큐는 프로그래밍에서도 널리 사용됩니다. 스트리트 파이터 또는 슈퍼 스매쉬 형제와 같은 게임을 생각해보십시오. 해당 게임의 플레이어는 버튼 조합을 눌러 특별한 동작을 수행 할 수 있습니다. 이러한 버튼 조합은 대기열에 저장할 수 있습니다.
이제 새로운 격투 게임에서 일하는 개발자라고 상상해보십시오. 게임에서 버튼을 누를 때마다 입력 이벤트가 발생합니다. 테스터는 버튼을 너무 빨리 누르면 게임이 첫 번째 동작 만 처리하고 특수 동작이 작동하지 않는다는 것을 알았습니다!대기열로 해결할 수 있습니다. 우리는 그들이 올 때 모든 입력 이벤트를 대기시킬 수 있습니다. 이 방법으로 중요하지 않는 경우에는 입력한 이벤트와 함께 약간의 시간,그들 사이에 그들은 모두 저장되고 사용할 수 있 처리합니다. 우리가 움직임을 처리 할 때 우리는 그것들을 제거 할 수 있습니다. 특별한 움직임을 운동할 수 있는 다음과 같다:
결론
스택과 큐는 간단한 데이터 구조물을 우리에게 허락된 데이터를 저장하고 검색 순차적으로 동작한다. 스택에서 우리가 입력 한 마지막 항목이 가장 먼저 나옵니다. 대기열에서 우리가 입력하는 첫 번째 항목이 먼저 나옵니다.
우리는 항목을 추가할 수 있습니다 스택을 사용하는pushpopenqueuedequeue작업입니다.
파이썬에서는 내장 된List데이터 구조를 사용하여 스택과 큐를 구현할 수 있습니다. Python 에는 하나의 객체에서 스택 및 큐 작업을 효율적으로 제공 할 수있는deque라이브러리도 있습니다. 마지막으로 데이터를보다 엄격하게 제어하기 위해 스택 및 큐 클래스를 만들었습니다.
많은 실제 활용 사례에 대한 스택과 큐,그들을 이해할 수 있게 많이 해결하기 위해 데이터 저장에 문제가 쉽고 효과적인 방식이다.