Difference between revisions of "Stacks"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(→‎Pop)
(→‎Kahoot)
 
(13 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
A stack is a last in, first out data structure that can only have data added or removed from the top.
+
A stack is a '''last in, first out''' data structure. A stack can only have data added or removed from the top. Imagine a stack of plates in a restaurant, you can only take the top plate and you can't grab one from the middle.
−
The stack has limited size and the stack pointed 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.
+
 
 +
The stack has limited size and this must be defined. The '''Stack Pointer''' will always point to the value at the top of the stack. It will start at zero for an empty stack and the maximum value should be equal to the size of the stack.
 +
 
 +
The videos below combine stacks & queues:
 +
 
 +
<youtube>https://www.youtube.com/watch?v=WnjVVJ0kIgQ&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=5</youtube>
 +
 
 +
https://www.youtube.com/watch?v=WnjVVJ0kIgQ&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=5
 +
 
 +
<youtube>https://www.youtube.com/watch?v=1hEK9yWs_cM&index=6&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW</youtube>
 +
 
 +
https://www.youtube.com/watch?v=1hEK9yWs_cM&index=6&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW
 +
 
 
==Check for Full==
 
==Check for Full==
 +
A stack must have a maximum size of the stack defined, this is often called StackMax. This will be used to check if the stack is currently full, it will do this by comparing the stack pointer and the StackMax.
 +
 +
<syntaxhighlight lang=python>
 +
procedure TestFull (ref Stack, ref SP)
 +
begin
 +
if SP = StackMax then
 +
output ‘no room on stack’
 +
else
 +
output ‘room available on stack’
 +
endif
 +
end { TestFull}
 +
</syntaxhighlight>
 +
 
==Check for Empty==
 
==Check for Empty==
 +
Testing for empty only requires the stack pointer, so if the stack pointer is zero the stack is empty.
 +
 +
<syntaxhighlight lang=python>
 +
procedure TestEmpty (ref Stack, ref SP)
 +
begin
 +
if SP = 0 then
 +
output ‘stack is empty’
 +
else
 +
                output ‘stack is not empty’
 +
endif
 +
end {TestEmpty}
 +
</syntaxhighlight>
 +
 
==Push==
 
==Push==
−
When an item is pushed it is added to the top of the stack. if Bill is at value one and Ted is pushed, he would be added to value 2.
+
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.
 +
 
 +
<syntaxhighlight lang=python>
 +
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}
 +
</syntaxhighlight>
  
 
==Pop==
 
==Pop==
−
Using the example from before, if Bob was at value 1 and Bill was at value 2, the value from the top of the stack would be removed. so Bill would be removed, just leaving Bob at value 1.
+
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.
 +
 
 +
<syntaxhighlight lang=python>
 +
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}
 +
</syntaxhighlight>
  
 
==Peek==
 
==Peek==
 +
Allows you to get the value from the top of the stack, without actually popping it. This is achieved by following the same algorithm for a pop, however, the stack pointer is never changed.
 +
 +
Again remember this can only be carried out on a stack that currently contains values, if it is empty it will crash.
 +
 +
<syntaxhighlight lang=python>
 +
procedure TestAndPeek (ref Stack, ref SP)
 +
begin
 +
if SP = 0 then
 +
output ‘stack is empty’
 +
else
 +
DataItem := Stack[SP]
 +
output DataItem
 +
endif
 +
end {TestAndPeek}
 +
</syntaxhighlight>
 +
 +
=='''Quiz'''==
 +
===Question 1===
 +
===Question 2===
 +
===Question 3===
 +
===Question 4===
 +
===Question 5===
 +
===Question 6===
 +
===Question 7===
 +
===Question 8===
 +
===Question 9===
 +
===Question 10===
 +
===Question 11===
 +
===Question 12===

Latest revision as of 07:48, 23 August 2023

A stack is a last in, first out data structure. A stack can only have data added or removed from the top. Imagine a stack of plates in a restaurant, you can only take the top plate and you can't grab one from the middle.

The stack has limited size and this must be defined. The Stack Pointer will always point to the value at the top of the stack. It will start at zero for an empty stack and the maximum value should be equal to the size of the stack.

The videos below combine stacks & queues:

https://www.youtube.com/watch?v=WnjVVJ0kIgQ&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=5

https://www.youtube.com/watch?v=1hEK9yWs_cM&index=6&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW

Check for Full

A stack must have a maximum size of the stack defined, this is often called StackMax. This will be used to check if the stack is currently full, it will do this by comparing the stack pointer and the StackMax. 

procedure TestFull (ref Stack, ref SP)
begin
	if SP = StackMax then
		output ‘no room on stack’
	else
		output ‘room available on stack’
	endif
end { TestFull}

Check for Empty

Testing for empty only requires the stack pointer, so if the stack pointer is zero the stack is empty. 

procedure TestEmpty (ref Stack, ref SP)
begin
	if SP = 0 then
		output ‘stack is empty’
	else
                output ‘stack is not empty’
	endif
end {TestEmpty}

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. 

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. This is achieved by following the same algorithm for a pop, however, the stack pointer is never changed.

Again remember this can only be carried out on a stack that currently contains values, if it is empty it will crash. 

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

Quiz

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Retrieved from ‘http://www.trccompsci.online/mediawiki/index.php?title=Stacks&oldid=8676’