this video is part three of our five part series overviewing data structures in this video we look at stacks and cues a stack is a data structure that is essential for the operation of the computer items are pushed onto the top of the stack when they are added to it and popped off the top when they're deleted from it it's also possible to peek at the top item without deleting it you can imagine a stack of coins the coin can only be added to or removed from the top of the stack the stack is therefore known as a last in first out or lifo data structure the last item to be pushed onto the stack must also be the first item to be popped off a stack has a stack pointer that always points to the node at the top any attempt to push an item onto a full stack is called a stack overflow conversely any attempt to pop an item off an empty stack is called a stack underflow both of these potential outcomes should be considered before attempting to push or pop an item a stack is often implemented using an array but can also be created using object orientated techniques stacks are used by processors to track the flow of programs when a procedure or function subroutine is called it changes the value of the program counter to the first instruction of the subroutine when the subroutine ends the processor must return the program counter to its previous value we can achieve this using a stack which allows subroutine calls to be nested so this program begins at line 13. when the program hits line 14 is to jump off to the procedure calculate pay the return address for line 15 is pushed onto the stack the pointer moves to point to this item now at the top of the stack the program continues until it hits line 10 it now needs to jump off to the procedure subtract deductions the return address for line 11 is pushed onto the stack and the pointer moves to point to this item now at the top of the stack the program continues until it hits line five it's reached the end of a procedure and needs to know where to return to the return address is popped off the top of the stack once again the pointer moves to the new top of the stack the program continues until it hits line 12. it's reached the end of another procedure and again needs to know where to go the return address is popped off the top of the stack and the pointer is updated to indicate the stack is empty local variables are also held on the stack which is why their values are lost when a subroutine ends they're popped off the stack interrupts can also be handled in the stack in the same way stacks are used for performing depth-first searches on graph data structures and we'll look at that in a later video keeping track of user inputs for undo operations backtracking algorithms for example pathfinding for maze solutions and evaluating mathematical expressions about brackets using a shunting yard algorithm and reverse polish notation so there are three really important operations you need to be aware of that can be performed on a stack pushing popping and peaking and we'll look at those in a later video a queue is a linear data structure items are enqueued at the back of the queue and dequeued from the front of the queue again just like the stack it's also possible to peak this time at the front item without deleting it you could imagine a supermarket checkout the customers at the front of the queue are served first and new customers join at the back by nature a queue system also can allow for people to jump the queue in the field of computer science we call this a priority queue in special circumstances new items can also join at the front of the queue so in this sense the queue is known as a first in first out or fifo structure a cue has a back pointer that always points to the last item sometimes also called the tail pointer it also has a front pointer that always points to the first item sometimes also known as a head pointer an attempt to encue an item in a full queue is called a q overflow meanwhile trying to dequeue an item from an empty queue is called a queue underflow again both of these outcomes should be considered before attempting to enqueue or dq an item cues could be implemented using an array or indeed using object orientated techniques however implementing a cue using array can create a problem since both the back and front pointers are moving in the same direction as items are added and removed from the queue the array can quickly run out of space one solution is to cycle the back pointer to the front of the array when it reaches the end this implementation is called a circular queue and this is not necessary if we're implementing a cue using object orientated techniques an array with a circular queue is ideal if you want to restrict the number of items and have a known memory footprint it's particularly useful in games design where the number of sprites on the screen affects the frame rate by only spawning sprites up to the limit of the queue a stable frame rate can be achieved queues can also be used for process scheduling transferring data between processors and printer spooling performing breadth-first searches on a graph data structure there are three basic operations you need to be aware of for a queue enqueuing an item dequeuing an item and peaking and we'll look at these in more detail in our second video on stacks and queues having watched this video you should be able to answer the following key question how do stacks and queues work and what are they used for we know that getting to grips with data structures and all the algorithms associated with them is a very tricky area of the course and so we've produced a book called essential algorithms for a level computer science that's available on amazon it covers all the data structures you need to know about along with the algorithms you need to perform on them and it covers all the exam boards we overview each data structure discussing its typical applications and the operations you can perform on it we provide a qr code that jumps off to a useful page of additional resources we then take each data structure and the algorithms you need to perform and present them first in simple structured english then in a diagrammatic format then in pseudocode and finally we present you with fully coded algorithms which you need to cover on the data structures in both python and vb so you can actually code them up and practice them yourselves you