Transcript stacksx_queues_and_linked_listsx

Advanced Higher
Computing Science
Stacks Queues and
linked lists
Why do we need data structures?
• How we represent data when solving a problem
should mirror the real world as closely as possible
• Data structures should be what you think about
when first approaching a problem
Are all complex data structures arrays?
• An array is a set of contiguous blocks of memory.
• Resizing an array is a complex and memory
intensive operation
• Storing data in non contiguous blocks makes the
data structure more flexible but more complex
Real world examples: Stacks
• Browser history
• Interrupts
• Blog posts
Real world examples: Stacks
• Undo function
• To do lists
The Stack
• A stack is a 1-dimensional array or list where data
elements can be added or retrieved only from the top
of the stack.
• The terms push and pop refer to adding and removing
items respectively.
• In a stack, a pointer is required to identify the location
of the top of the stack
• A stack is often referred to as a "Last in First Out"
structure
The stack
The interrupt stack:
Run programA
Interrupt event (interrupt1)
Store programA register contents in memory.
Push programA memory location on to stack
Run interrupt1
Interrupt event (Interrupt2)
Store interrupt1 register contents in memory.
Push interrupt 1 memory location on to stack
Run interrupt2
Complete Interrupt2 routine
Pop interrupt1 memory location from stack
Retrieve interrupt1 status and register contents from memory location
Complete interrupt1 routine
interrupt1 complete
Pop programA memory location from stack
Retrieve programA status and register contents from memory location
Continue programA
Implementing a stack
stackPointer is used to keep track of
the top of the stack
max is the maximum number of items
which the stack can hold
stack[] is an array to hold the data
Implementing a stack
CLASS Stack IS {INTEGER stackPointer, INTEGER max, INTEGER stack[]}
METHODS
CONSTRUCTOR Stack(INTEGER size)
DECLARE THIS.stack INITIALLY []*size
DECLARE THIS.stackPointer INITIALLY 0
DECLARE THIS.size INITIALLY size
END CONSTRUCTOR
PROCEDURE Push(INTEGER value)
IF THIS.stackPointer=THIS.size THEN
<stack overflow action>
ELSE
SET THIS.stack[THIS.stackPointer] TO value
SET THIS.stackPointer TO THIS.stackPointer+1
END IF
END PROCEDURE
Implementing a stack
FUNCTION pop() RETURNS INTEGER
IF THIS.stackPointer=0 THEN
<stack underflow action>
ELSE
SET THIS.stackPointer TO THIS.stackPointer -1
RETURN THIS.stack[THIS.stackPointer]
END IF
END FUNCTION
END CLASS
Real world examples: Queues
• Tech Support helplines
Real world examples: Queues
• Scheduled tasks
• Printer queues
The Queue
• A queue is a 1-dimensional array or list, but data
elements are inserted and retrieved at different
ends.
• In a queue two pointers are required: one to point
to the head of the queue and one to point to the
end.
• A queue is a "First in First Out" structure.
The Circular queue
The Circular queue
When the last space in the array is reached the rear
pointer is moved to the start of the array.
What would this queue look like after the following operations?
Leave 6
Join 77
The Circular queue
What would this queue look like after the following operations?
Leave 6
Join 77
Implementing a Circular queue
start is used to keep track of the front of the
queue
rear is used to keep track of the back of the
queue
maxSize is the maximum number of items
which the queue can hold
currentSize is the current number of items
which the queue is holding
queue[] is an array to hold the data
Implementing a circular queue
CLASS Queue IS {INTEGER start, INTEGER rear,
INTEGER currentSize, INTEGER maxSize, ARRAY OF
INTEGER queue}
METHODS
CONSTRUCTOR Queue(INTEGER size)
DECLARE THIS.start INITIALLY 0;
DECLARE THIS.rear INITIALLY 0;
DECLARE THIS.currentSize INITIALLY 0
DECLARE THIS.maxSize INITIALLY size;
DECLARE THIS.queue INITIALLY INTEGER[maxSize]
END CONSTRUCTOR
Implementing a circular queue
PROCEDURE join(INTEGER data)
IF THIS.currentSize = THIS.MaxSize THEN
SEND "Queue Overflow" TO DISPLAY
ELSE
SET THIS.queue[THIS.rear] TO data
SET THIS.rear TO THIS.rear + 1
SET THIS.currentSize TO THIS.currentSize + 1
END IF
IF THIS.rear > THIS.maxSize THEN
SET THIS.rear TO 1
END IF
END PROCEDURE
Implementing a circular queue
FUNCTION leave() RETURNS INTEGER
IF THIS.currentSize = 0 THEN
SEND "Queue Underflow" TO DISPLAY
RETURN 0
ELSE
RETURN THIS.queue[THIS.start]
SET THIS.queue[THIS.start] TO 0
SET THIS.currentSize TO THIS.currentSize - 1
SET THIS.start TO THIS.start + 1
END IF
IF THIS.start > THIS.maxSize THEN
SET THIS.start TO 1
END IF
END FUNCTION
END CLASS
A queue with one pointer
Join 56
Leave 6
A queue with one pointer
queuePointer keeps track of the front of
the queue
size is the maximum number of items which
the queue can hold
queue[] is an array to hold the data
A queue with one pointer
CLASS Queue IS {ARRAY OF INTEGER queue, INTEGER queuePointer,
INTEGER size}
METHODS
CONSTRUCTOR Queue(INTEGER queueSize)
DECLARE THIS. size INITIALLY queueSize
DECLARE THIS.queue INITIALLY [size]
DECLARE THIS.queuePointer INITIALLY 0
END CONSTRUCTOR
A queue with one pointer
PROCEDURE join(INTEGER value)
IF THIS.queuePointer=THIS.size THEN
<queue overflow action>
ELSE
SET THIS.queue[THIS.queuePointer] TO value
SET THIS.queuePointer TO THIS.queuePointer+1
END IF
END PROCEDURE
A queue with one pointer
FUNCTION leave() RETURNS INTEGER
DECLARE result INITIALLY <whatever>
IF THIS.queuePointer=0 THEN
<queue underflow action>
ELSE
SET result TO THIS.queue[0]
FOR i FROM 0 TO THIS.queuePointer-2 DO
SET THIS.queue[i] TO THIS.queue[i+1]
END FOR
SET THIS.queuePointer TO THIS.queuePointer-1
END IF
RETURN result
END FUNCTION
END CLASS
Real world examples: Linked lists
• Road train
• File blocks on disk
Linked Lists
• A linked list is a dynamic data structure, which means that
its size is not fixed
• Each item in a linked list consists of the data and a link to
the memory location of the next item.
• A linked list is very flexible as the order of items in a linked
list can be changed without actually moving any data
around, just the links between them.
File blocks on disk
• Why does this data need to be stored as a dynamic
structure?
• What causes disk fragmentation and why is it a
problem?
• What is done during disk defragmentation?
Linked Lists
• it is not possible to identify a specific item directly using
its index in the way that you can when storing data in
an array.
• To identify the position of an item in a linked list you
have to walk through the list from beginning to end.
• Linked lists can be used to implement queues and
stacks as well as arrays, with the advantage that they
do not need to have a fixed size, avoiding overflow
errors.
Implementing a linked list
Implementing a linked list
CLASS LinkedList IS {INTEGER data, POINTER head, POINTER next}
# POINTER is a link to a memory location#
METHODS
CONSTRUCTOR LinkedList
DECLARE THIS.data INITIALLY 0
DECLARE THIS.head INITIALLY NUL
DECLARE THIS.next INITIALLY NUL
END CONSTRUCTOR
PROCEDURE setupList()
DECLARE THIS.data INTEGER INITIALLY 0
DECLARE THIS.head POINTER INITIALLY NUL
END PROCEDURE
Implementing a linked list
PROCEDURE newNode(INTEGER data, POINTER next POINTER head)
IF THIS.head = NUL THEN
<point head to data>
THIS.next = NUL
ELSE
<check each node in turn until the one pointing to NUL is found>
<point last node to data>
THIS.next = NUL
END IF
END PROCEDURE
Implementing a linked list
PROCEDURE deleteNode(INTEGER data POINTER head)
IF THIS.head = NUL THEN
SEND "List is empty" TO DISPLAY
ELSE IF <head points to data> THEN
<point head to next item in list>
END IF
DECLARE found INITIALLY FALSE
REPEAT <loop through items>
IF
<current item = data> THEN
<Point current item to next item in list>
SET found TO true
END IF
UNTIL <current item pointer> = NUL
IF found = false THEN
SEND "not found" TO DISPLAY
END IF
END PROCEDURE
END CLASS
Using a linked list to implement a
stack or a queue
• Since a linked list is a dynamic structure, a stack can
grow and shrink as items are pushed and popped.
• The stack pointer effectively becomes the last item in
the list
• If a linked list is used to implement a queue, since it is a
dynamic structure, the front and back of the queue are
the last and first items in the list.
• Both structures will require a variable to store the
maximum number of items allowed in the linked list.
Past paper Examples
• 2016 Q2d, Q 3d
• Specimen Paper Q 3a
• Old Advanced Higher 2014 Q4
• Old Advanced Higher 2012 4b
• Old Advanced Higher 2010 Q2
2016 Q2d
The titles of the songs in one of the playlists are exported to a
program for processing using a queue structure. The queue
has been implemented as a 1-D array. The contents of the
queue are shown below:
Use pseudocode to write an algorithm to remove a played
song from the top of the playlist queue.
2016 Q2d
IF front = back THEN
<queue is empty>
ELSE
<play playlist[front]>
SET front TO front-1
END IF
2016 Q3d(i)
The names of the top 10 medal winning teams are held in a stack. Part of
the stack is shown.
The USA wins enough medals to be fourth on the table. Write down the
sequence of stack operations required to produce the new table.
2016 Q3d(i)
1.
2.
3.
4.
5.
6.
Pop Australia,
pop France,
push
USA,
push France,
push Australia
2016 Q3d(ii)
The stack storing the medal winning teams could be implemented
using a linked list.
The diagram below represents a linked list after the first six teams
have been added to the medal table.
Team Russia is to be added to the medal table between Germany
and the USA. Describe how team Russia would be added to the
correct place inthe linked list.
2016 Q3d(ii)
• A new node would be added to store Russia and its pointer
would be set to 241 (team Germany).
• The pointer of the node containing USA would be updated;
instead of storing 241, it would now store the address of the
new node.
Specimen Paper Q 3a
A computerised version of a card game, based on various animals native to
Scotland, is being developed for a website.
During game play, players can take a card from or place a card on a pile of
cards. A stack data structure will represent this pile of cards.
The stack is held in a 1-D array and the last item placed in the stack was
the Golden Eagle. The 1-D array in which the stack is held is shown below:
Specimen Paper Q 3a (i)
An item is added to the stack by “pushing” and
removed by “popping”. Draw the final state of the
stack after the following five operations:
1. Pop
2. Push Loch Ness Monster
3. Pop
4. Pop
5. Push Grouse
Index
Character
0
Ptarmigan
1
Otter
2
Golden Eagle
3
4
Specimen Paper Q 3a (i)
An item is added to the stack by “pushing” and
removed by “popping”. Draw the final state of the
stack after the following five operations:
1. Pop
2. Push Loch Ness Monster
3. Pop
4. Pop
5. Push Grouse
Index
Character
0
Ptarmigan
1
Grouse
2
3
4
Specimen Paper Q 3 (ii & iii)
(ii) Apart from the 1-D array, describe another item of data
required to implement a stack.
A stack pointer (INTEGER) is required to store the index
position of the top of the stack
(iii) When a stack is implemented using a 1-D array, adding a
valid item can cause an execution error.
Explain why an execution error can occur in this situation.
Stack Overflow occurs when the array is full and an attempt
is made to access an index position which does not exist.
Specimen Paper Q 3b (i)
A linked list could have been used rather than a stack
to represent the pile of cards.
(i) The animals Ptarmigan, Otter and Golden Eagle
are entered, in the order given, into a linked list.
Draw this linked list.
Specimen Paper Q 3b (i)
A linked list could have been used rather than a stack
to represent the pile of cards.
(i) The animals Ptarmigan, Otter and Golden Eagle
are entered, in the order given, into a linked list.
Draw this linked list.
Specimen Paper Q 3b (ii)
(ii) Explain why the execution error in part (a) (iii)
would not occur if a linked list is used rather than a
stack.
A linked list is a dynamic structure (items are not
stored contiguously in memory) so the number of
items is not fixed and items can be easily added
2014 Q4
In the early days of hand-held calculators, ‘Postfix’
notation was used to reduce memory access during a
calculation and made use of the stack to evaluate
expressions. Postfix notation avoids the use of
brackets.
The arithmetical expression 6 * (4 + 3)
is written in Postfix notation as 6 4 3 + *
and is then processed, left to right, using a stack.
2014 Q4
2014 Q4
The arithmetical expression 6 * (4 + 3)
is written in Postfix notation as 6 4 3 + *
At the beginning of the process the stack is empty.
The first element input is a 6 and this is pushed onto the stack.
0
1
2
3
4
5
6
Stack pointer
0
6
After the number “4” has been pushed on to the stack, the state of the stack is:
0
1
6
4
2
3
4
5
6
Stack pointer
(a) Explain why the “stack pointer” is needed during stack
operations.
1
2014 Q4
(b) (i) Following the algorithm above, show the state of the stack after the 3 has
been pushed on to the stack.
(ii) Show the contents of the stack, and the value of the stack pointer, after the
algorithm has run to completion.
2014 Q4
(i) Following the algorithm above, show the state of the stack after the 3
has been pushed on to the stack.
ii) Show the contents of the stack, and the value of the stack pointer, after the
algorithm has run to completion.
2014 Q4
(i) Following the algorithm above, show the state of the stack after the 3
has been pushed on to the stack.
0
1
2
6
4
3
3
4
5
6
Stack pointer
2
ii) Show the contents of the stack, and the value of the stack pointer, after the
algorithm has run to completion.
2014 Q4
(i) Following the algorithm above, show the state of the stack after the 3
has been pushed on to the stack.
0
1
2
6
4
3
3
4
5
6
Stack pointer
2
ii) Show the contents of the stack, and the value of the stack pointer, after the
algorithm has run to completion.
0
1
6
7
2
3
4
5
6
Stack pointer
1
2014 Q4
(i) Following the algorithm above, show the state of the stack after the 3
has been pushed on to the stack.
0
1
2
6
4
3
3
4
5
6
Stack pointer
2
ii) Show the contents of the stack, and the value of the stack pointer, after the
algorithm has run to completion.
0
1
6
7
0
1
42
2
3
4
5
6
Stack pointer
1
2
3
4
5
6
Stack pointer
0
2014 Q4
(c) The algorithm above makes use of the “pop”
operation. Use pseudocode to describe the
operation to pop a value from the stack.
(d) Describe one problem that should be checked for
when pushing a value onto a stack.
2014 Q4
c)
IF <stack is empty> THEN
SEND "Stack underflow" TO DISPLAY
ELSE
SET outputValue TO stack[stackPointer]
SEND outputValue TO DISPLAY
SET stackPointer TO stackPointer -1
END IF
d) Stack overflow
2012 4b
A 1-D array with six elements is used to hold the contents of a queue and
the variables front and rear are used to hold the positions of the item
at the front and rear of the queue.
The following lines of code are executed:
MyQ.addtoback(15)
MyQ.addtoback(29)
MyQ.remove
MyQ.addtoback(8)
The following diagram shows that 29 and 8 are in the queue. The number
15 is still present in the 1-D array but is not in the queue.
Index
0
1
2
15
29
8
3
4
5
front 1
rear 2
2012 4b
(i)
State what happens to the variables front and rear when a number is
removed from the queue.
SET front TO front + 1
ii) The state of MyQ shown above is changed by executing these additional
lines of code:
MyQ.addtoback(11)
MyQ.remove
MyQ.addtoback(9)
Draw a diagram that shows the new state of MyQ
Index
0
1
2
3
4
15
29
8
11
9
5
2012 4c
(i) Describe the problem that will arise as items continue to be added
and removed from MyQ.
The end of the array will be reached but there is still room in the array
for items to be placed in the queue
(ii) Describe how the problem in (c)(i) could be solved.
Either use a circular queue where items joining the queue will be
added to the start of the array and the pointer rear will become 1
Or
Reset the array every time an item is removed by shuffling items one
place up
2010 Q2
2010 Q2
(a) Explain why the characters L, E and D have not been
moved to the locations identified by indices 0, 1 and 2
after characters C and A have been processed.
It would be very inefficient to move every character one
place up every time a key is pressed
(b) State the values stored in the variables front and rear
after the characters O and N have been added and a
further three characters removed from the queue.
Front = 5 Back = 6
2010 Q2c
(c) Characters will continue to be added and removed from
the queue held in the 1-D array.
(i) State the problem encountered as characters continue to
be added and removed.
Rear will reach 9 but the queue is not full as there are spaces
at the front of the array.
(ii) Describe how to solve the problem encountered in (i).
The solution would be to wraparound where items are
added at the start of the array.
2010 Q2d
Another data structure used in programming is a stack.
(i) Explain how the operation of a stack data structure
differs from a queue.
In a stack items are popped and pushed at the same
end. In a queue items leave at one end and join at the
other
(ii) Explain why a keyboard buffer does not use a stack
data structure.
Characters would be processed in the wrong order ( last
key pressed processed before earlier characters )