PHP 마스터 | PHP 개발자의 데이터 구조 : 스택 및 대기열

데이터 구조 또는 초록 데이터 유형 (ADT)는 그 자체로 수행 할 수 있고 해당 작업의 영향에 대한 제약에 의해 제한되는 작업 모음에 의해 정의 된 모델입니다. 그것은 기본 데이터에 수행 할 수있는 일과 수행 방법 사이에 벽을 만듭니다. 우리 대부분은 정상적인 일상적인 사용으로 스택과 큐에 익숙하지만 슈퍼마켓 대기열과 자동 판매기는 데이터 구조와 어떤 관련이 있습니까? 알아 봅시다. 이 기사에서는 일상적인 사용에서 시작된 두 가지 기본 추상 데이터 유형 인 스택 및 큐를 소개합니다. 키 테이크 아웃 추상 데이터 유형 (ADT)은 수행 할 수있는 일련의 작업 세트로 정의 된 모델입니다. 스택과 대기열은 일상적인 사용으로 기원을 가진 기본 광고입니다. 컴퓨터 과학에서 스택은 마지막 객체가 처음으로 제거 된 (LIFO)이며, 대기열은 첫 번째, 첫 번째-첫 번째 (FIFO)로 작동하는 순차적 인 컬렉션입니다. 스택은 이미 푸시 및 팝 작업을 제공하므로 배열을 사용하여 구현할 수 있습니다. 스택을 정의하는 기본 작업에는 Init (스택 생성), 푸시 (상단에 항목 추가), 팝 (마지막 항목 제거), 상단 (제거하지 않고 상단의 항목을 봅니다)이 포함됩니다. 스택에 더 이상 항목이 포함되어 있는지 여부) PHP의 SPL 확장은 SPLSTACK 클래스를 포함한 표준 데이터 구조 세트를 제공합니다. 이중 연결 목록으로 구현 된 Splstack 클래스는 통과 가능한 스택을 구현할 수있는 용량을 제공합니다. Splstack으로 구현 된 ReadingList 클래스는 스택을 앞으로 (하향식) 및 뒤로 (하향식) 트래버링 할 수 있습니다. 다른 추상 데이터 유형 인 큐는 첫 번째, FIFO (First-At) (FIFO)로 작동합니다. 대기열을 정의하는 기본 작업에는 init (대기열 생성), enqueue (끝에 항목 추가), Dequeue (전면에서 항목 제거) 및 isempty (대기열에 더 이상 항목이 포함되어 있지 않든 반환)가 포함됩니다. 이중 연결 목록을 사용하여 구현 된 PHP의 Splque Class는 큐를 구현할 수 있습니다.

스택 일반적으로 스택은 일반적으로 레이어로 배열되는 물체 더미 (예 : 책상에 책 더미 또는 학교 식당의 트레이 스택입니다. 컴퓨터 과학 용어에서 스택은 특정 속성을 가진 순차적 인 컬렉션입니다. 그 점에서 스택에 마지막으로 배치 된 객체는 첫 번째 객체가 제거됩니다. 이 속성은 일반적으로

마지막으로

또는 lifo라고합니다. 사탕, 칩 및 담배 자동 판매기도 같은 원칙으로 작동합니다. 랙에로드 된 마지막 항목은 먼저 분배됩니다. 추상적 인 용어로, 스택은 ( "푸시")에 추가 된 모든 항목의 선형 목록이며 ( "팝") 목록이 한쪽 끝으로 제한됩니다. ). 스택을 정의하는 기본 작업은 다음과 같습니다.
• init - 스택을 만듭니다. 푸시 - 스택 상단에 항목을 추가하십시오. 팝 - 스택 상단에 추가 된 마지막 항목을 제거하십시오.
• 상단 - 스택 상단에있는 항목을 제거하지 않고보십시오. isempty - 스택에 더 이상 항목이 포함되어 있지 않든 반환합니다.
• 최대 용량을 갖도록 스택을 구현할 수도 있습니다. 스택이 가득 차 있고 새 엔티티를 수용하기에 충분한 슬롯이 포함되어 있지 않으면 오버플로 - 따라서 "스택 오버플로"라는 문구라고합니다. 마찬가지로, 팝 작업이 빈 스택에서 시도되면 "스택 언더 플로우"가 발생합니다. 우리의 스택은 Lifo 속성과 여러 기본 작업, 특히 푸시 및 팝에 의해 정의된다는 것을 알면 배열이 이미 푸시 및 팝 작업을 제공하므로 배열을 사용하여 스택을 쉽게 구현할 수 있습니다. 간단한 스택은 다음과 같습니다.
이 예에서는 array_push () 및 array_pop () 대신 array_unshift () 및 array_shift ()를 사용하여 스택의 첫 번째 요소가 항상 상단이되도록했습니다. Array_Push () 및 Array_Pop ()을 사용하여 의미 론적 일관성을 유지할 수 있습니다.이 경우 스택의 N 번째 요소가 상단이됩니다. 추상 데이터 유형의 전체 목적은 실제 구현에서 데이터의 조작을 추상화하는 것이기 때문에 어느 쪽도 차이가 없습니다. 스택에 몇 가지 항목을 추가해 봅시다.
• 스택에서 일부 항목을 제거하려면 :
스택 상단에 무엇이 있는지 보자 :
• 우리가 그것을 제거하면 어떻게됩니까?
그리고 새 항목을 추가하면?

스택이 첫 번째로 마지막으로 작동하는 것을 볼 수 있습니다. 스택에 마지막으로 추가 된 것은 가장 먼저 제거됩니다. 스택이 비어있을 때까지 계속 팝 아이템을 사용하면 스택 언더 플로우 런타임 예외가 발생합니다. 오, 안녕하세요… PHP는 프로그램 실행 호출 스택을 예외 및 예외까지 보여주는 스택 추적을 친절하게 제공했습니다! Splstack SPL Extension은 SPLSTACK 클래스 (PHP5> = 5.3.0)를 포함한 표준 데이터 구조 세트를 제공합니다. 우리는 동일한 객체를 구현할 수 있지만 훨씬 더 간절하지만 다음과 같이 splstack을 사용합니다. Splstack 클래스는 원래 정의한 것보다 몇 가지 방법을 구현합니다. SPLSTACK은 이중 연결 목록으로 구현되기 때문에 통과 가능한 스택을 구현할 수있는 용량을 제공하기 때문입니다. 다른 추상 데이터 형식 자체 인 링크 된 목록은 컬렉션의 각 노드가 수집의 다음 노드에 대한 포인터를 유지하는 특정 시퀀스를 나타내는 데 사용되는 선형 객체 (노드)입니다. 가장 간단한 형태로 링크 된 목록은 다음과 같습니다.

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

이중 연결 목록에 각 노드에는 두 개의 포인터가 있으며, 각 노드에는 컬렉션의 다음 및 이전 노드를 가리 킵니다. 이러한 유형의 데이터 구조는 양방향으로 이동할 수 있습니다.

크로스 (x)로 표시된 노드는 널 또는 센티넬 노드를 나타냅니다.이 노드는 트래버스 경로의 끝을 지정합니다 (즉, 경로 터미네이터). ReadingList는 splstack으로 구현되므로 스택을 앞으로 (하향식) 및 뒤로 (하향)로 이동할 수 있습니다. Splstack의 기본 트래버스 모드는 Lifo입니다. 스택을 역순으로 통과하려면 반복기 모드를 FIFO로 설정합니다 (첫 번째, 우선).

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

대기열

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

슈퍼마켓 결제에서 한 번 라인을 본 적이 있다면 첫 번째 사람이 먼저 제공되는 것을 알게 될 것입니다. 컴퓨터 용어에서 큐는 또 다른 추상 데이터 유형이며, 먼저

에서 첫 번째

기준 또는 FIFO에서 작동합니다. 인벤토리는 특히 이러한 품목이 부패하기 쉬운 성격 인 경우 FIFO 기준으로 관리됩니다. 대기열을 정의하는 기본 작업은 다음과 같습니다. init - 대기열을 만듭니다. enqueue - 대기열의 "끝"(꼬리)에 항목을 추가합니다. dequeue - 대기열의 "전면"(헤드)에서 항목을 제거하십시오. isempty - 대기열에 더 이상 항목이 포함되어 있지 않든 반환. Splqueue는 이중 연결 목록을 사용하여 구현되므로 상단 및 POP의 의미 론적 의미 가이 맥락에서 역전됩니다. ReadingList 클래스를 대기열로 재정의하겠습니다.

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

spldoublylinkedlist 또한 ArrayAccess 인터페이스를 구현하므로 배열 요소로 Splqueue 및 Splstack에 항목을 추가 할 수도 있습니다.

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

대기열 앞에서 항목을 제거하려면 :

<span><span><?php
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span>

enqueue ()는 push ()에 대한 별칭이지만 dequeue ()는 pop ()의 별칭이 아닙니다. POP ()는 대기열의 맥락에서 다른 의미와 기능을 갖습니다. 여기에서 POP ()를 사용했다면 FIFO 규칙을 위반하는 대기열의 끝 (꼬리)에서 항목을 제거합니다. 마찬가지로, 대기열의 전면 (헤드)에 무엇이 있는지 확인하려면 top () 대신 맨 아래 ()를 사용해야합니다.

<span><span><?php
</span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>

요약 이 기사에서는 스택 및 대기열 초록 데이터 유형이 프로그래밍에 어떻게 사용되는지 보았습니다. 이러한 데이터 구조는 추상적이며, 그 자체로 수행 할 수있는 작업에 의해 정의되어 구현과 기본 데이터 사이에 벽을 만듭니다. 이러한 구조는 또한 이러한 작업의 효과에 의해 제한됩니다. 스택 상단에서 항목을 추가하거나 제거 할 수 있으며 큐 전면에서 항목을 제거하거나 큐의 후면에 항목을 추가 할 수 있습니다. Flickr를 통해 Alexandre Dulaunoy의 이미지 PHP 데이터 구조에 대한 자주 묻는 질문 (FAQ) PHP의 다양한 유형의 데이터 구조는 무엇입니까?

PHP는 배열, 객체 및 리소스를 포함한 여러 유형의 데이터 구조를 지원합니다. 배열은 PHP에서 가장 일반적이고 다재다능한 데이터 구조입니다. 다른 배열을 포함하여 모든 유형의 데이터를 보유 할 수 있으며 색인 또는 연관성이있을 수 있습니다. PHP의 객체는 속성과 방법을 가질 수있는 클래스의 인스턴스입니다. 리소스는 데이터베이스 연결과 같은 외부 리소스에 대한 참조를 보유한 특수 변수입니다. PHP에서 스택을 구현하려면 어떻게해야합니까? 스택은 LIFO를 따르는 데이터 구조의 유형입니다 ( 마지막으로, 먼저) 원칙. PHP에서는 Splstack 클래스를 사용하여 스택을 구현할 수 있습니다. push () 메소드를 사용하여 스택에 요소를 푸시하고 pop () 메소드를 사용하여 스택에서 팝 요소를 푸시 할 수 있습니다.

PHP의 어레이와 객체의 차이점은 무엇입니까?

. PHP의 배열과 객체는 두 가지 유형의 데이터 구조이지만 몇 가지 주요 차이점이 있습니다. 배열은 간단한 값 목록이며 객체는 클래스의 인스턴스이며 속성과 방법을 가질 수 있습니다. 배열은 색인화되거나 연관성이있을 수 있지만 객체는 항상 문자열 키를 사용합니다. 배열은 다재다능하고 사용하기 쉽고 물체는 더 많은 구조와 캡슐화를 제공합니다. 데이터 구조를 사용하여 PHP 코드의 성능을 향상시키는 방법은 무엇입니까?

올바른 데이터 구조를 사용하면 PHP 코드의 성능을 크게 향상시킬 수 있습니다. 예를 들어, 많은 수의 요소를 저장하고 특정 요소를 자주 검색 해야하는 경우 해시 테이블이나 세트를 사용하여 배열을 사용하는 것보다 훨씬 빠를 수 있습니다. 마찬가지로, 양쪽 끝에서 요소를 자주 추가하고 제거 해야하는 경우, Deque를 사용하는 것은 배열을 사용하는 것보다 더 효율적 일 수 있습니다.

PHP의 SpldoublylinkedList 클래스는 무엇입니까? PHP에서는 이중 링크 된 목록을 구현하는 데이터 구조입니다. 일정한 시간에 목록의 양쪽 끝에 요소를 추가, 제거 및 액세스 할 수 있습니다. 또한 목록의 요소를 반복하고 요소를 정렬하는 방법을 제공합니다.

PHP에서 큐를 구현하려면 어떻게해야합니까?

큐는 다음과 같은 데이터 구조 유형입니다. FIFO (첫 번째, 첫 번째) 원칙. PHP에서는 Splqueue 클래스를 사용하여 큐를 구현할 수 있습니다. dequeue () 메소드를 사용하여 큐에서 큐에서 큐 요소를 사용하여 큐에 요소를 큐에 넣을 수 있습니다.

php의 스택과 대기열의 차이점은 무엇입니까?

스택과 대기열은 두 가지 유형의 데이터 구조이지만 요소가 추가 및 제거되는 방법에는 주요 차이가 있습니다. 스택은 Lifo (마지막, 첫 번째, 첫 번째) 원리를 따릅니다. 이는 마지막 요소가 제거 될 첫 번째 요소가 첫 번째 요소임을 의미합니다. 반면에, 큐는 FIFO (첫 번째, 첫 번째) 원리를 따릅니다. 즉, 첫 번째 요소가 제거 될 첫 번째 요소가 제거 될 첫 번째 요소입니다. PHP에서 SplHeap 클래스를 어떻게 사용할 수 있습니까?

PHP의 SplHeap 클래스는 힙을 구현하는 데이터 구조입니다. 힙은 각 상위 노드가 하위 노드보다 작거나 같은 이진 트리의 한 유형입니다. SplHeap 클래스를 사용하여 Min-Heap 또는 Max-Heap을 만들고 힙에 요소를 추가, 제거 및 액세스 할 수 있습니다.

PHP에서 데이터 구조를 사용하면 어떤 이점이 있습니까?

PHP에서 데이터 구조를 사용하면 몇 가지 이점이 있습니다. 보다 효율적이고 논리적 인 방식으로 데이터를 구성하는 데 도움이되므로 코드를 쉽게 이해하고 유지 관리 할 수 ​​있습니다. 특히 많은 양의 데이터 또는 복잡한 작업을 처리 할 때 코드의 성능을 향상시킬 수 있습니다.

PHP에서 이진 트리를 구현할 수있는 방법은 무엇입니까?

이진 트리는 유형입니다. 각 노드에 최대 두 자녀가있는 데이터 구조의 경우 좌파 자녀와 올바른 자녀라고합니다. PHP에서는 노드 값과 왼쪽 및 오른쪽 어린이에 대한 속성이있는 클래스를 사용하여 이진 트리를 구현할 수 있습니다. 그런 다음 방법을 사용하여 트리의 노드를 추가, 제거 및 검색 할 수 있습니다.

위 내용은 PHP 마스터 | PHP 개발자의 데이터 구조 : 스택 및 대기열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!