04 Stacks and Queues Free Online FlashCards

What does an abstract data type specify?

An abstract data type specifies how data may be accessed and which operations are supported, without requiring a particular implementation.

What access rule does a stack follow?

A stack follows last-in, first-out (LIFO): the most recently inserted item is removed first.

What are the fundamental stack operations?

The fundamental stack operations are push, which adds an item, and pop, which removes and returns the top item.

What are stack underflow and overflow?

Underflow occurs when pop or peek is attempted on an empty stack. Overflow occurs when a fixed-capacity array stack receives a push while full.

What is the time cost of an array-based stack?

With available capacity, array-based push, pop, and peek take O(1) time. Resizing can make one push O(n), but geometric resizing gives amortized O(1) pushes.

Why are linked-list stack push and pop operations O(1)?

A linked-list stack keeps its top at the list head, so push and pop modify only the first node and take O(1) time.

What access rule does a queue follow?

A queue follows first-in, first-out (FIFO): the earliest inserted item is removed first.

Which state variables manage a circular array queue?

A circular array queue uses front for the next item to remove, rear for the next insertion position, and size for the item count.

Why is a circular array better than a naïve array queue?

A circular array avoids shifting remaining elements after dequeue, so enqueue, dequeue, and front can each take O(1) time.

Why should a linked-list queue keep front and rear references?

A linked-list queue should maintain both front and rear references, allowing enqueue and dequeue to take O(1) time.

What must happen after the final linked-list queue dequeue?

After removing the final node, a linked-list queue must set both front and rear to null so the empty state is represented correctly.

Why can a stack support depth-first search?

A stack is suitable for depth-first search because it restores and processes the most recently chosen unfinished path first.