Skip to content

In Queue the dequeue should be O(1) complexity #942

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
fahimfaisaal opened this issue Mar 22, 2022 · 8 comments
Closed

In Queue the dequeue should be O(1) complexity #942

fahimfaisaal opened this issue Mar 22, 2022 · 8 comments
Assignees
@fahimfaisaal
Labels
algorithm Adds or improves an algorithm beginner-friendly Easy to implement code quality Code quality improvement performance Performance improvement

Comments

@fahimfaisaal
Copy link
Contributor

From this Queue implementation I believe the Operation is O(n) cause the complexity of Array.prototype.shift methods is O(n), see
@raklaptudirm raklaptudirm added feature Adds a new feature help wanted Needs to be worked on algorithm Adds or improves an algorithm labels Mar 22, 2022
@ayDavidGitHere
Copy link
Contributor

ayDavidGitHere commented Mar 24, 2022 •
edited
Loading

Dequeue on queue works on a O(n) complexity.
To achieve dequeue on O(1) use linked-lists.

https://github.com/ayDavidGitHere/Javascript/tree/master/Data-Structures/Linked-List

@fahimfaisaal
Copy link
Contributor Author

Yeah, I see.

@appgurueu
Copy link
Collaborator

The queue should be implemented using linked lists. The current implementation is clearly suboptimal for no good reason.

@raklaptudirm
Copy link
Member

@fahimfaisaal Are you working on this issue?

@fahimfaisaal
Copy link
Contributor Author

Yep.. I'll send pr soon.

@appgurueu appgurueu added performance Performance improvement beginner-friendly Easy to implement and removed feature Adds a new feature labels May 4, 2022
@raklaptudirm
Copy link
Member

raklaptudirm commented May 6, 2022 •
edited
Loading

@fahimfaisaal You still haven't sent a pull request. Are you working on this, or should I put this issue up for grabs?

@fahimfaisaal fahimfaisaal mentioned this issue May 6, 2022
Merged
12 tasks
@fahimfaisaal
Copy link
Contributor Author

@raklaptudirm I apologize for my latency.

@raklaptudirm
Copy link
Member

#1005 fixes this.

@raklaptudirm raklaptudirm added code quality Code quality improvement and removed help wanted Needs to be worked on labels May 6, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@fahimfaisaal fahimfaisaal

Labels
algorithm Adds or improves an algorithm beginner-friendly Easy to implement code quality Code quality improvement performance Performance improvement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@appgurueu @fahimfaisaal @raklaptudirm @ayDavidGitHere