Stack and Queues

Question 1

A list ADT with the restriction that insert and delete operations can only be performed at one end called the top-of-stack (TOS)

Answer 1

Stack

Question 2

Stack is a list ADT with the restriction that insert and delete operations can only be performed at one end called the _____________

Answer 2

top-of-stack (TOS)

Question 3

Stack follows the __________________ policy

Answer 3

Last In, First Out (LIFO)

Question 4

2 Main Stack Operations

Answer 4

push(x) and pop()

Question 5

Both push and pop operations operate on ________. It is updated after every push or pop

Answer 5

TOS

Question 6

Other stack operations

Answer 6

peek() - return value of TOS
isFull() - checks if stack is full
isEmpty() - checks if stack is empty

Question 7

Happens when you attempt to pop an empty stack

Answer 7

Stack Underflow Error

Question 8

Happens when you attempt to push to a full stack

Answer 8

Stack Overflow Error

Question 9

Initial value of TOS (Static Array Solution)

Answer 9

int top = -1;

Question 10

Push Operation Pseudocode (Static Array)

Answer 10

push(e):

if top < LIMIT -1
top = top + 1
stack[top] = e
else
error “Stack Overflow”

Question 11

Pop Operation Pseudocode (Static Array)

Answer 11

pop():

if top >= 0
top = top-1
return stack[top+1]
else
error “Stack Underflow”

Question 12

Linked List Solution Stack

Answer 12

Normal Linked list, with insertion and deletion at head (TOS)

Question 13

Applications of Stack

Answer 13

a) Balancing open/close symbols in PLs
b) Function calls (Recursion Stack)
c) Postfix expression evaluation

Question 14

A list ADT with the restriction that insert is done at one end of the list and delete is done at the other

Answer 14

Queue

Question 15

Queue follows the ____________________ policy.

Answer 15

First In, First Out (FIFO)

Question 16

Main Queue Operations

Answer 16

Enqueue - add element at tail (rear)
Dequeue - delete at head (front)

Question 17

Happens when attempting to dequeue an empty queue

Answer 17

Queue Underflow

Question 18

Happens when attempting to enqueue to a full queue

Answer 18

Queue Overflow

Question 19

Initial value for head and tail variables in
Circular Array Solution (Queue)

Answer 19

int head = 0;
int tail = 0;

Question 20

Circular Increment and Decrement

Answer 20

Increment : tail = (tail+1)%LIMIT

Question 21

Pseudocode for Enqueue (Circular Array Solution)

Answer 21

enqueue(e):
tail = (tail+1)%LIMIT //Circular Increment

 if tail != head:
       queue[tail] = e;
 else
     error "Queue Overflow"

Question 22

Pseudocode for Dequeue (Circular Array Solution)

Answer 22

dequeue():
if head!=tail
head = (head+1)%LIMIT
return queue[head]
else
error “Queue Underflow”

Question 23

Queue Linked List Solution

Answer 23

Track and Update pointers for head and tail node, and perform insertion on one end and deletion on the other.

Question 24

Queue Applications

Answer 24

CPU Scheduling
Routing
Event Handling