스택 자료 삭제 알고리즘 문제 관련 궁금한 점

조회수 574회

스택의 자료 삭제 알고리즘이다. 괄호 안에 들어갈 내용으로 가장 적합한 것은?(단, Top은 스택 포인터이고, S는 스택 이름이다.) *답: Under flow

if Top = 0
    then(        )
else {
    Remove S(Top)
    Top = Top -1
}

해당 문제의 코드는 연결 리스트로 스택을 구현한 것이 아니라 그냥 스택인 건가요? (연결 리스트 스택의 Top은 마지막 원소의 주소를 저장하기에 유추) 그런데 왜 Top이 포인터가 아닌데도 스택 포인터라고 부르는 건가요? 그리고 Top이 0이면 왜 Under flow인 건가요? Top이 0이면 스택에 원소가 하나 있는 거니까 삭제할 수 있는 거 아닌가요? 만약 해당 문제가 특정 언어로 표현된 것이 아니라 알고리즘으로 작성된 문제라서 Top이 원소의 개수를 표현한다고 해도 Top이 0이면 왜 Stack empty를 반환하는 게 아니라 Under flow를 반환하는지 설명해주실 수 있는 분 있을까요?

1 답변

  • 문제에서 Top을 스택 포인터라고 언급했습니다. 관습적으로 포인터 값이 0인 경우 포인터가 가리키는 것이 없음을 뜻하므로 if Top=0은 스택에 아무것도 없다라고 해석하는 것이 맞습니다.

    질문자 분은 Top을 포인터가 아니라고 질문하셨는데, 문제의 첫줄에 포인터라고 적혀있습니다. 간혹 간단한 스택의 구현에서 Top을 0-인덱스 기반의 최신 값이 저장된 배열의 인덱스로 정하고 스택을 만드는 경우도 있습니다만 문제에서 포인터라고 언급을 했으므로 그 경우에 해당하지 않습니다.

    빈 스택에서 pop을 하면 Under flow가 발생하기 때문에 pop할수 없고, 실제로 Under flow를 발생시키면 안되기 때문에 보통 예외를 던집니다.

    그리고 스택은 리스트보다는 벡터로 만드는 것이 유지 보수 및 실행 속도 측면에서 유리합니다. 표준 라이브러리들은 자료형식을 지정하지 않으면 덱을 이용해서 스택을 구현합니다.

    • (•́ ✖ •̀)
      알 수 없는 사용자
    • 아 책에 예제가 있는데 SP를 포인터가 아닌 int형으로 선언했는데도 스택 포인터라고 표현하길래 질문한건데 이 경우에는 왜 SP로 선언하는지 알 수 있을까요? 그리고 Top을 포인터로 선언 했을 때도 Top이 스택의 개수를 가지고 있을 수 있는건가요? lsy 2023.10.22 20:21
    • 저는 Top이 link 필드의 메모리만 만드는 예제만 보았는데, 저 문제의 경우에는 Top을 data 필드랑 link 필드 두 개의 메모리를 만들어서 data 필드에 스택의 개수를 저장하는 건가요? lsy 2023.10.22 20:22
    • 아니면 저 문제에서 Top=NULL 대신에 Top=0으로 표시한걸까요? lsy 2023.10.22 20:25
    • 1) 배열의 인덱스를 저장하는 변수도 추상적으로는 포인터라는 용어를 사용할 수도 있습니다. 가리키는 값이기 때문에... 그런데 포인터라는 자료형이 존재하는 언어에서는 용어가 혼동될수 있어서 특정 언어에서의 용어인지, 스택이라는 자료형의 추상적인 설명에서의 용어인지에 따라서 해석을 잘 해야겠습니다. 2) 스택은 최신 자료를 pop할수 있는 자료일 뿐입니다. 따라서 스택을 구현할 때 스택의 데이터의 수를 저장하는 변수를 만들지 않아도 됩니다. 필수가 아닙니다. 3) 저는 질문의 코드를 의사코드(pseudo code)라고 생각하고 답변을 달았던 것입니다. 알 수 없는 사용자 2023.10.23 16:59

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)