빈 스택에 다음 연산을 차례로 호출한다. 상태는 왼쪽이 바닥, 오른쪽이 맨 위다.
push(3) → push(7) → peek() → push(1) → pop() → pop() → size()peek()과 pop()이 스택을 다르게 바꾸는 점을 적는다.pop()을 호출하는 경우를 위해 명세가 정해야 하는 것을 적는다.peek()은 7, 첫 pop()은 1, 둘째 pop()은 7, size()는 1이다.peek()은 맨 위 값을 반환하고 스택을 바꾸지 않지만 pop()은 맨 위 값을 반환하며 삭제한다.Python list _items로 스택을 구현한다. 원소가 n = 1,000개 있다. 각 연산은 처음 상태에서 따로 실행한다.
push와 pop에 쓰는 메서드와 비용을 적는다.head를 맨 위로 둔 스택에서 push와 pop의 비용을 적고 순회가 필요 없는 이유를 적는다.push가 Θ(n)이 될 수 있는 경우를 적는다.append(x)와 pop() 모두 상각 Θ(1)이다.insert(0, x)는 기존 원소 1,000개를, pop(0)은 뒤에 남은 999개를 옮긴다. 둘 다 Θ(n)이다.push와 pop이 같은 끝을 사용하기 때문이다.push는 원소를 모두 복사해 Θ(n)이다.여는 괄호는 push, 닫는 괄호는 스택이 비어 있으면 실패하고 아니면 pop, 입력 끝에서 스택이 비어 있으면 성공이다.
(()(()))를 끝까지 읽은 결과를 적는다.(()))(는 몇 번째 기호를 읽을 때 실패하는지와 그 이유를 적는다.((())는 언제 실패가 드러나는지와 그때 스택에 남은 괄호 수를 적는다.([)]처럼 괄호 종류가 섞이면 소괄호만 보는 코드에 무엇을 더해야 하는지 적는다.)다. 앞의 네 기호에서 여는 괄호 두 개가 모두 짝을 이뤄 스택이 비었는데 닫는 괄호를 만났다.([)]는 )를 만날 때 맨 위가 [라 실패한다.오개념 점검: 여는 괄호와 닫는 괄호의 개수가 같다는 것만으로는 짝이 맞는다고 할 수 없다.
(A + B) × C를 후위식으로 바꾼다.6 2 3 + ×를 평가하며 각 단계의 스택을 적는다.9 3 - 2 /를 평가한다.A B + C ×다. 괄호 안의 +는 닫는 괄호에서 출력되고 ×는 입력 끝에서 출력된다.+에서 3, 2를 pop해 5를 push [6, 5] → ×에서 30을 push [30]. 결과는 30이다.-로 9 − 3 = 6, [6, 2]에서 /로 6 / 2 = 3이다.main이 a()를 부르고, a가 b()를 부른 뒤 b가 반환하고, 이어서 a가 c()를 부른다. 각 사건 뒤의 호출 스택(오른쪽이 맨 위)을 적는다.to_str(6, 2)가 재귀로 부르는 호출을 순서대로 적고, 가장 깊은 호출이 반환되는 순간 남아 있는 호출 프레임을 적는다.n이 서로 섞이지 않는 이유를 적는다.b 반환 [main, a] → [main, a, c]다.to_str(6, 2) → to_str(3, 2) → to_str(1, 2)다. to_str(1, 2)가 반환하는 순간 6과 3을 받은 두 호출 프레임이 남아 있다. 결과는 "110"이다.