Stacks

A stack is a last in, first out data structure that can only have data added or removed from the top. The stack has limited size and the stack pointer will always point to the value at the top of the stack. An empty stack thus has a stack pointer value of 0. You can only push an item if the stack is not full. You can only pop an item if the stack is not empty.

Push

When an item is pushed it is added to the top of the stack. The stack pointer points to the item at the top of the stack, so the stack pointer is incremented and then the data item is stored in that location of the stack. remember this can only be carried out if the stack is not currently full.

Algorithm

procedure TestAndPush (ref Stack, ref SP)
begin
	if SP = StackMax then
		output ‘no room on stack’
	else
		input DataItem
		SP := SP + 1
		Stack[SP] : = DataItem
	endif
end { TestAndPush}

Pop

Pop will remove the top item from the stack. You will need to store the item at the top of the stack (location of stack pointer), and then decrement the stack pointer by 1. The item may not be deleted it will just be overwritten the next time that location is used.

Remember a pop can only be performed if the stack is not currently empty.

procedure TestAndPop (ref Stack, ref SP)
begin
	if SP = 0 then
		output ‘stack is empty’
	else
		DataItem := Stack[SP]
		SP := SP – 1
		output DataItem
	endif
end {TestAndPop}

Peek

Allows you to get the value from the top of the stack, without actually popping it.