Unit 3: Stacks and Queues - Subjective Questions

A stack is a linear data structure in which insertion and deletion are performed only at one end, called the TOP.

It follows the Last In, First Out (LIFO) principle. If elements , , and are inserted in that order, then is removed first, followed by and .

Basic operations:

• Push: Inserts an element at TOP.
• Pop: Removes and returns the element at TOP.
• Peek: Returns the top element without removing it.
• isEmpty: Checks whether the stack contains no elements.

Applications:

• Managing function calls and recursion through the call stack.
• Implementing undo and redo operations in editors.
• Evaluating arithmetic expressions.
• Supporting backtracking algorithms.

In the array representation, a stack of maximum capacity is stored in a one-dimensional array, such as STACK[0...n-1]. An integer variable TOP identifies the position of the most recently inserted element.

Initialization:

• Set TOP = -1 to represent an empty stack.

Conditions:

• The stack is empty when TOP == -1.
• The stack is full when TOP == n - 1.
• Overflow occurs when a push is attempted while TOP == n - 1.
• Underflow occurs when a pop or peek is attempted while TOP == -1.

Advantages:

• Simple implementation.
• Constant-time access to the top element.
• Good cache locality.

Limitation:

• The maximum size is normally fixed when the array is created, which may cause overflow or unused memory.

A linked stack stores each element in a node containing two fields:

• data: stores the element.
• next: stores the address of the next node.

A pointer named TOP points to the first node, which represents the top of the stack.

Push operation:

1. Allocate a new node.
2. Store the new value in its data field.
3. Set newNode.next = TOP.
4. Set TOP = newNode.

Pop operation:

1. If TOP == NULL, report underflow.
2. Save TOP.data and the address of the top node.
3. Set TOP = TOP.next.
4. Release the removed node.
5. Return the saved value.

Both operations take time. A linked stack grows dynamically, but every element requires extra memory for its link.

Array stack:

• Stores elements in contiguous memory locations.
• Usually has a fixed capacity.
• Can overflow when the allocated array becomes full.
• Requires no pointer field for each element.
• Provides good cache performance.

Linked stack:

• Stores elements in dynamically allocated nodes.
• Can grow until available memory is exhausted.
• Does not require a predetermined capacity.
• Requires additional memory for a link in every node.
• Involves dynamic memory allocation and pointer manipulation.

Common characteristics:

• Both follow the LIFO principle.
• Push, pop, and peek take time.
• Both can suffer underflow when an operation is attempted on an empty stack.

An array stack is suitable when the maximum size is known, while a linked stack is useful when the number of elements changes unpredictably.

Let STACK be an array of capacity , and let TOP contain the index of the current top element.

Algorithm:

1. Check whether TOP == n - 1.
2. If true, report stack overflow and stop.
3. Otherwise, set TOP = TOP + 1.
4. Set STACK[TOP] = ITEM.

Pseudocode:

PUSH(STACK, TOP, n, ITEM)

• if TOP == n - 1: report OVERFLOW
• else:
• TOP = TOP + 1
• STACK[TOP] = ITEM
• return TOP

Only a constant number of comparisons and assignments is performed. Therefore, the time complexity is . The array itself requires space, while the push operation uses auxiliary space.

The pop operation removes and returns the element stored at the top of the stack.

Algorithm:

1. Check whether TOP == -1.
2. If true, report stack underflow because no element can be removed.
3. Otherwise, store STACK[TOP] in ITEM.
4. Set TOP = TOP - 1.
5. Return ITEM and the updated TOP.

Pseudocode:

POP(STACK, TOP)

• if TOP == -1: report UNDERFLOW
• else:
• ITEM = STACK[TOP]
• TOP = TOP - 1
• return ITEM, TOP

The removed array location does not need to be physically erased because decreasing TOP makes it logically inaccessible. The operation takes time and auxiliary space.

Stack traversal means visiting the elements currently stored in the stack. To follow stack order, traversal begins at TOP and proceeds toward index .

Algorithm:

1. If TOP == -1, report that the stack is empty.
2. Initialize i = TOP.
3. Display STACK[i].
4. Decrease i by .
5. Repeat until i < 0.

Pseudocode:

TRAVERSE(STACK, TOP)

• if TOP == -1: report EMPTY
• else:
• for i = TOP down to 0:
• display STACK[i]

For elements, traversal takes time and auxiliary space. Since TOP and the array contents are not modified, the original stack remains unchanged.

Infix notation places an operator between its operands, such as . It depends on precedence rules and parentheses.

Prefix notation, also called Polish notation, places the operator before its operands, such as .

Postfix notation, also called Reverse Polish notation, places the operator after its operands, such as .

For :

• The left subexpression becomes +AB in prefix and AB+ in postfix.
• The right subexpression becomes -CD in prefix and CD- in postfix.
• Combining both with multiplication gives:

Prefix: *+AB-CD

Postfix: AB+CD-*

Prefix and postfix expressions do not require parentheses because the position of each operator determines the evaluation order.

The algorithm uses an operator stack and an output sequence.

Procedure:

1. Scan the infix expression from left to right.
2. Append each operand directly to the output.
3. Push ( onto the stack.
4. On ), pop operators to the output until ( is found; then discard the parenthesis.
5. For an operator, pop operators having higher precedence, or equal precedence when the incoming operator is left-associative.
6. Push the incoming operator.
7. After scanning, pop all remaining operators to the output.

For :

• Multiplication has higher precedence than addition, so is grouped first.
• Division has higher precedence than subtraction, so is grouped first.
• Addition and subtraction are processed from left to right.

Postfix expression: ABC*+DE/-

The conversion takes time and requires auxiliary stack space for an expression of length .

Postfix evaluation algorithm:

1. Scan tokens from left to right.
2. Push every operand onto the stack.
3. When an operator is found, pop the right operand first and the left operand second.
4. Apply the operator as .
5. Push the result back onto the stack.
6. After all tokens are processed, the single remaining value is the answer.

Evaluation:

• Push , , and .
• Apply +: ; push .
• Apply *: ; push .
• Push and .
• Apply /: ; push .
• Apply -: .

Therefore, the value of the postfix expression is .

For tokens, evaluation takes time and space in the worst case.

A prefix expression is evaluated by scanning it from right to left.

Algorithm:

1. Scan tokens from right to left.
2. Push each operand onto the stack.
3. On finding an operator, pop the first value as the left operand and the second value as the right operand.
4. Apply the operator and push the result.
5. The final stack value is the result.

For - * 8 3 / 20 5:

• Evaluate * 8 3: .
• Evaluate / 20 5: .
• Apply the leading subtraction: .

Therefore, the expression evaluates to .

The order of operands must be preserved for non-commutative operators such as subtraction and division. The algorithm takes time and uses stack space in the worst case.

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Insertion occurs at the REAR, while deletion occurs at the FRONT.

In a simple array representation, elements are stored in QUEUE[0...n-1].

Initialization:

• Set FRONT = -1 and REAR = -1.

First insertion:

• Set both FRONT and REAR to .
• Store the item at QUEUE[REAR].

Later insertions:

• Increment REAR and store the new item.

Deletion:

• Remove QUEUE[FRONT] and increment FRONT.
• If the last element is removed, reset both variables to .

A simple linear queue can suffer false overflow when REAR == n - 1 even if deleted positions exist at the beginning. A circular queue solves this limitation.

A linked queue consists of dynamically allocated nodes. Each node contains data and a next pointer.

• FRONT points to the first node, which is removed next.
• REAR points to the last node, after which a new node is inserted.

Insertion:

1. Create a new node with next = NULL.
2. If the queue is empty, set both FRONT and REAR to the new node.
3. Otherwise, set REAR.next to the new node and move REAR to it.

Deletion:

1. If FRONT == NULL, report underflow.
2. Save the node referenced by FRONT.
3. Move FRONT to FRONT.next.
4. If FRONT becomes NULL, also set REAR = NULL.
5. Release the removed node.

Insertion and deletion both take time. The queue grows dynamically but requires extra memory for links.

Let QUEUE[0...n-1] be an array queue initialized with FRONT = REAR = -1.

Insertion algorithm:

1. If REAR == n - 1, report queue overflow.
2. If FRONT == -1, set FRONT = 0 because the first element is being inserted.
3. Set REAR = REAR + 1.
4. Store ITEM in QUEUE[REAR].

Pseudocode:

ENQUEUE(QUEUE, FRONT, REAR, n, ITEM)

• if REAR == n - 1: report OVERFLOW
• else:
• if FRONT == -1: FRONT = 0
• REAR = REAR + 1
• QUEUE[REAR] = ITEM

The operation takes time. In a linear queue, overflow may be reported even when positions before FRONT are unused. This wasted-space problem can be prevented with a circular queue.

Deletion takes place at the FRONT of the queue.

Algorithm:

1. If FRONT == -1 or FRONT > REAR, report underflow.
2. Store QUEUE[FRONT] in ITEM.
3. If FRONT == REAR, the deleted element was the only element; set FRONT = REAR = -1.
4. Otherwise, set FRONT = FRONT + 1.
5. Return ITEM.

Pseudocode:

DEQUEUE(QUEUE, FRONT, REAR)

• if FRONT == -1 or FRONT > REAR: report UNDERFLOW
• ITEM = QUEUE[FRONT]
• if FRONT == REAR: FRONT = REAR = -1
• else: FRONT = FRONT + 1
• return ITEM

Resetting both indices after deleting the last element restores the initial empty state. The deletion operation takes time.

Array queue traversal:

• First check whether FRONT == -1.
• If the queue is not empty, visit QUEUE[i] for every index from FRONT through REAR.
• In a circular queue, advance with until REAR has been visited.

Linked queue traversal:

• Start with a temporary pointer at FRONT.
• Visit the data in the current node.
• Move the pointer to next.
• Repeat until the pointer becomes NULL.

Traversal must not modify FRONT, REAR, or the links; therefore, a temporary index or pointer is used.

If the queue contains elements, both forms of traversal take time. An array traversal uses auxiliary space, and iterative linked traversal also uses auxiliary space.

A linear queue moves FRONT and REAR only toward larger indices. Deleted positions at the beginning cannot normally be reused, causing false overflow. A circular queue treats the array as a ring, so positions following index continue at index .

For an array of size :

Empty condition:

• FRONT == -1.

Full condition:

Insertion:

• If full, report overflow.
• If empty, set FRONT = REAR = 0.
• Otherwise, set .
• Store the new item at QUEUE[REAR].

Deletion:

• If empty, report underflow.
• Remove QUEUE[FRONT].
• If FRONT == REAR, reset both to .
• Otherwise, set .

Both operations take time, while circular organization uses the allocated array more efficiently.

A priority queue is an abstract data type in which every element has an associated priority. Removal is based on priority rather than only on arrival time. Elements with equal priority are commonly served in FIFO order.

Types:

• Max-priority queue: Removes the element with the highest priority or largest key.
• Min-priority queue: Removes the element with the lowest priority or smallest key.

Basic operations:

• Insert an element with its priority.
• Inspect the minimum or maximum priority element.
• Delete the minimum or maximum priority element.
• Check whether the queue is empty.

Implementations:

• Sorted array or list: Inspection and removal can take , but insertion may take .
• Binary heap: Inspection takes , while insertion and deletion take .

Priority queues are used in CPU scheduling, graph algorithms, event simulation, and emergency-service systems.

A deque, or double-ended queue, is a linear data structure that permits operations at both the front and the rear.

General deque operations:

• Insert at front.
• Insert at rear.
• Delete from front.
• Delete from rear.
• Inspect the front or rear element.

Input-restricted deque:

• Insertion is allowed at only one end, usually the rear.
• Deletion is allowed at both ends.

Output-restricted deque:

• Insertion is allowed at both ends.
• Deletion is allowed at only one end, usually the front.

A deque can behave like a stack by inserting and deleting at the same end. It can behave like a queue by inserting at the rear and deleting at the front. Circular arrays and doubly linked lists are common deque implementations.

Let the deque use an array of size with FRONT = REAR = -1 initially.

Empty condition: FRONT == -1.

Full condition:

Insert at front:

• Reject the operation if full.
• If empty, set FRONT = REAR = 0.
• Else if FRONT == 0, set FRONT = n - 1; otherwise decrement FRONT.
• Store the item at DEQUE[FRONT].

Insert at rear:

• Reject the operation if full.
• If empty, initialize both indices to .
• Else set .
• Store the item at DEQUE[REAR].

Delete from front:

• Reject if empty.
• If FRONT == REAR, reset both to ; otherwise set .

Delete from rear:

• Reject if empty.
• If only one element exists, reset both indices.
• Else if REAR == 0, set REAR = n - 1; otherwise decrement REAR.

Each operation takes time.