EMC 2C Stacks and Queues

What are the main operations of a stack?

• insert, delete, view

• enqueue, dequeue, front

• The main operations of a stack are push, pop, and peek.

• add, remove, top

How do you implement a queue using an array?

• Implementing a queue with linked lists instead of arrays.

• Using a stack to manage elements in a last-in-first-out manner.

• A queue can be implemented using an array by maintaining 'front' and 'rear' pointers to manage the addition and removal of elements.

• Using a single pointer to track the current position in the array.

What is the time complexity of push and pop operations in a stack?

• O(n^2)

• O(n)

• O(1)

• O(log n)

Describe a real-world application of stacks.

• Data encryption techniques

• Web browser history management.

• Task scheduling

• File storage management

What is the difference between a stack and a queue?

• Both stack and queue use LIFO.

• A stack uses FIFO, while a queue uses LIFO.

• A stack can only hold integers, while a queue can hold any data type.

• A stack uses LIFO, while a queue uses FIFO.

What is a circular queue and how does it differ from a regular queue?

• A circular queue is a linear structure that does not connect the ends.

• A circular queue is a queue that connects the end back to the front, allowing for efficient use of space, unlike a regular queue which can become inefficient with space.

• A circular queue is a type of stack that allows for last-in-first-out access.

• A circular queue is a queue that only allows adding elements at the front.

List the applications of queues in computer science.

• Data encryption methods

• Image rendering algorithms

• Applications of queues include task scheduling, print job management, CPU scheduling, breadth-first search, and request handling in web servers.

• File compression techniques

Explain how a stack can be used to reverse a string.

• A stack can reverse a string by removing characters from the end only.

• A stack can only store integers, not characters.

• Reversing a string requires sorting the characters alphabetically.

• A stack can reverse a string by pushing each character onto the stack and then popping them off to get the characters in reverse order.

What are the advantages of using a circular queue?

• Increased complexity in implementation

• Higher memory usage compared to linear queues

• Slower access time for elements

• Advantages of using a circular queue include efficient space utilization, constant time complexity for operations, and elimination of shifting elements.

How do you check if a given expression has balanced parentheses using a stack?

• Replace all parentheses with asterisks and check the length.

• Count the number of parentheses and check if they are even.

• Use a queue to store the parentheses and check for matches.

• Use a stack to track opening parentheses and ensure they are matched by closing parentheses.