DSA - STACK & QUEUES Flashcards

1
Q

Define Stack:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define Abstract Data Type

A

Implements data Structures using other data types

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does the command Push do?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What does the command Pop do?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does the command isEmpty() do?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the Top END of Stack?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the Bottom End of Stack?

A

Last Element to be removed/completed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does push(x) followed by is_empty give?

A

FALSE

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does the command top(stack) do?

A

Returns the value at top of stack without editing the stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does the command push(element, Stack)?

A

Pushes an element on top of chosen stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does the command pop (stack) do?

A

Removes & Returns top element of the stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does EmptyStack do?

A

returns an empty Stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How do you Implement Stack as an Array?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Why is MAXSTACK useful than using allocate_memory?

A

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

Allocate_memory automatically allocates memory but takes time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Where is the bottom in an array Stack?

A

position 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Where is the top in an array Stack?

A

position stack_size-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Define Queue:

A

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

21
Q

What does enqueue do?

A

Puts value x at the rear of the queue

22
Q

What does dequeue do?

A

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

23
Q

What does is_empty(QUEUE/STACK) do?

A

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

24
Q

What are the 2 Pointers in the list?

A

Rear & Front

25
What is EmptyQueue do?
returns an empty queue
26
What does push(element, queue)
pushes an element onto the REAR of the given queue CAN BE CONFUSING, SO LOOK AT CONTEXT OF PUSH
27
What does top(queue) do?
returns the first element in the queue
28
What does pop(queue) do?
Returns the queue with the front element removed
29
Why is having Front at beginning and Rear at end the Ideal Scenario for Queue as a Linked List?
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
30
Why is having REAR at beginning and FRONT at end NOT the Ideal Scenario for Queue as a Linked List?
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
31
Which Data Structure implement queues easier?
ARRAY
32
What is Normal Basic Array Queue Flaw?
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
33
How does a Circular Array based Queue?
- 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
34
What does front+1%MAXSIZE & Rear+1%MAXSIZE do & Why is it important?
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
35
If Front and Rear are on the same index in Circular List?
The List is either FULL or EMPTY
36
What is Invariant?
A Condition on Code. - Must always be true during execution of some section of code
37
Why are Invariants important?
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
38
What does DIV do?
Return the Division of 2 Numbers without a Remainder
39
What does MOD do?
Returns the Remainder of 2 Number in Division
40
What is the code to Implement Circular array Queue?
queue = new int [MAXQUEUE]; front = 0; size = 0; DON'T USE REAR AS CANNOT DIFFER IF ARRAY IS FULL / EMPTY
41
CODE for is_empty():
boolean is_empty() { return size ==0; }
42
CODE for is_full() ;
boolean is_full() { return size ==MAXQUEUE; }
43
CODE for Enqueue:
Void enqueue (int val){ if (size == MAXQUEUE) {throw QueueFullException;} queue[(front+size) MOD MAXQUEUE] = val; size++; }
44
CODE for Dequeue:
int dequeue () { if (size == 0) {throw QueueEmptyException;} val = queue[front]; front = (front +1) mod MAXQUEUE size -- ; return val; }
45
Why do we MOD to get index?
So that the array can wrap around thus upholding its circular property. Also makes sure that the new value points at the correct index
46
How would you get REAR using Size?
first + size mod MAXQUEUE - where first is the first non-empty element in the cell in the array
47
Why do we need to check is_full / is_empty?
We need to check if invariance is maintained, otherwise a bug occurs.
48
What is Front range?
0 <= front < MAXQUEUE
49
What is Size Range
0 <= size <= MAXQUEUE