Can You Improve the Time Complexity of Building a Queue with Stacks?

  • Thread starter Thread starter Shackman
  • Start date Start date
  • Tags Tags
    Building Queue
AI Thread Summary
The discussion centers around implementing a queue using stacks, focusing on achieving the fastest possible performance. The proposed method involves using two stacks: items are pushed onto the first stack during enqueue operations. For dequeue operations, all items must be popped from the first stack and pushed onto the second stack, resulting in a time complexity of O(n^2) in the worst case. Suggestions for improvement include exploring alternative methods to reduce the time complexity and questioning the validity of using a queue of stack pointers, with one stack per object. The conversation emphasizes the need for a more efficient solution to manage the enqueue and dequeue operations effectively.
Shackman
Messages
22
Reaction score
2
Hello, I'm tasked with building a queue from as many stacks as I'd like, trying to get the fastest implementation possible. The best I can think of is using two stacks and as you enqueue items you push them on the first stack stack, but every time you want to dequeue if there are n items enqueue'd you have to pop each one individually and push them onto the second stack for n-1 times, then pop the first item enqueue'd and return it. Then any dequeue is easy..simply popping off the second stack because the order is reversed. If you want to enqueue again though, you'd have to do the reverse and pop each item off the second and push it back onto the first another n-1 times. So it looks like worst case it is O(n^2). Can anyone think of something better or help me improve this?
 
Technology news on Phys.org
Would it be cheating to use a queue of stack pointers and use one stack per object?
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »

Thread 'Who is responsible for the software when AI takes over programming?'

I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
View full post »

Similar threads

Running time of FirstFit(FF): Original and Improved version
Replies
4
Views
1K
MHB How can we apply the functions?
Replies
2
Views
1K
Merge Sorted Stacks in Ascending Order Using 4n-4 Moves
Replies
3
Views
3K
Java Can You Help Me Debug My Java LinkedList Stack Implementation?
Replies
4
Views
23K
How did early compilers overcome the need for a compiler to compile itself?
Replies
6
Views
2K
How Can We Efficiently Parallelize the N-Queens Problem?
Replies
11
Views
4K
Optimal Frequency Homework: Maximizing Air/Ground Queues
Replies
1
Views
947
How to creaate a priority queue using print queue
Replies
6
Views
3K
Stargazing Astro Image Stacking (optimize DSS image stacking and post processing)
Replies
43
Views
11K
Comp Sci Java Non-Recursive du command popping java.lang.InterruptedException
Replies
3
Views
3K

Hot Threads

Recent Insights

Back
Top