이 글은 주로 PHP 데이터 구조의 기본 스택을 소개하며, 이는 특정 참조 가치가 있습니다. 이제는 필요한 친구들이 참조할 수 있습니다.
interface StackInterface
{
public function push(string $item);
public function pop();
public function top();
public function isEmpty();
}배열 기반 스택 구현을 살펴보겠습니다
class ArrStack implements StackInterface
{
private $stack;
private $limit;
public function __construct(int $limit = 20)
{
$this->limit = $limit;
$this->stack = [];
}
public function __get($val)
{
return $this->$val;
}
public function push(string $data = null)
{
if (count($this->stack) < $this->limit) {
array_push($this->stack, $data);
} else {
throw new \OverflowException('stack is overflow');
}
}
public function pop()
{
if ($this->isEmpty()) {
throw new \UnderflowException('stack is empty');
} else {
return array_pop($this->stack);
}
}
public function isEmpty()
{
return empty($this->stack);
}
public function top()
{
return end($this->stack);
}PHP의 강력한 배열 구조 덕분에 스택의 기본 작업 방법을 쉽게 작성할 수 있습니다. 물론, 세계 최고의 언어는 그 명성에 걸맞게 살아갑니다.
그런데 한 학우가 말하기를, 스택과 이전 연결 리스트가 모두 선형 구조라고 하더군요. 연결 리스트를 직접 사용하여 스택을 구현할 수 있나요? 이 질문은 매우 예리하며 대답은 '예'입니다.
아마도 똑똑한 학생들은 내가 이전에 스택 인터페이스를 정의한 적이 있고 스택의 구현은 위의 것 이상일 것이라고 추측했을 것입니다. 연결리스트 기반의 구현을 살펴보겠습니다.
class LinkedListStack implements StackInterface
{
private $stack;
private $limit;
public function __construct(int $limit)
{
$this->limit = $limit;
$this->stack = new LinkedList();
}
public function top()
{
return $this->stack->getNthNode($this->stack->getSize() - 1)->data;
}
public function isEmpty()
{
return $this->stack->getSize() === 0;
}
public function pop()
{
if ($this->isEmpty()) {
throw new \UnderflowException('stack is empty');
} else {
$lastItem = $this->top();
$this->stack->deleteLast();
return $lastItem;
}
}
public function push(string $item)
{
if ($this->stack->getSize() < $this->limit) {
$this->stack->insert($item);
} else {
throw new \OverflowException('stack is overflow');
}
}이전의 연결리스트 구현이 포함되어 있습니다. 자세한 내용을 이해하지 못하는 학생은 여기로 가서 살펴보세요. 일부 학생들은 다시 묻습니다. 그 스택의 용도는 무엇입니까? 이것은 매우 좋은 질문입니다. 요구사항을 살펴보겠습니다.
수학 수식 검사 클래스를 구현하고, 다음 수식을 입력하면 예상한 결과가 true가 됩니다.
"8 * (9 -2) + { (4 * 5) / ( 2 * 2) }다음 내용은 거짓입니다.
"5 * 8 * 9 / ( 3 * 2 ) )"
다음 내용도 거짓입니다.
"[{ (2 * 7) + ( 15 - 3) ]"스스로 생각해보고 구현을 살펴보세요.
class ExpressionChecker
{
//$expressions[] = "8 * (9 -2) + { (4 * 5) / ( 2 * 2) }";
//$expressions[] = "5 * 8 * 9 / ( 3 * 2 ) )";
//$expressions[] = "[{ (2 * 7) + ( 15 - 3) ]";
public function check(string $expression): bool
{
$stack = new \SplStack();
foreach (str_split($expression) as $item) {
switch ($item) {
case '{':
case '[':
case '(':
$stack->push($item);
break;
case '}':
case ']':
case ')':
if ($stack->isEmpty()) return false;
$last = $stack->pop();
if (
$item == '{' && $last != '}' ||
$item == '(' && $last != ')' ||
$item == '[' && $last != ']'
)
return false;
break;
}
}
if ($stack->isEmpty()) {
return true;
}
return false;
}
}특수 시리즈
위 내용은 모두의 학습에 도움이 되기를 바랍니다. 더 많은 관련 내용은 PHP 중국어 홈페이지를 주목해주세요!
관련 권장 사항:
php redis 잠금 및 잠금 해제 PHP 메서드 Beanstalkd 운영을 위한 매개변수 설명 및 매개변수 설명위 내용은 PHP 데이터 구조 기본 스택의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!