stacks.md

#Data Structures: Stacks

Objectives

• Learn what a stack is
• Learn what a stack overflow is
• Overflow a stack in JS
• Calculate a JS stack size

Variables in JavaScript (and most other programming languages) are stored in two places: stack and heap.

Usually in computer programming:

The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. When the variable is no longer used, it is popped off the stack

Stacks & Heaps: Stacks are attached to threads and Heaps are usually attached to the application

What the heck is a stack?

A stack can be thought of as a literal physical stack or pile. An insertion and deletion of items takes place at one end called top of the stack. Think of it like a pile of books -- You can only take the top item off the stack in order to remove things from it. 

Stacks demonstrate LIFO (Last in, First out). The three operations that can be performed on stacks are 1) push - inserting an item into a stack, 2) pop - deleting an item from the the stack, and 3) stack which displaying the contents of the stack

Looks familiar, right?

What does stack overflow mean??

A stack overflow is an undesirable condition in which a particular computer program tries to use more memory space than the call stack has available. In programming, the call stack is a buffer that stores requests that need to be handled. This type of attack is a variation on the buffer overflow attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular compilers use a shared stack for both data and procedure calls, and do not verify the length of data items. Frequently programmers do not write code to verify the size of data items, either, and when an oversized or undersized data item is copied to the stack, a security breach may occur.

Let's demo a stack

We have a stack with 5 spaces. We are all objects. Let's push 5 objects in! 

If we push 6 objects, what happens?

Let's make a stack in JavaScript in Chrome console

function Stack(){
	return new Array();
}

var stack = new Stack();

stack.push('e')
stack.push('m')
stack.push('o')
stack.push('s')
stack.push('e')
stack.push('w')
stack.push('a')

Let's use the stack return the data in reverse.

stack.join('').split('').reverse().join('')

or 

stack.reverse()

Let's pop it out

stack.pop()
stack.pop()

console.log(stack)

##Examples of Stacks

Undo/Redo in MS Word
Evaluating expressions (e.g. X = (A + B) * (C + D))
Local variables

A call stack is a stack data structure that stores information about active subroutines of a computer program.

Examples:

Execution stack
Control stack
Run-time stack
Machine stack

Let's try and calculate the size of the stack

var counter = 0;
try {
  function foo() {
    counter += 1;
    foo();
  }
  foo();
} catch(e) {
  console.error(e);
  console.log('counter =', counter);
}

Let's try and increase the size of each frame and see what happens

var counter = 0;
try {
  function foo() {
    var local = 1;
    counter += 1;
    foo();
  }
  foo();
} catch(e) {
  console.error(e);
  console.log('counter =', counter);
}

Let's work backwards:

• We know that an integer in JavaScript takes 8 bytes.

• Use a variable N to symbolize the size of single stack frame

• We can calculate the maximum stack size

    20,961 * N = 17,967 * (N + 8)
    2,994N = 143,736
    N = 48 bytes per frame
    48 bytes per frame * 20,961 (total frames) = 1,006,152 bytes
  

Let's calculate this to MegaBytes and we can see that Calculator

1.006152 MB is our stack frame size 

Sources:

JavaScript: Stacks & Heaps

Stacks & Heaps