Stacks

like singly linked lists, stacks are a data structure that can only see what comes immediately next. Think of the stack like a stack of dishes after a meal, ready for the wash... or even in the cupboards ready for a meal! Would you lift up the entire stack of dishes and grab a plate from the bottom to work with? No, we'd take from the top so as not to drop any plates, but also because it's more efficient that moving the whole stack without working on it. Handling things in this order is referred to as "LIFO", Last In First Out. Or FILO--same words, different order.

With LIFO in mind, don't get confused by the terms push and pop. With stacks, push and pop both work on the TOP of the stack. I guess that makes sense because that is the functional end; so think of it that way. PUSH adds a a node to the TOP of the stack, and POP removes it. These operations are O(1) because regardless how big and ugly stack mountain may be it doesn't take any extra time to drop something or take anything off the top of it.Another word we should know is to PEEK. This is how to look at just the TOP. If a stack is empty and your don't take a PEEK at it before you begin, you'll get a "null reference error". That makes sense.

How to PUSH

1. Create a new node, or have a node ready to add.
2. Point the "next" property of that node, to the existing TOP node.
3. Don't forget to reassign the title of TOP from the old top to the new top.

Here's a pseudo code for that because you need more exposure, you aren't great at it yet:

ALGORITHM Push(node)
//INPUT <-- Node to add
// OUTPUT <-- none

	node.Next <-- Top
	Top <-- node

How to POP

1. Dethrone TOP and give that node a new temporary reference, like TEMP.
2. You many now crown the next node, new TOP! so that means our original .next is the new TOP.
3. Change the next property of the node formerly known as top, to null.
4. Return that node, who is currently known as temp.

Here's some pseudo code for pop because look! You are already getting better at this! WOOT!

ALGORITHM Pop()
// INPUT <-- No input
/ OUTPUT <-- Top Node of stack

	Node temp <-- Top
	Top <-- Top.Next
	temp.Next <-- null
	return temp

How to Peek

If you don't like being barked at, always peek before you pop. You can't pop if there's nothing to pop, right? IF you do this you'll get a NullExceptionError. BOO! So, here is what you should do:

ALGORITHM Peek()
// INPUT <-- none
// OUTPUT <-- Node of top of stack

	return Top

• you can traverse the stack by using a while loop, while(stack.pop())

• You can also use while (peek()) @ 10:25am

Don't Forget the QUEUES

A queue is a thing that polite British people do to get something that is in fairly popular demand. It's a line. And because it is so polite and orderly it runs in a FIFO, First In First Out, manner. When a new chap, or node, enters the line, this is called ENQUEUE, and since he's the newest and there's nobody behind him, his .next value is going to be null, and you can call him REAR, since that is where he is. Meanwhile, the fellow-node at the head of the line, whom we will loving refer to as FRONT, is waiting to DEQUEUE. That is when nodes are removed from the line. At some point we will all dequeue. Just like with the stacks, you can PEEK on the queue to see who is first in line. Also, as with stacks, you will get barked a nullExceptionError should you dequeue when hoone is there.

Here is what a QUEUE looks like in case you were wondering. It is totally not a stack. nobody is flopped on top of somebody else. These aren't pancakes! They're lovely gentleman grocery shoppers, waiting to checkout:

How to enQueue

Leave this to me, I'm British, I know how to queue.
-Arthur Dent

Adding a caboose is an O(1) action because slapping one on the end of 1 or 1 million is still slapping one on the end--since we don't need to traverse to get there. Here we go:

1. Get your node ready
2. Point the current caboose, or REAR, to the value of your new node, instead of null. Rear.next = new node!
3. Now that we're safely added, we can move the title of REAR to the newly enqueued node.

Here is some sweet pseudo code for that move:

ALGORITHM Enqueue(node)
// INPUT <-- Node to add to queue
// OUTPUT <-- none

	Rear.Next <-- node
	Rear <-- node

How to DEqueue

1. Create a new reference called temp and make it point wherever front it pointing.
2. Now we take front and point it to temp.next, or the node that is second in the queue.
3. with the new Front safely established we can break bonds with the queue. temp.next = null;
4. Return that node, temp, to the trash!

Here is some pseudo code for the sick move:

ALGORITHM Dequeue()

	Node temp <-- Front
	Front <-- Front.Next
	temp.Next <-- null
	
	return temp;

How to Peek-at-queue

much like peeking at stacks:

ALGORITHM Peek()

	return Front

source: codefellows