1.4.2 Data structures definitions/info Flashcards
(b) (c)
What is a stack?
A data structure which follows a last in, first out (LIFO) structure
- holds an ordered, linear sequence of items
what is needed to keep track of a stack?
a pointer which points to the top of the stack
what is the operation to add an item to a stack?
push - adds an element to the top of a stack
what is the operation to remove an item from a stack?
pop - removes an element from the top of the stack
what is the peek operation?
returns a copy of the element on the top of the stack without removing it
what are the steps for the push operation?
- check if the stack is full
- add an item by incrementing the pointer by 1 and then inserting the item into the array at the pointer
what are the steps for the pop operation?
- checks if the stack is empty
- store the item at the top of the stack (at the index equal to the pointer)
- reduce the pointer by 1
- return the item
what are the steps for the peek operation?
- return the item at the top of the stack (at the index equal to the pointer)
what other functions can there be for a stack?
is_empty - checks if the stack is empty
is_full - checks if the stack is at maximum capacity when stored in a static structure
what is a static data structure?
a data structure of fixed size
what are the ways a stack can be implemented?
- using a static array
- using a dynamic linked list
what is a queue?
a data structure which follows first in, first out (FIFO) structure
- holds an ordered linear sequence of items
what is the operation to add an item to a queue?
enqueue - adds an element to the queue
what is the operation to remove an item from a queue?
dequeue - removes an element from the front of the queue
what is needed to keep track of a queue?
- a pointer at the front
- a pointer at the back/rear
what other operations can a queue have?
- is_empty - checks if the queue is empty
- is_full - checks if the queue is full
what are the steps for the enqueue operation? (for linear queues)
- check if the queue is full
- increment the back/rear pointer
- add the item to where the back/rear is pointing to
- check if this is the first item to be added to the queue (if the front pointer = -1) and if so, sets the front pointer to 0
what are the steps for the dequeue operation? (for linear queues)
- check if the queue is empty
- store the item at the front of the queue in a variable
- increment the front pointer
- return the item
what is a circular queue?
a queue which reuses the empty slots at the front of the queue when elements are dequeued
how does a circular queue work?
- as items are enqueued, and the rear pointer reaches the last position, it wraps around to point at the start of the array
- as items are dequeued, the front pointer will wrap around until it passes the rear pointer
how is the enqueue operation adjusted for circular queues?
- use an additional check to cycle back to the beginning if there is free space
how is the dequeue operation adjusted for circular queues?
- use an additional check to cycle to the beginning of the queue
what is a priority queue?
a queue where each element in the queue has a priority
when new elements are added into the queue, they are inserted ahead of those with a lower priority and behind those with equal priority.
what is a dynamic data structure?
a data structure where the size can change at any time
