Stacks, Queues, Priority Queues, and the Prince's Complaint Line

Stacks and queues are very simple, yet fundamental, data structures in computer science. Simply put: they store data. You put a piece of data in the stack or queue, go about your business and later take that piece of data out. Where they differ is in how they order the data that is extracted. Stacks are last-in, first-out data structures that return the most recent data inserted. Queues are first-in, first-out data structures that return the least recent data inserted. And priority queues return the highest priority data inserted (accord to some priority value). Understanding these ordering effects is the key insight into understanding how these data structures can effectively be used.

Before he became king, Prince Fredrick had a tradition of hearing his future subjects' complaints every Tuesday in the great room. At 10 am the doors would open, and his loyal subjects would fill the room to raise their complaints. On days that he was feeling particularly generous, Prince Fredrick would even task his steward with addressing some of the complaints. However, on most days Fredrick felt that he had done his part by just listening and he would promptly forget everything that was said.

By 6 am every Tuesday a great crowd formed outside the doors to the Hall of Complaints. In fact, farmers with particularly pressing concerns camped out for days or weeks hoping to be near the front of the crowd and thus be selected to discuss their complaint. The fact that their complaint would likely be ignored did not dampen their resolve. They needed to be heard.

Fredrick never gave much thought to what happened before the doors opened. After all, he was the prince. Why should he care about what happened outside of his room?

Then, Rok the Dragon arrived. In early June the dragon started burning crop fields and eating the livestock -- typical dragon activities. However, Fredrick continued to use his system, selecting the subjects from the front of the room.

In late July, Fredrick finally selected a farmer who was there to talk about the dragon. "What is your complaint?" asked Fredrick.

"A dragon ate my farm." the farmer replied.

"A dragon?" Fredrick screamed. "We must act now before it destroys a second farm!"

Silence followed Prince Fredrick's proclamation.

"What is it?"

Fredrick

asked, but nobody responded. Fredrick singled out another farmer and directed the question at him.

"It is just... Well... The dragon has destroyed over twenty farms since it arrived here in June. My farm was actually destroyed six weeks ago."

"Then why am I only hearing about it now?" screamed the prince.

"Noble sir, I have been lining up for six weeks to discuss the dragon. It is only today that you gave me an audience." answered the second farmer.

"How many others are here to talk about the dragon?" inquired the prince. Half the people in the room raised their hands. The prince screamed at everyone in general. Eventually he calmed down enough to send his best knights to run the dragon out of town.

"This will never happen again." the prince vowed. "From hence forth there will be a SYSTEM. Each person will write down their complaint and put it on top of a complaint stack. Each Tuesday from 10 am to 11 am I will take the top complaints off the stack and read them. This way I will always hear the most recent complaints."

Everyone in the room looked at each other. They gave a half-hearted cheer. "Yay."

For the next few months life returned to normal and the Royal Complaint Stack worked about as well as the unorganized mob of people in the complaint room. Then Rok returned. On Wednesday he ate one farm and took a week-long nap.

On the following Tuesday the prince read through the first ten complaints on the stack. All ten were about the refereeing at last Sunday's sporting event. The blue team had lost and its fans were unhappy. The prince had an easy solution and told the steward to bet against the blue team next week. Feeling like he had fulfilled his duty to the people, the prince decided to quit early and play some golf.

The prince found Rok sleeping on the golf course. The prince screamed when he saw the dragon. "What is it doing here? Why was I not told?" He threw his golf clubs at his caddy in frustration and stormed back to the castle.

He was still fuming when he got back to the castle. "I should have been told. Why did no one complain?"

"Your honor" started the steward very carefully. Fredrick picked up on his tone immediately.

"Where is the complaint stack?" he demanded. The steward brought in the stack of complaint papers. The prince started to leaf through them. The top eight were something about food poisoning from today's special at some local restaurant. Under those were more complaints about refereeing. Then he found it. Complaint number thirty one on the stack was about the dragon.

"Curses!" he yelled at the stack of papers.

"No more complaining about minor things when there are important problems!" the prince declared.

The steward sighed. "Sir, how will we tell? The people want to be able to complain about what is bothering them."

"Then there shall be a NEW SYSTEM." Everyone groaned quietly.

The prince retired to his study and began working on the new system. It had to let people voice their frustrations. It had to allow the prince to find the most important issues. More importantly, it could not take too much of his time; he really hated dealing with complaints. He spent three weeks in isolation working on his system.

The following Monday, he addressed his subjects. "I have devised a new system: a priority queue. Each of you shall write your complaints on a piece of paper. Every Monday night, the steward shall read each complaint and assign a priority from 0 to 10. We shall then deal with the highest priority complaints first." The prince paused and waited for the applause. A few subjects clapped lack-lusterly. The steward audibly groaned at his new task. He knew quite well that everyone was going to complain to him about the assigned priorities.

And so the kingdom adopted a priority based complaint system. Over time, the subjects embraced this system. The prince went on to become king and guide his kingdom through a period of unprecedented happiness and quick responses to dragons. Everyone in the kingdom was happy... except of course the steward.