Stack.md (1943B)
1 # Stack 2 3 CS202 L14 / CS303 Ch 1 4 5 **Definition:** This is a data structure that uses the lifo approach where you add to the top and remove from the top of the struct. 6 7 push: add to stack 8 9 peek: get top element. This can also be implemented by doing pop then pushing the result. 10 11 pop: remove from top 12 13 This can be implemented as a [SinglyLinkedList](SinglyLinkedList.md) 14 15 See [Queue](Queue.md) for information about the fifo implementation. 16 17 --- 18 19 # ASM Stack 20 21 **Source:** Performance Aware Programming 22 23 "The Stack" in ASM 24 25 The stack is a region of memory allocated to the task of storing relatively small amounts of scoped variables. Additionally, the stack grows downwards in terms of memory addresses. 26 27 In 8086, somewhere early on in the program there will be an instruction like `mov sp 40000` which will set the stack pointer to the logical bottom of the stack (note, this grows by decrementing the address). 28 29 Then to push to the stack we may do something like this: 30 31 ```asm 32 sub sp, -2 33 mov [sp], ax 34 ``` 35 36 And to pop from the stack we may: 37 38 ```asm 39 mov ax, [sp] 40 add sp, 2 41 ``` 42 43 This is one way, bad but illustrative, to do this. The other way is as follows: 44 45 ```asm 46 push ax 47 ``` 48 49 ```asm 50 pop ax 51 ``` 52 53 This is often used with functions, and either the function or calling code could push / pop. 54 55 To store the IP register so functions may return from where they're called from we can do this: 56 57 ```asm 58 call interesting_function 59 ``` 60 61 This will push the IP to the stack and then jump. 62 63 To pop the IP register we may use: 64 65 ```asm 66 ret 67 ``` 68 69 ## Calling Conventions 70 71 Pushing registers to the stack introduces the concept of "calling conventions" which dictate who performs what operations. 72 73 There are also conventions about how to pass parameters and how to return parameters. These are arbitrarily defined, but must be agreed upon. 74 75 This is also where the idea of an "ABI" comes from. Executables and shared libraries have to adhere to these conventions.