[자료구조][파이썬으로 쉽게 풀어쓴 자료구조] 04 스택 문제풀기

728x90

 

🙆‍♂️연습 문제

---

4.1 스택에서 사용되는 정보의 입출력 방법은 무엇인가?

1. LIFO            2. FIFO            3.FILO            4.LILO

답 : 1번 후입선출이다.

 

4.2 스택의 응용분야로 거리가 먼 것은?

1. 미로 찾기            2. 수식 계산 및 수식 표기법            3. 운영체제의 작업 스케줄링            4. 서브루틴의 복귀번지 저장

답 : 3번 운영체제의 작업 스케줄링이다.

 

4.3 다음 중 스택에 대한 설명을 모두 골라라.

1) 입출력이 한쪽 끝으로만 제한된 리스트이다.

2) head(front)와 tail(rear)의 2개 포인터를 갖고 있다.

3) FIFO(First-In-First-Out)방식으로 동작한다.

4) 배열 구조와 연결된 구조로 구현이 가능하다.

5) 함수 호출 시 복귀 주소를 저장하는데 사용된다.

 

답 : 1,4,5이다.

2,3은 큐에 대한 설명

 

4.4 문자 A,B,C,D,E를 스택에 넣었다가 다시 꺼내 출력하면 어떻게 되는가?

답 : E, D, C, B, A

 

4.5 10, 20, 30, 40, 50을 순서대로 스택에 넣었다가 3개의 항목을 삭제하였다. 남아 있는 항목은?

10과 20

 

4.6 순서가 A,B,C,D로 정해진 입력 자료를 스택에 입력하였다가 출력할 때, 가능한 출력 순서의 결과가 아닌 것은? 단 스택에는 입력 자료의 일부를 저장하고 꺼낼 수도 있다. 예를 들어 A를 저장하고 바로 A를 꺼낼 수 있다. A,B를 모두 저장하고 B를 먼저 꺼내고 A를 꺼낼 수도 있다. 그러나 자료의 입력 순서는 반드시 지켜져야 한다.

1) D,A,B,C         2) A,B,C,D         3)A,B,D,C         4)B,C,D,A

답 : 1번 사유 : D가 먼저 나오려면 A,B,C,D가 다 들어간 상태라 A가 바로 나오는건 슈퍼 불가능

 

4.7 배열 구조(파이썬의 리스트)로 구현한 스택에서 공백상태와 포화상태를 설명하라

비어있는 상태가 공백상태인데 포화상태가 있나?

len(stack)==0인경우가 공백상태

 

4.8 4.2절에서 구현한 스택에서 삽입연산과 삭제연산의 시간 복잡도를 설명

    def push(self,ch):
        self.stack.append(ch)
    def pop(self):
        if not self.emt():
            return self.stack.pop(-1)

시간복잡도는 push와 pop 둘 다 O(1)이다.

 

4.9 4.2절의 스택 클래스에 스택 항목들을 가장 최근에 들어온 순서대로 출력하는 멤버 함수 display2()를 추가하라 단 리스트의 슬라이싱 기법이 아니라 순환적으로 구현하라.

    def display2(self):
        for i in range(self.size()-1,-1,-1):
            print(self.stack[i])

 

4.10 공백 상태의 스택에 총 25번의 push 연산과 10번의 pop연산이 실행되었는데 이 중에 3번은 공백 상태였다. 현재 스택의 항목 수는 어떻게 될까?

15개아님?

 

4.12 이처럼 스택을 사용하는 프로그램이 하는 일?

s=stack()
n=4096

while n>0:
    s.push(n%2)
    n=n//2
while not s.isEmpty():
    print(s.pop())

2진수로 변환해주는 프로그램이다.

 

 

🙆‍♂️스택

---

"""
스택 클래스 Stack
def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환
def size : 스택의 현재 길이를 반환
def clear : 스택 값을 초기화
def push : 입력 요소 ch를 스택에 입력
def pop : 스택의 최상단 값을 삭제
def peek : 스택의 최상단 값 반환
def disply : 스택의 상태를 출력
"""
class Stack:
    def __init__(self):
        self.stack=[]
    def emt(self):
        return len(self.stack)==0
    def size(self):
        return len(self.stack)
    def clear(self):
        self.stack=[]
    def push(self,ch):
        self.stack.append(ch)
    def pop(self):
        if not self.emt():
            return self.stack.pop(-1)
    def peek(self):
        if not self.emt():
            return self.stack[-1]
    def display(self):
        print(self.stack)

 

🙋‍♂️괄호 검사 알고리즘

---

https://naman-develop.tistory.com/177

[자료구조] 스택 - 괄호 검사 알고리즘

 

 

🙋‍♂️ 중위 표현식 후위 표현식으로 변환

---

https://naman-develop.tistory.com/180

[자료구조] 스택 - 중위표현식 후위표현식으로 변환

 

🙋‍♂️ 중위 표현식 후위 표현식으로 변환

---

https://naman-develop.tistory.com/183

[자료구조] 스택 - 미로 탐색