스택,stack

LIFO (last-in-first-out)

Topics
top = top of stack, top-of-stack, 'tos'
(easy, del ok, 배열,array로 구현되는 stack의 index 얘기?)
tos 값은 empty stack에 대해선 −1. 스택 초기화 때 이 값이 정해짐.
push할 때, tos가 증가한 다음, stack[tos]에 값이 대입.
pop할 때, stack[tos]가 return_value이며, tos는 감소.
bottom

Actions
  • create() or initialize()
  • push(x) or add(x)
  • pop() or remove()
  • peek() or top() - top에 있는 것을
  • get length/size
  • is_full() (Weiss C)
  • dispose_stack() or free_stack() - array 구현에서, stack_array와, stack_array에 대한 포인터/tos/stack_size를 담고 있는 관리용 구조체를 free. (Weiss C, del ok)
  • make_null() or discard()? - array 구현에서, tos에 -1을 대입. (Weiss C, del ok)

위에서
입력은 push, 출력은 pop

한쪽만 열려 있는 큐,queue로 볼 수 있음
일반화하면 데크,deque

에러,error or 예외,exception
  • overflow - bounded_stack의 경우, 정해진 크기를 초과하면 array로 구현되었을 경우 array_bound를 overflow하는... tbw
  • underflow - 스택이 비어 있을 때 pop()이 호출되면... chk
이건 각각 다음과 equiv.
  • a push on a full stack
  • a pop on an empty stack

기타 구현시 ... topics
stack_size - bound?
element_type - 원소,element 타입,type
구현 시 자료구조,data_structure를 ...
Sub:
bounded_stack https://xlinux.nist.gov/dads/HTML/boundedstack.html - 크기가 정해진.
stack_overflow (writing) Wiki:StackOverflow https://everything2.com/title/stack overflow
stack_underflow https://everything2.com/title/stack underflow
call_stack // 이건 컴퓨터구조 쪽
WpEn:Call_stack
호출,call시 parameter/argument passing을 위한 공간으로 보통 레지스터,register, 스택, 혹은 둘의 조합을 사용함. 이 셋 외의 예외가 있나? QQQ
스택프레임,stack_frame - writing; Google:stack.frame // 이건 컴퓨터구조 쪽
WpEn:Stack_frame redir to WpEn:Call_stack#STACK-FRAME (2023-12-22)
스택기계,stack_machine - writing; Google:stack.machine // 이건 pure/theoretical CS쪽 .... 이런식으로 여기 Sub들을 나중에 분류해야 함.
Stackless, Stackless Python → 파이썬,Python
spaghetti_stack and cactus_stack
https://xlinux.nist.gov/dads/HTML/cactusstack.html
Wiki:SpaghettiStack
WpEn:Parent_pointer_tree
WpJa:スパゲッティスタック
unwinding_the_stack ... or stack_unwinding ?
Wiki:UnwindingTheStack
Google:unwinding stack
스택포인터,stack_pointer - writing; Google:stack.pointer
stack_smashing (writing)
security쪽 주제, 공격의 일종.
Wiki:StackSmashing
... Google:Stack Smashing
stack_trace
디버깅,debugging에서/디버깅을 위해, 나오는 출력?
WtEn:stack_trace
WpEn:Stack_trace
https://wiki.osdev.org/Stack_Trace
...Google:stack.trace
stack-oriented_programming w - is a 프로그래밍패러다임,programming_paradigm
Rel 스택기계,stack_machine stack-based_language
stack-based_language w
Rel 스택기계,stack_machine stack-oriented_programming
stack-based_memory_allocation
stack-based memory allocation (SBMA)
WpEn:Stack-based_memory_allocation
Cmp: heap-based_memory_allocation (HBMA) ... 힙,heap esp 힙메모리,heap_memory
Up: 메모리할당,memory_allocation

Uses: / rel.

후위표기법,postfix_notation postfix_notation aka RPN - 을 계산하는 것은 stack으로 구현하면 편한데, tbw.
대충 적자면
피연산자,operand가 나오면 (숫자 등)
연산자,operator가 나오면 (+, /, * 등)
단항연산자,unary_opeartor - tbw
이항연산자,binary_operator가 나오면 (이항연산,binary_operation이면) 두 개를 stack에서 pop하여, 계산하고, 결과 하나를 push

infix_notation 식,expression을 postfix_notation 식으로 변환하는 것도 stack으로 구현하는데,
이 때는 연산자 스택에 (, ) - 괄호,parenthesis도 들어가며
연산자의 precedence - operator_precedence - 가 숫자로 정해져 있어야 한다



data struc. 보다는 comp arch 얘기 - 메모리,memory 구조/layout(메모리배치,memory_layout - w)관련된
https://wiki.osdev.org/Stack
그러고보니 저쪽에서 말하는 걸 여기서 분리한다면, (힙,heap도 똑같은 문제가 있음 - computer memory의 영역과 data structure에서 다른 의미로 동일한 표현이 쓰이는) 좋은 pagename scheme? TBD, 그 전엔 일단 section 나누어서.

Up: 자료구조,data_structure and ADT
리스트,list의 일종.