DSA - STACK & QUEUES

Question 1

Define Stack:

Answer 1

Is a Last-In-First-Out abstract data type

Question 2

Define Abstract Data Type

Answer 2

Implements data Structures using other data types

Question 3

What does the command Push do?

Answer 3

Puts value x onto the top of the stack.

Theoretically can push as many values onto a stack, however we will get an exception when memory memory runs out

Question 4

What does the command Pop do?

Answer 4

Removes (sometimes returns) value on top of the stack.

Question 5

What does the command isEmpty() do?

Answer 5

Says whether stack is empty:
- length of stack is 0
- Top pointer is 0
Rises an EmptyStackException ERROR

Question 6

What is the Top END of Stack?

Answer 6

First Element to be executed / completed and where new values are pushed in

Question 7

What is the Bottom End of Stack?

Answer 7

Last Element to be removed/completed

Question 8

What does push(x) followed by is_empty give?

Answer 8

FALSE

Question 9

What does push(x) followed by push() gives?

Answer 9

x

Question 10

What does the command top(stack) do?

Answer 10

Returns the value at top of stack without editing the stack

Question 11

What does the command push(element, Stack)?

Answer 11

Pushes an element on top of chosen stack

Question 12

What does the command pop (stack) do?

Answer 12

Removes & Returns top element of the stack

Question 13

What does EmptyStack do?

Answer 13

returns an empty Stack

Question 14

Why does top at the beginning the ideal scenario for a Stack as a Linked List?

Answer 14

• Inserting & Deleting from the beginning of a linked list is constant:
• push = insert_beg
• pop = delete_beg
  -is_empty = is_empty

Every operations on Stacks takes constant time

Question 15

Why does having top at end is not ideal for a Stack as a Linked List?

Answer 15

• delete_end has a linear time due to having to traverse through the entire list to find the end and delete the node.
• insert_end will be fast

Question 16

How do you Implement Stack as an Array?

Answer 16

stack = new int[MAXSTACK];
stack_size = 0;

Question 17

Why is MAXSTACK useful than using allocate_memory?

Answer 17

MAXSTACK is useful because it allocates memory as pre-requisite before implementing a stack.

Allocate_memory automatically allocates memory but takes time.

Question 18

Where is the bottom in an array Stack?

Answer 18

position 0

Question 19

Where is the top in an array Stack?

Answer 19

position stack_size-1

Question 20

Define Queue:

Answer 20

First-In-First-Out abstract data type, it is a list of values

Question 21

What does enqueue do?

Answer 21

Puts value x at the rear of the queue

Question 22

What does dequeue do?

Answer 22

Takes out a value from front of the queue
WILL RETURN ERROR IF QUEUE IS EMPTY

Question 23

What does is_empty(QUEUE/STACK) do?

Answer 23

Says whether the queue is empty, a queue is empty is End Queue = Head Queue

Question 24

What are the 2 Pointers in the list?

Answer 24

Rear & Front

Question 25

What is EmptyQueue do?

Answer 25

returns an empty queue

Question 26

What does push(element, queue)

Answer 26

pushes an element onto the REAR of the given queue

CAN BE CONFUSING, SO LOOK AT CONTEXT OF PUSH

Question 27

What does top(queue) do?

Answer 27

returns the first element in the queue

Question 28

What does pop(queue) do?

Answer 28

Returns the queue with the front element removed

Question 29

Why is having Front at beginning and Rear at end the Ideal Scenario for Queue as a Linked List?

Answer 29

As long as we use 2 pointers in the head node, one to the first node in the linked list and the second to the end of the linked list, It will take a constant time to dequeue and enqueue items.

HAS FIXED NO. OF STEPS WITHOUT BACK POINTERS AND MORE EFFICENT

Question 30

Why is having REAR at beginning and FRONT at end NOT the Ideal Scenario for Queue as a Linked List?

Answer 30

Can enqueue in constant time however dequeue we require the address of the penultimate node of the list in order to remove the last node and set it to END.

NEED TO TRAVERSE THROUGH WHOLE LINKED LIST , Costing LINEAR TIME

Question 31

Which Data Structure implement queues easier?

Answer 31

ARRAY

Question 32

What is Normal Basic Array Queue Flaw?

Answer 32

Whenever we enqueue we increment rear, this will eventually run out of space. To fix or amend this every time we dequeue we move everything left, which is slow

Question 33

How does a Circular Array based Queue?

Answer 33

• There are 2 pointers Rear & Front that will move Clockwise
• Pointer will move after every enqueue & dequeue
• Dequeue will read and remove current front then increment front by doing front+1%MAXSIZE (Will return the remainder)
• Enqueue put the value at position of Rear then increment Rear by doing Rear+1%MAXSIZE

Question 34

What does front+1%MAXSIZE & Rear+1%MAXSIZE do & Why is it important?

Answer 34

They both return remainders within the range of
[0- (MAXSIZE-1)], Thus allows its circular feature.

EXAMPLE:
IF MAXSIZE = 12
AND Front = 12 & Rear = 18
Enqueue - Rear 18%12 = 6 so puts it in index 6 and Rear becomes 19
Dequeue - Removes item in index 12%12 =0, then Front points to new index which is 13%12 = 1

These all work only when they are empty

Question 35

If Front and Rear are on the same index in Circular List?

Answer 35

The List is either FULL or EMPTY

Question 36

What is Invariant?

Answer 36

A Condition on Code.
- Must always be true during execution of some section of code

Question 37

Why are Invariants important?

Answer 37

They Specify the conditions that must be met and maintained in parts of the code
CAN:
- Communicate Information to the reader of the code
- Both Identify and Debug errors in the code
- Mathematically Prove the program is correct

Question 38

What does DIV do?

Answer 38

Return the Division of 2 Numbers without a Remainder

Question 39

What does MOD do?

Answer 39

Returns the Remainder of 2 Number in Division

Question 40

What is the code to Implement Circular array Queue?

Answer 40

queue = new int [MAXQUEUE];
front = 0;
size = 0;

DON’T USE REAR AS CANNOT DIFFER IF ARRAY IS FULL / EMPTY

Question 41

CODE for is_empty():

Answer 41

boolean is_empty() {
return size ==0;
}

Question 42

CODE for is_full() ;

Answer 42

boolean is_full() {
return size ==MAXQUEUE;
}

Question 43

CODE for Enqueue:

Answer 43

Void enqueue (int val){
if (size == MAXQUEUE) {throw QueueFullException;}
queue[(front+size) MOD MAXQUEUE] = val;
size++;
}

Question 44

CODE for Dequeue:

Answer 44

int dequeue () {
if (size == 0) {throw QueueEmptyException;}
val = queue[front];
front = (front +1) mod MAXQUEUE
size – ;
return val;
}

Question 45

Why do we MOD to get index?

Answer 45

So that the array can wrap around thus upholding its circular property.

Also makes sure that the new value points at the correct index

Question 46

How would you get REAR using Size?

Answer 46

first + size mod MAXQUEUE
- where first is the first non-empty element in the cell in the array

Question 47

Why do we need to check is_full / is_empty?

Answer 47

We need to check if invariance is maintained, otherwise a bug occurs.

Question 48

What is Front range?

Answer 48

0 <= front < MAXQUEUE

Question 49

What is Size Range

Answer 49

0 <= size <= MAXQUEUE