Stacks · 스택
What is an ADT?
- An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
- You use the operations and ignore how it is built inside.
- A stack, a queue, and a linked list are all ADTs.
ADT란 무엇인가?
- 추상 데이터 구조(ADT)는 데이터의 모음과 그에 대한 일련의 연산으로 정의됩니다.
- 연산을 사용하고 내부 구동 방식은 무시합니다.
- 스택, 큐, 연결リスト는 모두 ADT입니다.
A stack is LIFO
- A stack is Last In, First Out (LIFO).
- The last item you add is the first one you take off.
- Think of a stack of plates: you take the top plate first.
스택은 LIFO입니다
- 스택은 후입 선출(LIFO)입니다.
- 가장 최근에 추가한 항목이 가장 먼저 꺼내집니다.
- 접시 쌓이를 생각해보십시오: 맨 위 접시를 먼저 꺼냅니다.
push and pop with a list
- We can build a stack from a Python list.
- push =
stack.append(x)— add to the end (the top). - pop =
stack.pop()— remove and return the end (the top).
목록을 이용한 push 및 pop
- Python list를 사용하여 스택을 구현할 수 있습니다.
- push =
stack.append(x)— 끝부분(맨 위)에 추가합니다. - pop =
stack.pop()— 끝부분(맨 위)을 제거하고 반환합니다.
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek and empty
- peek at the top without removing it:
stack[-1]. - A stack is empty when
len(stack) == 0. - Popping an empty stack is an error, so check first.
peek과 empty
- 제거하지 않고 맨 위를 확인합니다:
stack[-1]. - 스택이 비어 있을 때는
len(stack) == 0입니다. - 비어 있는 스택에서 pop하는 것은 오류이므로, 먼저 확인해야 합니다.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
캐미지아 가위코드에서
- 시험에서는 배열과
top포인터(인덱스)를 사용하여 스택을 만듭니다.
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
Common mistakes
- A stack is last-in, first-out: push to the top, pop from the top.
- Check it is not empty before you pop.
흔한 실수
- 스택은 후입 선출입니다: 맨 위에 push하고, 맨 위에서 pop합니다.
- pop하기 전에 비어 있지 않은지 확인하십시오.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
이제 직접 해보기
- 스택으로 list를 사용하십시오(
append로 push,pop로 제거). - Answer 확인 버튼을 눌러 코드를 테스트하세요.
A stack is LIFO · 스택은 LIFO입니다
A stack pushes and pops at one end — last in, first out. · 스택은 한쪽 끝에서만 삽입(push)과 제거(pop)가 이루어지며, 이는 '후입 선출(Last In, First Out)' 원리입니다.
Start with an empty stack. Push 1, then 2, then 3. Then pop once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].) · 빈 스타트 시작합니다. push하여 1, 2, 3을 순서대로 넣으세요. 이후 pop을 한 번 수행하여 제거된 값을 top에 저장합니다. (top은 3이어야 하며 스타트는 [1, 2]이어야 합니다.)
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Use a stack to reverse the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].) · 스택을 사용하여 리스트 items을 역순으로 만드세요. 모든 요소를 스타트에 push한 후, 모두 pop하여 result에 담습니다. (result은 [3, 2, 1]이어야 합니다.)
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write top(stack) that returns the top item (the last one) without removing it. If the stack is empty, return None. · top(stack)을 작성하여 제거하지 않고 최상단 요소(마지막으로 들어간 값)를 반환하세요. 스타트가 비어 있다면 None을 반환합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.