Week 6 Flashcards
True or false, Stacks are last in and first out.
True. They are LIFO linear data structures. (In other words, reverse order of insertion).
True or false, stacks can only be accessed at the top using push and pop operations.
This is true.
What is this data structure?
A structure where insertions and deletions are made at the same location in the data structure. (on one side).
This is a stack.
What are the basic operations of a stack?
Push: Stores an element at the top of the stack (insert)
Pop: remove and return the element at the top of the stack (delete)
Can you pop an empty stack.
No
If the stack has a maximum size, can you push when the stack is full?
You cannot push when the stack is full.
What does the stack operation peek do?
Returns the top element without popping.
What does the stack operation search do?
Returns the position where an object is on the stack.
Returns -1 if not found.
What does the stack operation full do? How about empty?
Checks if the stack is full and checks if the stack is empty.
What does the stack operation clear do?
Clears the entire stack.
What are some applications of stacks?
Function calls and recursion.
Undo and Redo
Expression evaluation
Backtracking
Environment specific modeling
How does a stack look like in an array?
Push: increment the top and store the element at that position in the array.
top +=1
array[top] = value
Pop: Copy the top element in the array to a temporary value and decrement top.
temp = array[top]
top -= 1
What is the difference between a stack in a linked list and in an array?
Unlike arrays, linked lists have no max size.
What is the complexity of time operations for pop and push (regardless of implementation?)
They are O(1)
What are queues analogous to?
It is analogous to lineups at store checkouts. They are FIFO
What are the basic operations of queues?
enqueue: add an element to the end of the list. (add insert).
dequeue: delete and return the element at the beginning of the list. Remove, poll, delete.
If the capacity is max you cannot enqueue. If the queque is empty you cannot dequeue.
What additional operations may queues use?
peek
search
clear
full
empty
How is a queue implemented in an array?
Two variables to point the beginning and the end.
The head index is incremented after dequeuing.
The tail index is incremented before enqueuing.
(Why not the reverse?)
In a queue, where do you add and remove elements from.
You remove from the head and add to the tail.
How do we know that a queue is empty?
The head and tail will be equal. We will set both of them to -1 to indicate an empty queue.
How will the enqueue instruction work in a queue?
If the queue is empty we set the head and tail to 0.
Else, increment tail mod n
* tail += 1
* tail % n
* set array[tail] to element value.
How do we dequeue in an array?
Store array[head] in a temporary variable.
If only one element in the queue(head == tail)
* set head and tail to -1 (indicates empty)
else, Increment head mod n.
* head+= 1
* head%n
* return the value in the temporary variable.
