데이터 구조 학습 총화 - 5. 스 택
41831 단어 데이터 구조
데이터 구조 학습 총화 - 5. 스 택
： （stack）
5.1 창고 의 정의
스 택 (stack) 은 표 끝 에 만 삽입 하고 삭제 하 는 선형 표 입 니 다.
저 희 는 삽입 과 삭 제 를 허용 하 는 한 끝 을 스 택 지붕 (top) 이 라 고 부 르 고 다른 한 끝 은 스 택 바닥 (bottom) 이 라 고 부 르 며 데이터 요 소 를 포함 하지 않 은 스 택 을 빈 스 택 이 라 고 부 릅 니 다.스 택 은 후진 선 출 (Last In First Out) 의 선형 표 라 고도 부 르 는데 LIFO 구조 라 고 부른다.
스 택 의 정 의 를 이해 하려 면 주의해 야 합 니 다:
5.2 스 택 의 순서 저장 구조 및 실현
5.2.1 스 택 의 순서 저장 구조
， ， 。
저 희 는 top 변 수 를 정의 하여 스 택 꼭대기 요소 가 배열 에 있 는 위 치 를 표시 합 니 다. 이 는 스 택 꼭대기 의 top 이 커지 고 작 아 지 는 것 을 의미 합 니 다.스 택 의 길이 가 StackSize 이면 스 택 꼭대기 위치 top 은 StackSize 보다 작 아야 합 니 다.스 택 에 하나의 요소 가 존재 할 때 top 은 0 과 같 기 때문에 우 리 는 보통 빈 스 택 의 판정 조건 을 top 은 - 1 과 같 습 니 다.
5.2.2 스 택 의 순서 저장 구조 - 스 택 작업
class Stack
{
protected $stack; //
protected $top = -1; //
protected $out; //
protected static $maxLength; //
public function __construct($maxLength)
{
$this->stack = [];
self::$maxLength = $maxLength;
}
/**
* @return array
*/
public function getStack()
{
return $this->stack;
}
/**
*
*
* @param $elem
* @return bool|int
*/
public function push ($elem)
{
//
if ($this->top == self::$maxLength - 1) {
return false;
}
//
$this->top++;
//
$this->stack[$this->top] = $elem;
return $this->top;
}
}
5.2.3 스 택 의 순서 저장 구조 - 스 택 작업
class Stack
{
protected $stack; //
protected $top = -1; //
protected $out; //
protected static $maxLength; //
public function __construct($maxLength)
{
$this->stack = [];
self::$maxLength = $maxLength;
}
...
/**
*
*
* @return bool|mixed
*/
public function pop ()
{
//
if ($this->top == -1) {
return false;
}
//
$this->out = $this->stack[$this->top];
//
unset($this->stack[$this->top]);
//
$this->top--;
return $this->out;
}
}
5.3 스 택 공간 공유
우 리 는 하나의 배열 로 두 개의 스 택 을 저장 할 수 있다.배열 은 두 개의 점 이 있 고 두 개의 스 택 은 두 개의 스 택 밑 이 있 습 니 다. 한 스 택 밑 을 배열 의 시작 단 으로 합 니 다. 즉, 아래 는 0 곳 으로 표시 하고 다른 스 택 은 스 택 의 끝 입 니 다. 즉, 아래 는 배열 의 길이 n - 1 곳 으로 표시 합 니 다.이렇게두 스 택 에 원 소 를 추가 하면 양 끝 점 이 중간 으로 뻗 는 것 입 니 다.
사실 관건 적 인 사 고 는 배열 의 양 끝 에서 중간 에 접근 하 는 것 이다.top 1 과 top 2 는 스 택 1 과 스 택 2 의 스 택 포인터 로 두 개의 스 택 지붕 이 만 나 지 않 으 면 두 개의 스 택 을 계속 사용 할 수 있 습 니 다.스 택 1 이 비어 있 을 때 top 1 은 - 1 시 입 니 다.top 2 가 n 과 같 을 때, 즉 스 택 2 가 비어 있 을 때.스 택 2 가 빈 스 택 이 라면 스 택 1 의 top 1 은 n - 1 일 때 스 택 1 이 가득 합 니 다.스 택 1 이 빈 스 택 일 때 top 2 가 0 일 때 스 택 2 가 가득 합 니 다.그러나 더 많은 상황 은 사실은 내 가 방금 말 한 것 이다. 두 창고 가 만 났 을 때, 즉 두 포인터 사이 의 차이 가 1 일 때, 즉 top 1 + 1 = = top 2 는 창고 가 꽉 찼 다.
5.3.1 공유 스 택 스 택 작업
class SharedStack
{
protected $stack; //
protected $topOne; // 1
protected $topTwo; // 2
protected static $maxLength; //
public function __construct($maxLength)
{
$this->stack = [];
self::$maxLength = $maxLength;
}
/**
* @return array
*/
public function getStack()
{
return $this->stack;
}
/**
*
*
* @param $stackNum 1/2
* @param $e //
* @return bool|mixed
*/
public function push($stackNum, $e)
{
//
if ($this->topOne + 1 == $this->topTwo) {
return false;
}
switch ($stackNum)
{
// 1
case 1 :
$this->topOne++;
$this->stack[$this->topOne] = $e;
$key = $this->topOne;
break;
// 2
case 2 :
$this->topTwo--;
$this->stack[$this->topTwo] = $e;
$key = $this->topTwo;
break;
default :
$this->topOne++;
$this->stack[$this->topOne] = $e;
$key = $this->topOne;
break;
}
return $key;
}
...
}
5.3.1 공유 창고 출고 작업
class SharedStack
{
protected $stack; //
protected $topOne; // 1
protected $topTwo; // 2
protected static $maxLength; //
public function __construct($maxLength)
{
$this->stack = [];
self::$maxLength = $maxLength;
}
/**
* @return array
*/
public function getStack()
{
return $this->stack;
}
...
/**
*
*
* @param $stackNum 1/2
* @return bool|mixed
*/
public function pop($stackNum)
{
switch ($stackNum) {
// 1
case 1 :
if ($this->topOne == 0) {
return false;
}
$e = $this->stack[$this->topOne];
unset($this->stack[$this->topOne]);
$this->topOne--;
break;
// 2
case 2 :
if ($this->topTwo == self::$maxLength) {
return false;
}
$e = $this->stack[$this->topTwo];
unset($this->stack[$this->topTwo]);
$this->topTwo++;
break;
default :
if ($this->topOne == 0) {
return false;
}
$e = $this->stack[$this->topOne];
unset($this->stack[$this->topOne]);
$this->topOne--;
break;
}
return $e;
}
}
5.4 스 택 의 응용 - 재 귀
：
5.4.1 피 보 나 끈기 수열 실현
피 보 나치 수열 (Fibonacci sequence) 은 황금 분할 수열 이 라 고도 부 르 는데 수학자 레오 나르도 피 보 나치 (Leonardoda Fibonacci) 가 토끼 번식 을 예 로 들 어 도입 되 었 기 때문에 '토끼 수열' 이 라 고도 부른다. 수학 적 으로피 보 나치 수열 은 다음 과 같이 전달 하 는 방법 으로 정의 된다. * F (1) = 1, F (2) = 1, F (n) = F (n - 1) + F (n - 2) (n > = 3, n * 8712 ° N) * * 현대 물리, 준 결정 구조, 화학 등 분야 에서 피 보 나치 수열 은 모두 직접적인 응용 이 있 기 때문에 미국 수학 회 는 1963 년 부터 을 이름 으로 한 수학 잡 지 를 출판 했다.이 방면 의 연구 성 과 를 전문 적 으로 게재 하 는 데 쓰 인 다.
class FibonacciSequence
{
public $num;
public function __construct($num)
{
$this->num = $num;
}
public function init()
{
$fbi = [];
for ($i = 0; $i < $this->num; $i++)
{
array_push($fbi, $this->Fbi($i));
}
$array['sum'] = array_sum($fbi);
$array['fbi'] = $fbi;
return $return;
}
protected function Fbi($i)
{
if ($i < 2) {
return $i == 0 ? 0 : 1;
}
return $this->Fbi($i - 1) + $this->Fbi($i - 2);
}
}
$fbi = new FibonacciSequence(10);
print_r($fbi->init());
5.4.2 귀속 정의
， 。 ， 。
물론 배달 과정 을 쓰 는 것 이 가장 두 려 운 것 은 영원히 끝나 지 않 는 무한 한 재 귀 총 에 빠 지 는 것 이다. 따라서 모든 재 귀 정 의 는 적어도 하나의 조건 이 있어 야 한다. 만족 할 때 재 귀 는 더 이상 진행 하지 않 는 다. 즉, 자신 을 인용 하지 않 고 반환 값 으로 물 러 나 는 것 이다.
5.4.3 창고 의 인용 - 사 칙 연산 표현 식 값 구하 기
5.4.3.1 접미사 (역 폴란드) 표현법 정의
， （Reverse Pollish Notation, RPN） 。
5.4.3.2 접미사 식 계산 결과
먼저 '9 + (3 - 1) * 3 + 10/2' 에 대해 알 아 보 겠 습 니 다.접미사 표현 식 을 사용 하려 면 '931 - 3 * + 102/+' 여야 합 니 다. 이런 표현 식 을 접미사 표현 식 이 라 고 합 니 다.접미사 라 고 부 르 는 이 유 는 모든 기호 가 숫자 를 연산 하려 는 뒤에 나타 나 기 때문이다.
접미사 표현 식: 931 - 3 * + 102/+ 규칙: 왼쪽 에서 오른쪽으로 표현 식 의 모든 숫자 와 기 호 를 옮 겨 다 니 며 숫자 를 만나면 바로 스 택 에 들 어가 고 기호 가 있 으 면 스 택 꼭대기 에 있 는 두 개의 숫자 를 스 택 에서 나 와 연산 을 하고 연산 결 과 를 스 택 에 들 어가 최종 결 과 를 얻 을 때 까지 합 니 다.
우 리 는 평소에 사용 하 는 표준 사 칙 연산 식, 즉 '9 + (3 - 1) * 3 + 10/2' 를 접두사 표현 식 이 라 고 합 니 다. 모든 연산 기 호 는 두 숫자 사이 에 있 기 때문에 현재 우리 의 문 제 는 접두사 에서 접두사 로 전환 하 는 것 입 니 다.
：“9 + （3 - 1）* 3 + 10 / 2” “9 3 1 - 3 * + 10 2 / +”。
규칙: 왼쪽 에서 오른쪽으로 접미사 식 의 모든 숫자 와 기 호 를 옮 겨 다 니 며 숫자 라면 출력 합 니 다. 접미사 식 의 일부분 이 됩 니 다. 기호 라면 스 택 기호 와 의 우선 순 위 를 판단 합 니 다. 오른쪽 괄호 나 우선 순위 가 낮 거나 스 택 정상 기호 (곱 하기 우선 가감) 입 니 다.스 택 상단 요 소 는 스 택 에서 순서대로 출력 하고 현재 기 호 를 스 택 에 넣 으 며 최종 출력 접미사 표현 식 까지 입 니 다.
좋은 웹페이지 즐겨찾기
