Lists, Stacks, and Queues Flashcards
What is one of the most common data structures?
Lists
What is another word for lists?
Collections
What is one example of a linear list?
Arrays
Which data structure uses Last in, First out?
Stack
When is a stack in an overflow state?
When there is no more space and you attempt to push another value on it
What is the operation called when adding an element to a stack?
Push
What are the 4 stack operations?
- Push()
- Pop()
- Peek()
- isFull()
What is an example of a stack in the real world?
Undo operations
What are the elements in a linked list called?
Nodes
What do the nodes in a stack contain?
A pointer to “next” and some data
What is it called when you move from one node to another using the “next” pointer?
Link Hopping or Pointer Hopping
What is the first node in a linked list called?
Head
What is the last node in a linked list called?
Tail
Do stacks have a pointer to previous?
No
What does the tail of a singly linked list point to?
Nothing (nullptr)
What way is a singly linked list traversed?
From head to tail
What is the difference between a singly linked list and a doubly linked list?
Pointer called “previous”
How does a queue grow?
Add to it’s tail
How does a queue shrink?
Remove from it’s head
Which data structure is First in, First out?
Queue
What operation adds an element to a queue?
Enqueue
What operation removes an element from a queue?
Dequeue
How many pointers does a circular queue require?
3
What is the best data structure for a queue?
Doubly linked list
What is a priority queue?
Adding a rule to prioritize something other than FIFO
Which way of adding elements to a priority queue leads to slower removal?
Added in the order they come in
Which way of adding elements leads to slower additions?
Adding based on priority