Stacks Questions and Answers

Q: Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record with smallest key present in the stack1) without deleting the corresponding record, and2) without increasing the complexities of the standard stack operations.Which one or more of the following approach(es) can achieve it?

Only keeping, with every record, a pointer to the record with the smallest key below it works.On PUSH, compare the new key with the minimum stored in the current top record and save a pointer to whichever is smaller (the new record itself if it is smaller): O(1). On POP, simply discard the top record; the record beneath already holds the minimum of everything below it. MIN reads the top record's pointer: O(1). No standard operation becomes slower.A single pointer to the minimum fails when the minimum is popped: finding the new minimum then needs a scan of the stack, O(n). A sorted auxiliary array makes PUSH and POP O(n), since an element must be inserted or removed in the middle. A min-heap gives O(1) MIN but makes PUSH and POP O(log n), increasing their complexity.

A stack is a liner data structure in which insertion and deletion of elements are done at only one end, which is known as the top of the stack. Stack is called a last-in, first-out (LIFO) structure because the last element which is added to the stack is the first element that is deleted from the stack.

Top	L
	M
	N
	O
	P
Bottom	Q

Read the above paragraph and answer the following.

Which of the following items will be at the top in the stack after removing three items?

Exam Year(s)

DSSSB TGT - 2023,

Answer: A

O will be at the top. A stack removes items from the top, last in and first out. The stack from top to bottom is L, M, N, O, P, Q. Removing three items takes away L, then M, then N, and O is left at the top. L is the item removed first, N is removed third and P lies below O, so none of them is on top. Elements are added and removed only at the top, so the order of removal is the reverse of the order of addition.

Discuss in Forum

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.

We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record with smallest key present in the stack
1) without deleting the corresponding record, and
2) without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

A.Keep with every record in the stack, a pointer to the record with the smallest key below it.
B.Keep a pointer to the record with the smallest key in the stack.
C.Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
D.Keep a Min-Heap in which the key values of the records in the stack are maintained.

Exam Year(s)

GATE CS - 2025,

Answer: A

Only keeping, with every record, a pointer to the record with the smallest key below it works.

On PUSH, compare the new key with the minimum stored in the current top record and save a pointer to whichever is smaller (the new record itself if it is smaller): O(1). On POP, simply discard the top record; the record beneath already holds the minimum of everything below it. MIN reads the top record's pointer: O(1). No standard operation becomes slower.

A single pointer to the minimum fails when the minimum is popped: finding the new minimum then needs a scan of the stack, O(n). A sorted auxiliary array makes PUSH and POP O(n), since an element must be inserted or removed in the middle. A min-heap gives O(1) MIN but makes PUSH and POP O(log n), increasing their complexity.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Stacks Questions and Answers || Stacks MCQ Questions and Answers || Stacks GK Questions and Answers || Stacks GK MCQ Questions || Stacks Multiple Choice Questions and Answers || Stacks GK || GK on Stacks || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Stacks Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications