5.2 Stacks, Queues and Lists Flashcards
What is a dynamic Set M
Manages elements of a changing set M
Stack is LIFO or FIFO?
LIFO
Queue is LIFO or FIFO?
FIFO
How is Boolean Empty() operation implemented using a Stack?
if top == 0 then return true else false
How is Push(key k) operation implemented using a Stack?
top++
A[top] - k
How is key Pop() operation implemented using a Stack?
if Empty() then error
else
top–;
return A[top + 1]
How is key Top() operation implemented using a Stack?
if Empty() then error
else return A[top]
How is a stack created
A = new key[1 … n]
top = 0
What is the time complexity for the 5 operations when using a stack
O(1)
How is a queue created?
A = new key[1 … n]
head = tail = 1
How is the Boolean Empty() operation implemented using a queue
if head == tail them return true
else fals
How is the Enqueue(key k) operation implemented using a queue
A[tail] = k
if tail == A.Length then tail = 1
else tail++
How is the Dequeue operation implemented using a queue
k = A[head]
if head == A.length then head = 1
else head++
return k
How is a list created
head = nil;
How is the ptr Search(key k) operation implemented using a List
x = head
while x != nil and x.key != k
x = x.next
if x = nil then error else return x
How is the ptr Insert(key k) operation implemented using a List
x = new Item()
x.key = k; x.prev = nil; x.next = head
if head != nil then head.prev = x
head = x; return x
What are the complexities for the three operations when implementing using a List
Creating List - O(1)
Search - O(n)
Insert - O(1)
What are the complexities for the 5 operations when implementing using a Queue
O(1)
Why would you use a queue/stack over a list
Simplicity/security. If you don’t want people pulling things out of the middle of your data structure, don’t let them.
