1.4.2 Data structures definitions/info
No description yet. This curated deck is ready for daily study.
Card preview (24)
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