Day 2 - CPSC 2120

May 12, 2016
===============================================================================


Based off the answer to the problem below...

11+12+13+...+(n+5)=(n+5)(n+6)/2 - 10(11)/2

1+2+3+...+n=n(n+1)/2

1+2+...+10+11+...+n+(n+1)+(n+2)+(n+3)+(n+4)+(n+5) = (n+5)(n+6)/2

24+27+30+33+36+...+3n+6 = 3[8+9+10+11+12+...+(n+2)] = 3[(n+2)(n+3)/2 - 7(8)/2] 

We use the original formula and subtract the difference between the original
formula.

19. 128G

22. 2Y

24. Powers of Ten, working with exponents


STACKS


STACK OPERATIONS

push
pop
isempty

Implementations: Vectors, arrays, linked lists

Arrays are a STORAGE STRUCTURE, NOT A DATA STRUCTURE

isempty - if the stack is empty
pop - pop top item off the stack
push - push item on the stack
top - look at the top item on the stack
 
ADT - Abstract Data Type

Implementing a Stack:

Arrays are more efficient to use than Vectors

popping a stack will take the top item and then adjust the top to point to the
item below it.  

Using an array

top


| |3 
| |2  <- STACK
| |1
|_|0


PUSH(3) PUTS 3 ON 0, PUSH(4) PUTS 4 ON 1
POP RETURNS THE 4, THEN ADJUSTS THE TOP TO POINT TO 0


void push(int value)
{
	if stack isFull() == false
	{
		top++;
		stack.index[top] = value;
	}
}

int pop()
{
	if stack.isEmpty == false
	{
		temp = stack.index[top];
		top--;
	}
	return temp;
}

***AFTER IT IS POPPED, IT IS IGNORED FROM A STACK, OVERWRITTEN AFTER PUSHED

int top()
{
	if stack.isEmpty() == false
	{
		temp = stack.index[top];
	}
	return top;
}


bool isEmpty()
{
	return (top == -1);
}

bool isFull()
{
	return (top == 999);
}

***Review infix to postfix, postfix to quadruple