There are two problems in CLRS about implementing stacks and queues with singly linked lists. I know the solutions, I know how STACK-EMPTY and PUSH and POP and QUEUE-EMPTY and ENQUEUE and DEQUEUE are defined. But can we define STACK-FULL and QUEUE-FULL with worst-case $\Theta(1)$ time? One idea is to set a counter and increment or decrement it whenever we add or delete elements but I don't want to use some extra information or add something to the problem. I just want to use the information (like attributes) relevant to singly linked lists only.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ You have to add this additional information. Its not even a lot of information, and its pretty standard to keep it even in practical implementations $\endgroup$– nir shaharAug 17, 2021 at 9:13
-
$\begingroup$ @nirshahar So there is no other way? That's the only way? $\endgroup$– EmadAug 17, 2021 at 9:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No, you have to add additional information. There is no way to meet your requirements without adding additional information.
