DSA - STACK & QUEUES Flashcards
Define Stack:
Is a Last-In-First-Out abstract data type
Define Abstract Data Type
Implements data Structures using other data types
What does the command Push do?
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
What does the command Pop do?
Removes (sometimes returns) value on top of the stack.
What does the command isEmpty() do?
Says whether stack is empty:
- length of stack is 0
- Top pointer is 0
Rises an EmptyStackException ERROR
What is the Top END of Stack?
First Element to be executed / completed and where new values are pushed in
What is the Bottom End of Stack?
Last Element to be removed/completed
What does push(x) followed by is_empty give?
FALSE
What does push(x) followed by push() gives?
x
What does the command top(stack) do?
Returns the value at top of stack without editing the stack
What does the command push(element, Stack)?
Pushes an element on top of chosen stack
What does the command pop (stack) do?
Removes & Returns top element of the stack
What does EmptyStack do?
returns an empty Stack
Why does top at the beginning the ideal scenario for a Stack as a Linked List?
- 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
Why does having top at end is not ideal for a Stack as a Linked List?
- 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 do you Implement Stack as an Array?
stack = new int[MAXSTACK];
stack_size = 0;
Why is MAXSTACK useful than using allocate_memory?
MAXSTACK is useful because it allocates memory as pre-requisite before implementing a stack.
Allocate_memory automatically allocates memory but takes time.
Where is the bottom in an array Stack?
position 0
Where is the top in an array Stack?
position stack_size-1
Define Queue:
First-In-First-Out abstract data type, it is a list of values
What does enqueue do?
Puts value x at the rear of the queue
What does dequeue do?
Takes out a value from front of the queue
WILL RETURN ERROR IF QUEUE IS EMPTY
What does is_empty(QUEUE/STACK) do?
Says whether the queue is empty, a queue is empty is End Queue = Head Queue
What are the 2 Pointers in the list?
Rear & Front
What is EmptyQueue do?
returns an empty queue
What does push(element, queue)
pushes an element onto the REAR of the given queue
CAN BE CONFUSING, SO LOOK AT CONTEXT OF PUSH
What does top(queue) do?
returns the first element in the queue
What does pop(queue) do?
Returns the queue with the front element removed
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
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
Which Data Structure implement queues easier?
ARRAY
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
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
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
If Front and Rear are on the same index in Circular List?
The List is either FULL or EMPTY
What is Invariant?
A Condition on Code.
- Must always be true during execution of some section of code
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
What does DIV do?
Return the Division of 2 Numbers without a Remainder
What does MOD do?
Returns the Remainder of 2 Number in Division
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
CODE for is_empty():
boolean is_empty() {
return size ==0;
}
CODE for is_full() ;
boolean is_full() {
return size ==MAXQUEUE;
}
CODE for Enqueue:
Void enqueue (int val){
if (size == MAXQUEUE) {throw QueueFullException;}
queue[(front+size) MOD MAXQUEUE] = val;
size++;
}
CODE for Dequeue:
int dequeue () {
if (size == 0) {throw QueueEmptyException;}
val = queue[front];
front = (front +1) mod MAXQUEUE
size – ;
return val;
}
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
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
Why do we need to check is_full / is_empty?
We need to check if invariance is maintained, otherwise a bug occurs.
What is Front range?
0 <= front < MAXQUEUE
What is Size Range
0 <= size <= MAXQUEUE
