Stack

Question 1

Is an Stack Random or Sequential Access?

Answer 1

Sequential

Question 2

A stack is a data structure in which we add elements and remove elements according to LIFO or FIFO?

Answer 2

LIFO. Last in, First out.

Question 3

What is a real world analogy for a Stack?

Answer 3

Washing a stack of dishes. When someone adds a plate to the stack, it will be the first one you grab to wash.

Question 4

What does BigO scoring not account for with the stack?

Answer 4

It’s useful LIFO ability.

Question 5

What are the four fairly standard Stack methods?

Answer 5

Push, Pop, Peek and Contains.

Question 6

How should you implement a Stack in Kotlin?

Answer 6

Use java.util.ArrayDeque.
E.g.
var stack = ArrayDeque()

Question 7

What does the PUSH method do?

Answer 7

It pushes an element onto the top of the Stack.

Question 8

What does the POP method do?

Answer 8

It removes an element form the top of the stack and return the ‘popped’ element.

Question 9

What does the PEAK method do?

Answer 9

It allows you to get the value at the top of the list without actually removing it.

Question 10

What does the CONTAINS method do?

Answer 10

It is used for searching through the Stack. It returns true or false.

Question 11

What is the BigO of ACCESSING an element in a Stack?

Answer 11

O(n) Worst-case the element we need is at the bottom of the stack and we must pop all other elements on top of it before reaching the bottom element.

Question 12

What is the BigO of SEARCHING an element in a Stack?

Answer 12

O(n) Linear Search is required.

Question 13

What is the BigO of INSERTING an element in a Stack?

Answer 13

O(1) Push requires only one operation.

Question 14

What is the BigO of DELETING an element in a Stack?

Answer 14

O(1) Pop requires only one operation.

Question 15

What is an example use case of a Stack

Answer 15

Recursion. Each time a function calls itself it is pushed to the stack and then popped when it completes.
Back button in a web browser.
Undo/Redo.

Question 16

What are the names of the operations for stacks?

Answer 16

The insert operation is usually called “push”
delete is “pop”
retrieve is “peek”

isempty tells us whether the stack is empty
new that creates an empty stack

note: Stacks are inherently tied to the idea of recursion

Question 17

What is a stack?

Answer 17

A stack is a linear container that allows us to
insert, delete and retrieve only at one end.

There is no general find operation

A stack is LIFO (last in, first out)

Question 18

List the area of applications where stack data structure can be used?

Answer 18

Expression evaluation
Backtracking
Memory Management
Function calling and return

Question 19

What is the condition for a stack overflow?

Answer 19

Overflow occurs when top = Maxsize -1

Question 20

Write the steps involved in the insertion and deletion of an element in the stack.

Answer 20

Push:
–Increment the variable top so that it can refer to the next memory allocation
–Copy the item to the at the array index value equal to the top
Repeat step 1 and 2 until stack overflows

Pop:

–Store the topmost element into the an another variable
–Decrement the value of the top
–Return the topmost element

Question 21

Depth first search

Answer 21

Uses a stack to progress to the deepest part of a tree or graph before traversing to other nodes.

Can also be done with recursion