Master Stacks and Queues: A Comprehensive Guide for Computer Science MSc Students

Question 1

What is the fundamental difference between a stack and a queue?

Accepted Answer

Stacks adhere to First-In-Last-Out (FILO) while queues follow First-In-First-Out (FIFO)

Answer

Queues adhere to FILO while stacks follow FIFO

Answer

Stacks store elements linearly, while queues store elements circularly

Answer

Queues store elements linearly, while stacks store elements circularly

Question 2

What purpose does a sentinel node serve in a queue?

Accepted Answer

Marks the queue's end

Answer

Enhances search performance

Answer

Reduces memory consumption

Answer

Increases algorithm complexity

Question 3

Explain the difference between an empty stack and an empty queue:

Accepted Answer

An empty stack has a null top pointer, while an empty queue has two null pointers (front and rear).

Answer

An empty queue has a null top pointer, while an empty stack has two null pointers (front and rear).

Answer

An empty stack has a front pointer pointing to null, while an empty queue has a rear pointer pointing to null.

Answer

An empty queue has a front pointer pointing to null, while an empty stack has a rear pointer pointing to null.

Question 4

Which property is NOT characteristic of stacks?

Accepted Answer

Insertion and removal from any position

Answer

Last-In, First-Out (LIFO)

Answer

Restricted element access to the top item

Answer

Dynamic resizing

Question 5

What is the time complexity of the enqueue operation in a queue?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 6

In text editors, which data structure is employed to implement undo/redo functionality?

Accepted Answer

Stack

Answer

Queue

Answer

Array

Answer

LinkedList

Question 7

How do circular queues differ from regular queues?

Accepted Answer

Circular queues allow elements to wrap around to the front when the end is reached

Answer

Circular queues have a fixed size

Answer

Regular queues can store elements anywhere in memory

Answer

Circular queues are more efficient for large datasets

Question 8

Which algorithm utilizes the stack data structure?

Accepted Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Dijkstra's algorithm

Answer

Floyd-Warshall algorithm

Question 9

Which of the following is NOT a potential drawback of using stacks?

Accepted Answer

Simplicity of implementation

Answer

Limited access to elements

Answer

Risk of stack overflow

Answer

Inefficiency for large datasets

Question 10

How can a queue be implemented using a stack?

Accepted Answer

Employing two stacks: one for enqueue and one for dequeue

Answer

Utilizing recursion to reverse the order of elements in the stack

Answer

Creating a circular buffer for storing elements

Answer

Adding a new head node to the stack for each enqueue operation

Question 11

What is the main difference between a deque and a queue?

Accepted Answer

A deque allows insertion and deletion at both ends, while a queue only allows at one end

Answer

A queue supports priority-based retrieval, while a deque does not

Answer

A deque has a fixed size, while a queue can grow dynamically

Answer

Queues are implemented using arrays, while deques use linked lists

Question 12

Which sorting algorithm employs stacks?

Accepted Answer

Quicksort

Answer

Bubble sort

Answer

Selection sort

Answer

Merge sort

Question 13

What is the time complexity of a push operation in a stack implemented using a linked list?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 14

What is the primary difference between a stack and a queue?

Accepted Answer

Stacks follow LIFO, while queues follow FIFO

Answer

Queues are implemented using arrays, while stacks are implemented using linked lists

Answer

Stacks are used for function calls, while queues are used for message passing

Answer

Queues are unbounded, while stacks have a fixed size

Question 15

Which of the following is a real-world example of a queue?

Accepted Answer

A line of people waiting for a bus

Answer

A stack of books on a desk

Answer

A binary tree

Answer

A hash table

Question 16

What is the difference between a priority queue and a regular queue?

Accepted Answer

Priority queues assign priorities to elements

Answer

Regular queues are implemented using arrays, while priority queues are implemented using linked lists

Answer

Priority queues are used for scheduling, while regular queues are used for message passing

Answer

Regular queues have a maximum size, while priority queues can grow indefinitely

Question 17

What is the time complexity of a pop operation in a stack implemented using an array?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 18

What is the time complexity for adding an element to a queue using an array?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 19

What is the advantage of using a priority queue over a typical queue?

Accepted Answer

Prioritizes elements based on a key

Answer

Faster insertion and deletion

Answer

Supports simultaneous access

Answer

Reduces memory usage

Question 20

Which structure is employed to perform a breadth-first search (BFS) of a graph?

Accepted Answer

Queue

Answer

Stack

Answer

Linked list

Answer

Array

Question 21

How does a deque differ from a regular queue?

Accepted Answer

A deque allows insertion and deletion from both ends

Answer

A deque has a set size

Answer

A deque can store various data types

Answer

A deque is inherently faster than a queue

Question 22

What is a key difference between stacks and queues?

Accepted Answer

Stacks allow access only to the top element.

Answer

Queues allow insertions at any position.

Answer

Queues have no memory limitations.

Question 23

Which of the following operations is NOT supported by a stack data structure?

Accepted Answer

Accessing a specific element in the middle of the stack

Answer

Checking if the stack is empty

Answer

Popping the top element from the stack

Answer

Pushing an element to the top of the stack

Question 24

A data structure that follows the 'last-in-first-out' (LIFO) principle is known as a:

Accepted Answer

Stack

Answer

Binary search tree

Answer

Linked list

Answer

Queue

Question 25

Consider a queue implemented using an array. What is the time complexity of the 'dequeue' operation in this implementation?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Question 26

Which of the following is NOT a fundamental property of a queue?

Accepted Answer

Elements can be accessed directly by their position

Answer

Queues are commonly used in resource management and simulations

Answer

Elements are processed in a first-in-first-out (FIFO) manner

Answer

Queues can be implemented using both arrays and linked lists

Question 27

What happens when an attempt is made to 'push' an element into a full stack?

Accepted Answer

A stack overflow exception is typically generated

Answer

The stack is automatically expanded to accommodate the new element

Answer

The top element of the stack is overwritten with the new element

Answer

The element is discarded and the stack remains unchanged

Question 28

What is the primary advantage of using a circular array to implement a queue?

Accepted Answer

Elimination of the need to shift elements during dequeue operations

Answer

Reduced memory consumption

Answer

Improved scalability

Answer

Faster insertion and deletion operations

Question 29

Which of the following data structures follows the Last-In-First-Out (LIFO) principle where the last element added is the first one to be removed?

Accepted Answer

Stack

Answer

LinkedList

Answer

Queue

Answer

Array

Question 30

In a queue, which operation retrieves and removes the element that has been waiting the longest?

Accepted Answer

Dequeue()

Answer

Size()

Answer

Enqueue()

Answer

Peek()

Question 31

What is the time complexity of determining if a stack is empty?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Question 32

Which real-world application typically utilizes a stack data structure?

Accepted Answer

Function calls

Answer

Graph traversal

Answer

Database management

Answer

File handling

Question 33

Which advantage does a circular queue offer over a linear queue?

Accepted Answer

Reduced memory waste due to its ability to reuse memory space

Answer

Faster enqueue operations

Answer

Simpler implementation

Answer

Improved cache locality

Question 34

When implementing a stack using a linked list, what potential disadvantage arises?

Accepted Answer

Slower performance compared to an array-based implementation due to the overhead of node manipulation

Answer

Difficulty in maintaining the LIFO order

Answer

Increased memory usage

Question 35

In a priority queue, what is the time complexity of retrieving the element with the highest priority?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Question 36

Which data structure is most appropriate for implementing the 'back' button functionality in a web browser?

Accepted Answer

Stack

Answer

Hash Table

Answer

Queue

Answer

Priority Queue