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.
-
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
1 Answer
No, you have to add additional information. There is no way to meet your requirements without adding additional information.