찾다

집 >백엔드 개발 >PHP 튜토리얼 >PHP 마스터 | PHP 개발자의 데이터 구조 : 스택 및 대기열

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

Christopher Nolan
Christopher Nolan원래의
2025-02-23 11:35:39127검색

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

PHP 마스터 | PHP 개발자의 데이터 구조 : 스택 및 대기열크로스 (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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

php sentinel less String Array Object NULL define if for while include continue using class Interface Property Collection pointer number function default this overflow table database Access Other
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
이전 기사：PHP 스트림을 효과적으로 사용합니다다음 기사：없음

관련 기사

더보기