An Abstract Data Type (ADT) defines a data structure by its behaviour (operations and their effects) rather than its implementation. The user only needs to know WHAT the ADT does — not HOW it stores data internally. Two fundamental ADTs: the stack and the queue.
A stack is a LIFO (Last In, First Out) data structure. Think of a stack of plates — you can only add or remove from the top. Elements are pushed onto the top and popped from the top.
| Operation | Description | Time |
|---|---|---|
| push(item) | Add item to the top of the stack | O(1) |
| pop() | Remove and return the top item | O(1) |
| peek() / top() | Return the top item WITHOUT removing it | O(1) |
| isEmpty() | Return True if stack is empty | O(1) |
| isFull() | Return True if stack is at capacity (if bounded) | O(1) |
| size() | Return number of elements in stack | O(1) |
Stack overflow: pushing onto a full stack. Stack underflow: popping from an empty stack. Both must be handled (check isEmpty/isFull before operations). In recursion, stack overflow occurs when recursion depth exceeds the call stack size — every function call uses stack space.
// Stack using an array + top pointer
stack ← [] (empty array, max size MAX)
top ← -1 // -1 = empty
function push(item)
if top = MAX - 1 then
print("Stack overflow!")
else
top ← top + 1
stack[top] ← item
endif
endfunction
function pop()
if top = -1 then
print("Stack underflow!")
else
item ← stack[top]
top ← top - 1
return item
endif
endfunction
function peek()
if top = -1 then return None
return stack[top]
endfunction
function isEmpty()
return top = -1
endfunction
A queue is a FIFO (First In, First Out) data structure. Think of a supermarket queue — people join at the back (enqueue) and are served from the front (dequeue).
| Operation | Description | Time |
|---|---|---|
| enqueue(item) | Add item to the rear (back) of the queue | O(1) |
| dequeue() | Remove and return item from the front | O(1) |
| front() / peek() | Return the front item without removing it | O(1) |
| isEmpty() | Return True if queue is empty | O(1) |
| size() | Return number of elements | O(1) |
A circular queue (ring buffer) uses a fixed-size array with two pointers: front and rear. When the rear reaches the end of the array, it wraps around to index 0. This avoids wasting space from elements removed at the front.
// Circular queue with size MAX
queue ← array of size MAX
front ← 0
rear ← -1
count ← 0
function enqueue(item)
if count = MAX then print("Queue full")
else
rear ← (rear + 1) MOD MAX // wrap around
queue[rear] ← item
count ← count + 1
endif
endfunction
function dequeue()
if count = 0 then print("Queue empty")
else
item ← queue[front]
front ← (front + 1) MOD MAX // wrap around
count ← count - 1
return item
endif
endfunction
A priority queue is a variant where each element has a priority. Higher-priority elements are dequeued before lower-priority ones, regardless of arrival order. Implemented using a heap (O(log n) enqueue/dequeue). Used in Dijkstra's algorithm — always process the unvisited node with smallest distance first.
| Operation | Stack | Queue | Priority Queue (heap) |
|---|---|---|---|
| Insert (push/enqueue) | O(1) | O(1) | O(log n) |
| Remove (pop/dequeue) | O(1) | O(1) | O(log n) |
| Peek/front | O(1) | O(1) | O(1) |
| Search (contains) | O(n) | O(n) | O(n) |
| Size/isEmpty | O(1) | O(1) | O(1) |
Stack and queue operations are all O(1) (constant time) for the core push/pop/enqueue/dequeue operations — because they always add/remove from a fixed end. This is a key advantage over arrays (where inserting at a specific position is O(n)).
rear ← (rear + 1) MOD MAX. Know why circular queues solve the "false full" problem of linear queues — when front pointer moves forward, that space is reused.8 questions · 24 marks · instantly marked
| Term | Definition |
|---|