Week 6

Question 1

True or false, Stacks are last in and first out.

Answer 1

True. They are LIFO linear data structures. (In other words, reverse order of insertion).

Question 2

True or false, stacks can only be accessed at the top using push and pop operations.

Answer 2

This is true.

Question 3

What is this data structure?

A structure where insertions and deletions are made at the same location in the data structure. (on one side).

Answer 3

This is a stack.

Question 4

What are the basic operations of a stack?

Answer 4

Push: Stores an element at the top of the stack (insert)

Pop: remove and return the element at the top of the stack (delete)

Question 5

Can you pop an empty stack.

Answer 5

No

Question 6

If the stack has a maximum size, can you push when the stack is full?

Answer 6

You cannot push when the stack is full.

Question 7

What does the stack operation peek do?

Answer 7

Returns the top element without popping.

Question 8

What does the stack operation search do?

Answer 8

Returns the position where an object is on the stack.

Returns -1 if not found.

Question 9

What does the stack operation full do? How about empty?

Answer 9

Checks if the stack is full and checks if the stack is empty.

Question 9

What does the stack operation clear do?

Answer 9

Clears the entire stack.

Question 10

What are some applications of stacks?

Answer 10

Function calls and recursion.
Undo and Redo
Expression evaluation
Backtracking
Environment specific modeling

Question 11

How does a stack look like in an array?

Answer 11

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

Question 12

What is the difference between a stack in a linked list and in an array?

Answer 12

Unlike arrays, linked lists have no max size.

Question 13

What is the complexity of time operations for pop and push (regardless of implementation?)

Answer 13

They are O(1)

Question 14

What are queues analogous to?

Answer 14

It is analogous to lineups at store checkouts. They are FIFO

Question 15

What are the basic operations of queues?

Answer 15

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.

Question 16

What additional operations may queues use?

Answer 16

peek
search
clear
full
empty

Question 17

How is a queue implemented in an array?

Answer 17

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?)

Question 18

In a queue, where do you add and remove elements from.

Answer 18

You remove from the head and add to the tail.

Question 19

How do we know that a queue is empty?

Answer 19

The head and tail will be equal. We will set both of them to -1 to indicate an empty queue.

Question 20

How will the enqueue instruction work in a queue?

Answer 20

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.

Question 21

How do we dequeue in an array?

Answer 21

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.