Stacks & Queues:

1. What is a stack?

Stack in simple terms can be explained as a heap of objects placed one over the other. In a stack, the last placed object can be accessed first, and it is said to be “Last-in-First- out” (LIFO) method.

2. What are operations on stack ADT?

§ push: pushing is to add elements on the top of the stack.

§ pop: popping is removing elements from the top of the stack.

§ isfull: isfull finds out whether the stack is full or not

§ isempty: isempty finds out whether the stack is empty or not

§ create: to create an empty stack

§ top: to return the top element of a stack.

3. What are the applications of Stack?

• Verifying Parenthesis matching

• To convert from infix to postfix

• To evaluate postfix expression

• Used in recursion

• Keeping track of function calls

• Computer applications that use undo features

4. What are queues?

A queue is a linear data structure in which elements are added at the “rear” and deleted from the “front”.

5. What are operations on queue ADT?

§ qstore: adding elements at the end of a queue.

§ qdelete: removing elements from the front of the queue.

§ isfull: isfull finds out whether the queue is full

§ isempty: isempty finds out whether the queue is empty

§ create: to create an empty queue

§ first: to return the first element of a queue

§ last: to return the last element of a queue

6. What are the applications of queue?

• Printing using the computer

• Reservation system

• Computer networks

• Railroad car rearrangement, wire routing

7. What are different types of queues?

Queue can be of four types:

1. Simple Queue

2. Circular Queue

3. Priority Queue

4. Dequeue (Double Ended queue)

8. What is a circular queue?

A circular queue is a queue in which all nodes are treated circular such that the first node follows the last node.

9. What is a priority queue?

A priority queue is a queue that contains items that have some preset priority. When an element has to be removed from a priority queue, the item with the highest priority is removed first.

10. What is a double-ended queue?

In dequeue(double ended queue) Insertion and Deletion occur at both the ends i.e. front and rear of the queue.

11. Explain the differences between Stacks and Queues

Stacks	Queues
Stack is a heap of elements placed one over the other	Queue is a set of elements placed one after the other
Stack mechanism is known as Last In First Out (LIFO)	Queue mechanism is known as First In First Out (FIFO)
Stack is mainly characterized by “top” which refers to its top element.	Queue is mainly characterized by “front” and rear, which refers to its first and last elements.
Both insertion and deletion occur at the same end i.e. at the top.	Insertion and deletion occur at two different ends i.e. insertion at rear and deletion at front.
If there is no value at the top, stack is said to be empty.	If front=rear, queue is said to be empty.
The common terms associated with stack are : push, pop, top, isfull, isempty.	The common terms associated with queue are: qinsert, qdelete, front, rear, isfull, isempty.
Stack can be implemented using both arrays and linked lists.	Queue also can be implemented using both arrays and linked lists.
This has no sub types	It has sub types such as: simple queue, circular queue, double-ended queue, priority queue.