# Stack Flashcards

1
Q

Is an Stack Random or Sequential Access?

A

Sequential

2
Q

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

A

LIFO. Last in, First out.

3
Q

What is a real world analogy for a Stack?

A

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

4
Q

What does BigO scoring not account for with the stack?

A

It’s useful LIFO ability.

5
Q

What are the four fairly standard Stack methods?

A

Push, Pop, Peek and Contains.

6
Q

How should you implement a Stack in Kotlin?

A

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

7
Q

What does the PUSH method do?

A

It pushes an element onto the top of the Stack.

8
Q

What does the POP method do?

A

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

9
Q

What does the PEAK method do?

A

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

10
Q

What does the CONTAINS method do?

A

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

11
Q

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

A

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.

12
Q

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

A

O(n) Linear Search is required.

13
Q

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

A

O(1) Push requires only one operation.

14
Q

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

A

O(1) Pop requires only one operation.

15
Q

What is an example use case of a Stack

A

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.

16
Q

What are the names of the operations for stacks?

A

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

17
Q

What is a stack?

A

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)

18
Q

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

A

Expression evaluation
Backtracking
Memory Management
Function calling and return

19
Q

What is the condition for a stack overflow?

A

Overflow occurs when top = Maxsize -1

20
Q

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

A

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

21
Q

Depth first search

A

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