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 shahar
    Aug 17, 2021 at 9:13
  • $\begingroup$ @nirshahar So there is no other way? That's the only way? $\endgroup$
    – Emad
    Aug 17, 2021 at 9:21

1 Answer 1


No, you have to add additional information. There is no way to meet your requirements without adding additional information.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.