Stacks and Queues Flashcards
Stacks
For stacks
What order is the data inserted in?
Where are insertions and deletions made?
Are last in, first out (LIFO) linear data structures
* In other words, reverse order of insertion!
Can only be accessed at the “top” using push and pop operations
A structure where insertions and deletions are made at the same location in the data structure (on one side).
Stacks
When pushing, what happens if the stack is full?
When popping what happens when the stack is empty?
You cannot push when the stack is full.
You cannot pop an empty stack.
Stacks
What are the other operations (other than pushing and popping) for a stack?
peek: Return the top element without popping.
search: returns the position where ab object is on the stack. (returns -1 if not found)
clear: clears the entire stack.
full: Check is the stack is full
empty: checks if empty
What are the possible stack applications.
Function calls and recursion
Undo and Redo (text editor)
Expressions for parsing
Backtracking (Go back and forth in browsers)
Game (a game that follows stack behaviour)
Stacks
When implementing stacks with arrays, what must the variable point to?
What else do we need to consider?
Must use a variable to point to the top
* Will initially be set to -1, to indicate an empty stack e.g. top = -1
Will have a maximum size
* Unless a resizable array (list) is used
Stacks
For a stack, how will push and pop be implemented with an array
push:
* Increment top and store the element at that position in the array
e.g.
top += 1
array[top] = elementValue
pop:
* Copy the top element in the array to a temporary variable
* Decrement top
e.g.
temp = array[top]
top -= 1
Stacks
When implementing a stack with a linked list, what are some of the advantages over using an array.
How does push and pop work?
Unlike arrays there is no max size.
push: inserts the element at the head of the list.
pop: copy the element at the head of the list, delete the node, then return the element.
Stacks
When using stacks in general, what is the complexity for push and pop?
It is O(1) regardless of whether it is in an array or a linked list.
Queues
What are queues. How does data enter and leave a queue?
How are elements accessed?
They are FIFO. First in, First out.
Elements are accessed at the head and the tail of the list.
Queues
What are the basic operations of a queue?
What happens when you try to enqueue a full queue?
What happens when you try and dequeue from an empty queue?
Enqueue: add an element to the end of the list. You cannot add to a full queue.
Dequeue: delete and return the element at the beginning of the list. You cannot dequeue from an empty queue.
Queue
How are queues implemented using an array?
What indicates an empty queue?
We use two variables to point to the beginning and the end.
* The head index is incremented after dequeuing
* The tail index is incremented before enqueuing
Heda and tail are set to -1 to indicate an empty queue.
Queue
In an queue array implementation how might we enqueue and dequeue.
Enqueue:
If the queue is empty, head and tail = 0.
Otherwise increment tail mod n
tail += 1
tail % n
set array[tail] to element value.
Dequeue:
Store array[head] to a temporary variable.
If only one element in the queue (head == tail), then set head and tail = -1.
Else, increment head mod n
head += 1
head % n
return the value in the temporary value.
Queue
In a queue linked list implementation, how do we enqueue and dequeue?
Insert the element at the tail of the list.
Copy the element at the head of the list, delete and the node, then return the element.
Queues
In general, what is the complexity of enqueue and dequeue.
They are O(1).
Priority Queues
What is a priority queue?
Each element has an associated priority. The smallest value means the highest priority.
