Stacks:
- Last in first out
- The most recent piece of data added to the list is the first piece of data to be removed.
- These are good for linear data
- These operate on a LIFO data structure (Last in, First Out)
- Add data from the top and remove from the top (Pancake stack on a plate, the last on the plate: Last cooked, is the first eaten!)
- Adding data to the stack is called Pushing
- Removing data from the stack is called Popping
- These terms are used with the Little Man computer
- Stacks are implemented using an array
- A stack within computers memory system is implemented using pointers.
- Pointers are only used to located the top of the stack
- Stack pointers use a base 0 number system.
- Pushing or popping always takes place at the top of the stack
- If you have a pop instruction the stack pointer moves by -1
- If you have a push instruction the stack pointer moves by +1
- Errors can occur at the bottom or the top of the stack;
- if the stack is full and you try to push another piece of data there will be a stack overflow error
- if the stack is empty and you try to pop another piece of data there will be an error
Queues:
- First in first out
- The most recent piece of data to the queue is the last piece of data to be taken out
- There are two pointers:
- One to monitor the back of the queue where data is added
- One for the front of the queue where data will be removed from
- When a queue is empty the two pointers have the same value.
- The data within a queue does not physically move forward in the queue (this is because it will be inefficient), instead the two pointers are used to denote the front (data removed) and back (data added) of the queue, and these pointers move.
- The pointers are designated ranges so they know where to move.
- These are a circular data structure- unlike stacks.
- The end pointer can be 'before' the start pointer, but as the queue is a circular data structure it will read from the start, then go back to the beginning to read to the end point
No comments:
Post a Comment