Stacks and Queues Flashcards
stacks
what is a stack
container of objects that are inserted and removed acording to the LIFO principle
stacks
what is the main principle of a stack
Last in First Out
(LIFO)
stacks
elements can only be added and removed from ther stack at the …
top
stacks
a stack is an …… data type
abstract
stacks
name the 5 functions u can do top a stack and what they do
- push - adds item to top of stack
- pop - removes item from the top of stack
- top - returns top element (doesnt remove)
- test for empty - prevent underflow
- test for full - prevent underflow
stacks
example of the use of a stack
undo button
stacks
when is an array implementatio for a stack used
when the size is predictable
stacks
what are the two ways a stack can be implemented
- array
- linked list
stacks
what are the disadvantages of an array implementation for a stack
- limited size
- empty entries waste space
- can be stack overflow
stacks
what are the disadvantages and advantages of an linked list implementation for a stack
- -space used by pointers
- +no stack overflow
- +unlimited size
what is the principle of a queue
the first item inserted is the first to be removed
(FIFO)
queues
what are the two pointers in a queue called and what do they do
- front - keeps track of first element
- rear - keeps track of the last element
queues
how do you add an element to a queue
enqueue
queues
how do u remove an element from a queue
dequeue
queues
write an algorithm to show how a data item is added into a queue
take into account possibility of it being full
- declare max size
- calculate number of elements by size = tail - head
- check if size is less than max size
- if yes, add item to queue
- if no, error msg saying queue is full
