LIFO 대 FIFO

LIFO는 Last In, First Out의 약자입니다. 마찬가지로 스택에 넣은 마지막 항목은 스택에서 가져온 첫 번째 항목입니다.

당신이 당신의 요리 비유로 설명 한 것은 ( 첫 번째 개정판에서 ) 대기열 또는 선입 선출 (FIFO), 선입 선출 (First In, First Out)입니다.

둘의 주요 차이점은 LIFO / 스택이 같은 끝에서 밀고 (삽입) 튀어 나오고 (제거), FIFO / 대기는 반대쪽 끝에서 그렇다는 것입니다.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

스택 포인터

스택의 후드에서 일어나는 일을 살펴 보겠습니다. 여기에 약간의 메모리가 있습니다. 각 상자는 주소입니다 :

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

그리고 현재 비어있는 스택의 맨 아래를 가리키는 스택 포인터가 있습니다 (스택이 커지거나 커지는 지 여부는 여기에서 특별히 관련이 없으므로 무시할 것입니다. 그러나 물론 실제로는 어떤 작업이 추가되는지 결정합니다) SP에서 빼는 것).

a, b, and c다시 밀어 봅시다 . 왼쪽의 그래픽, 중간의 “높은 수준”작업, 오른쪽의 C-ish 의사 코드 :

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

보시다시피, 우리는 매번 push스택 포인터가 가리키는 위치에 인수를 삽입하고 다음 위치를 가리 키도록 스택 포인터를 조정합니다.

이제 팝하자 :

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Pop의 반대입니다 push. 스택 포인터를 이전 위치를 가리 키도록 조정하고 있던 위치의 항목을 제거합니다 (일반적으로 호출 한 사람에게 반환 pop).

당신은 아마 저를 발견 b하고 c메모리에 남아 있습니다. 나는 그것들이 오타가 아니라고 확신하고 싶습니다. 우리는 곧 다시 돌아올 것입니다.

스택 포인터가없는 수명

스택 포인터가 없으면 어떻게되는지 봅시다. 다시 밀면서 시작 :

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

어, 흠 … 스택 포인터가 없으면 가리키는 주소로 무언가를 옮길 수 없습니다. 상단이 아닌 밑을 가리키는 포인터를 사용할 수 있습니다.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

어 오. 스택베이스의 고정 값을 변경할 수 없으므로 동일한 위치 a로 밀어서 덮어 씁니다 b.

우리가 몇 번이나 밀 었는지 추적 해 보지 않겠습니까? 또한 우리가 터진 시간을 추적해야합니다.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

잘 작동하지만 실제로 *pointer는 이전과 거의 비슷하지만 입력하는 것이 아니라 pointer[offset]말할 것도없이 (추가 산술이 없음) 보다 저렴 합니다. 이것은 나에게 손실처럼 보인다.

다시 해보자. Pascal 문자열 스타일을 사용하여 배열 기반 컬렉션의 끝을 찾는 대신 (컬렉션에 몇 개의 항목이 있는지 추적) C 문자열 스타일을 사용해 봅니다 (처음부터 끝까지 스캔).

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

이미 문제를 추측했을 수도 있습니다. 초기화되지 않은 메모리는 0으로 보장되지 않습니다. 따라서 top to place를 찾으면 a임의의 가비지가있는 사용되지 않는 메모리 위치를 건너 뜁니다. 마찬가지로, 상단까지 스캔 할 때, 우리 a는 방금 밀어 낸 메모리 너머로 넘어 0가게 됩니다. 마지막으로 발생하는 다른 메모리 위치를 찾을 때까지 되돌아 가서 바로 이전에 임의의 쓰레기를 반환합니다.

그것은 수정하기가 쉽고 , 스택에 맨 위에 항상으로 표시되도록 작업을 추가 Push하고 Pop업데이트해야하며 0그러한 종결 자로 스택을 초기화해야합니다. 물론 0이것은 스택의 실제 값으로 (또는 종료 자로 선택한 값)도 가질 수 없다는 것을 의미 합니다.

또한 O (1) 연산을 O (n) 연산으로 변경했습니다.

TL; DR

스택 포인터는 모든 작업이 발생 하는 스택의 상단을 추적 합니다. 이 그것을 제거의 정렬하는 방법이 있습니다 ( bp[count]그리고 top여전히 기본적으로 스택 포인터입니다)하지만를 두 끝은 더 느린 단순히 스택 포인터를하는 것보다 복잡하고된다. 스택의 상단이 어디에 있는지 알지 못하면 스택을 사용할 수 없습니다.

참고 : x86에서 런타임 스택의 “하단”을 가리키는 스택 포인터는 전체 런타임 스택이 거꾸로되어있는 것과 관련된 오해 일 수 있습니다. 즉, 스택의베이스는 높은 메모리 주소에 배치되고 스택의 끝은 낮은 메모리 주소로 커집니다. 스택 포인터 는 모든 동작이 발생하는 스택의 끝을 가리키며 해당 팁은 스택의베이스보다 낮은 메모리 주소에 있습니다.

---

답변