Stack and Queues Flashcards
A list ADT with the restriction that insert and delete operations can only be performed at one end called the top-of-stack (TOS)
Stack
Stack is a list ADT with the restriction that insert and delete operations can only be performed at one end called the _____________
top-of-stack (TOS)
Stack follows the __________________ policy
Last In, First Out (LIFO)
2 Main Stack Operations
push(x) and pop()
Both push and pop operations operate on ________. It is updated after every push or pop
TOS
Other stack operations
peek() - return value of TOS
isFull() - checks if stack is full
isEmpty() - checks if stack is empty
Happens when you attempt to pop an empty stack
Stack Underflow Error
Happens when you attempt to push to a full stack
Stack Overflow Error
Initial value of TOS (Static Array Solution)
int top = -1;
Push Operation Pseudocode (Static Array)
push(e):
if top < LIMIT -1
top = top + 1
stack[top] = e
else
error “Stack Overflow”
Pop Operation Pseudocode (Static Array)
pop():
if top >= 0
top = top-1
return stack[top+1]
else
error “Stack Underflow”
Linked List Solution Stack
Normal Linked list, with insertion and deletion at head (TOS)
Applications of Stack
a) Balancing open/close symbols in PLs
b) Function calls (Recursion Stack)
c) Postfix expression evaluation
A list ADT with the restriction that insert is done at one end of the list and delete is done at the other
Queue
Queue follows the ____________________ policy.
First In, First Out (FIFO)
Main Queue Operations
Enqueue - add element at tail (rear)
Dequeue - delete at head (front)
Happens when attempting to dequeue an empty queue
Queue Underflow
Happens when attempting to enqueue to a full queue
Queue Overflow
Initial value for head and tail variables in
Circular Array Solution (Queue)
int head = 0;
int tail = 0;
Circular Increment and Decrement
Increment : tail = (tail+1)%LIMIT
Pseudocode for Enqueue (Circular Array Solution)
enqueue(e):
tail = (tail+1)%LIMIT //Circular Increment
if tail != head:
queue[tail] = e;
else
error "Queue Overflow"
Pseudocode for Dequeue (Circular Array Solution)
dequeue():
if head!=tail
head = (head+1)%LIMIT
return queue[head]
else
error “Queue Underflow”
Queue Linked List Solution
Track and Update pointers for head and tail node, and perform insertion on one end and deletion on the other.
Queue Applications
CPU Scheduling
Routing
Event Handling
