Answer a programming question, get a tiny bit of fame!

[Bert Bates]

Hi Guys,

We're working away on K&B 7. We believe that the best way to introduce a topic is to provide a simplified, real-world example of the topic in use. Here's an example of such a topic:

If the topic is "queues", we might say:

Suppose you need to automate your company's customer support center. Sometimes there are more callers than support staff. When this happens, we want to put the callers on hold and answer the "on hold" callers in the order in which they called in. First caller gets handled first.

Now, here's the deal, I'm looking for a similar example for stacks. Here's what I DON'T want:

- "Suppose you're creating the back button for a new browser" - not many folks will do that
- "Suppose you're implementing a new JVM" - same
- "Suppose you run a railroad switching yard and need to resort train cars" - again, uncommon
- "Suppose you want to automate the trays in a cafeteria" - really?

I also would prefer not to use a computer science-y task like traversing a tree.

If anyone comes up with a nice, natural, in-the-world example, and we use it in the book, we'll give you a shout out like "this example contributed by rancher Bob Smith, thanks Bob!".

[Bert Bates]

Oh, and extra-bonus fame if you can come up with a good example (same criteria as above) of a "franken-structure" - a situation in which a single structure (an ArrayDeque) is sometimes treated like a stack and other times like a queue.

For instance a calling center that has priority clients that can jump to the front of the queue almost works, but not quite...

[Ernest Friedman-Hill]

At work we've been talking about "stacked dialogs" a lot lately. You're ordering something online (filling out a form) and you need to choose a "payment method" and you have never actually put in your gift certificate. So you push a button and a new form comes up in front of the old one, representing the subsidiary task of creating a new payment method. While you're working on that, you need to enter the expiration date, so you end up with a third form -- a trivial date picker, but still, it's a little form. Each time you complete a form, it is "popped off the stack" and you interact with the previous one. In all cases, you can only interact with the form that's showing -- the "top of the stack" -- and you return to them in the reverse order that you first saw them.

The iOS GUI is full of these stacked dialogs.

[Bert Bates]

aren't you famous enough?

interesting, it's got possibilities...

[Ernest Friedman-Hill]

Bert Bates wrote:aren't you famous enough?

I hereby grant my byline to somebody more deserving

[Tess Jacobs]

Bert Bates wrote:aren't you famous enough?

It's not fair. The rich are getting richer and the famous are getting more famous

[Jelle Klap]

How about a good ol' stack of pancakes? Everybody loves pancakes!

[Jayesh A Lalwani]

Bah! Jelle stole my example. The pancake example can illustrate LIFO ordering. Maybe you can talk about how a stack ensures that the workers always got the hottest pancakes.

Another good example of a stack could be something that explains the execution stack. However, I have a hard time coming up with a non-technical example.

[Ernest Friedman-Hill]

Not that I'm being competitive about protecting my idea, but the thing with pancakes is that once you've stacked them up, you proceed to cut through the whole stack like one big cake, and eat a mouthful consisting of a little piece of each pancake. This makes them not LIFO at all.

Come to think of it, the little wedge of the bottom pancake on the stack is the first one into your mouth

[Martin Vashko]

A non-technical example of an execution stack could be my typical working day:

1) I'm sitting at my desk, writing a specification.
2) A co-worker stops by to politely inform me that I've somehow broken build scripts yesterday. I put aside the specification work and have a look at the scripts.
3) Phone rings. A customer is reporting a bug. I'm answering the phone.
4) I try to instruct the customer's technician to upload the data related to the bug to our FTP server, but I discover the server is down.
5) I go to the server and try to figure out what's wrong with the FTP server.
6) On my way there I accidentally spill a cup of coffee on co-worker's desk.

So, this is my stack. At this point, the course of actions follows like this:

6) Search frantically for some cloth to stop the coffee spill before it reaches the edge of the desk and the computer beneath.
5) When done, return to the server. Restart it to get FTP up and running and instruct the customer to upload the data
4) When done, have a look at the data and create a ticket for the issue.
3) When done, get back to the customer and inform him the ticket has been created.
2) When done, get that pesky build script working.
1) When done, go home, since it's long past the office hours. The specification waits on the stack one more day.

Or better, I wish it would work this way. Turns out the implementation of stack hard-wired into my brain is buggy and throws exceptions (or worse) when the size of the stack exceeds about three...

[Jelle Klap]

Ernest Friedman-Hill wrote:Not that I'm being competitive about protecting my idea, but the thing with pancakes is that once you've stacked them up, you proceed to cut through the whole stack like one big cake, and eat a mouthful consisting of a little piece of each pancake. This makes them not LIFO at all.

Come to think of it, the little wedge of the bottom pancake on the stack is the first one into your mouth

Oh you Americans and your ridiculous pancake eating rituals!
This is how pancakes are meant to be eaten! You pop one of the top of the stack, put whatever you like on it, roll it up and eat it. One at a time

[Tess Jacobs]

How about dinner time. In the kitchen, mum stacks the plates on the hand. She then walks to dining room and distributes the plates to her kids in a LIFO order.

[Ernest Friedman-Hill]

Jelle Klap wrote:
This is how pancakes are meant to be eaten! You pop one of the top of the stack, put whatever you like on it, roll it up and eat it. One at a time

Those are not pancakes, they are crepes!

[Jelle Klap]

Ernest Friedman-Hill wrote:

Jelle Klap wrote:
This is how pancakes are meant to be eaten! You pop one of the top of the stack, put whatever you like on it, roll it up and eat it. One at a time

Those are not pancakes, they are crepes!

Oi! I'm not French! Those are good old, original Dutch pannenkoeken (literal translation: pancakes). I don't eat crêpes while watching soccer, I eat pancakes while watching football, thank you very much
Or I would if I didn't loathe the game...

[Rameshwar Soni]

Monday morning at the school, Mr.Peter the strict professor enters the classroom of 100 students including Tom and Jack the naughty and mischievous students.

Mr.Peter: "Tomorrow you all need to submit your books with completed assignments of chapter 1 and 2.
I will try to check maximum books in tomorrow's 50 minutes lecture.So be ready to submit your books on my desk"

Next morning.................

Tom: "Jack, my friend have you completed your assignments ?

Jack : "No, the assignments are incomplete. What about you ?

Tom : "Same here. I haven't completed them. Now Mr.Peter will come and ask about them."

Jack : "I know. I am very afraid man. What will happen to us ?? "

Tom : "Don't worry you are Tom's friend. Do you remember what Mr.Peter said ?"

Jack : "Yes, he is going to check are assignments."

Tom : "No, he said I will try to check maximum books in tomorrow's 50 minutes lecture."

Jack : "So what do you have any idea to save us from Mr. Peter ?"

Tom : "Only one thing can save us".

Jack : "What's that ?"

Tom : "The concept of Stack."

Jack : "What are talking ? I am not able to understand."

Tom : "The concept of Stack is LIFO (Last In First Out) or we can say FILO (First In Last Out)"

Jack : "Don't know what you are talking. I am really afraid man"

Tom : " I think you need to do it practically. Let Mr.Peter come and when he comes, you just follow me.

Jack : "Ok."

..................Mr.Peter enters the classroom...................

Mr.Peter "All students please submit your books with completed assignments. I will try to check maximum books in this lecture."

................................Tom runs fast, very fast to submit his book on Mr.Peter's desk and Jack follows him. Rest all students are moving slowing and submitting their books on Mr.Peter desk., which resulted in a stack of 100 books with Tom's and Jack's books kept at the bottom.................................

After 50 minutes Mr.Peter managed to correct or check only first 90 books and he is tired and says

Mr.Peter : Rest all books will be checked by me tomorrow.

Tom : Jack did you understood stack. Go First and Come Out the Last. i.e. Our book was the first to go for getting checked and last to get checked

Jack : I understood it now. Thanks to the concept of Stack for saving us.

.......Next day Tom and Jack completed their assignments and finally got it checked.

....Thanks to Stack for giving us one extra day to complete our assignments.

We can also show some stack of books as a picture at a desk and a professor checking them etc.

It was just an attempt. Sorry to those who didn't liked it.

[Bear Bibeault]

I don't care what they're called, they look good!

(But yeah, Americans would call those crepes -- pancakes are much thicker.)

[Matthew Brown]

Where I come from, I think we'd call those drop scones.

If it helps the argument, I could probably bring myself to eat lots of both types. All in the name of research, of course.

[Frank Silbermann]

How about a Hewlet Packard calculator program that computes Reverse Polish Notation?

[Bert Bates]

Let me add a refinement.

The example should make some sort of sense as an app that might, remotely, make some business sense or some interesting game. So it's not so much something like pancakes, which, while occurring naturally in "stacks", you would probably not automate...

So the example I gave of automating a call center is conceivable as an actual app.

[Steve Luke]

How about an inventory mapping system. The system is designed to map particular items to their location. When an item comes in as inventory the system assigns it a space and directs the inventory clerk where to put it. When the item is purchased the system tells the clerk where to get the item to ship. It will direct the clerk to the last item placed because it will be the one which is most accessible.

[Mark Yevgeny]

Bert Bates Wow! that's really great K&B 7 WOW !!! I Love Head First Things.

[dennis deems]

Can't think of a business application. But many solitaire games such as Klondike illustrate LIFO: you build down on the tableau until you can begin filling the foundations; from any given tableau pile it's always the last card played that goes to the foundation. So if we were designing a software version of the game, we naturally might want to implement the tableau piles as stacks.

[Bert Bates]

so far this game-domain idea is my favorite!

[Bear Bibeault]

What's the name of the game that's sort of like a vertical checkers? Seems sort of stack-y to me.

[Mike Simmons]

Connect Four?

[Bear Bibeault]

Mike Simmons wrote:Connect Four?

That's it.

[Martin Vashko]

What about Backgammon?

[Bert Bates]

great game, and I think perhaps still a good direction, but in Connect4 there is only pushing - no popping until the game is done...

maybe some sort of a "breadcrumb" idea? backing out of a maze...

[Ryan McGuire]

Bert Bates wrote:great game, and I think perhaps still a good direction, but in Connect4 there is only pushing - no popping until the game is done...

maybe some sort of a "breadcrumb" idea? backing out of a maze...

How about the back button in a web browser? You push the most recent page on top of the stack whenever you navigate to a new page and pop one off the stack when you hit the back button.

In fact, you could implement forward and back with two separate stacks. When you hit the Back button, you would push the current page onto the "Future" stack and pop one off the "Past" stack and use it. If you hit the Forward button, push the current page onto the Past stack and pop one off the Future stack to use. If you navigate to a new page, clear out the Future stack. After each of those operations, disable the Back button iff the Past stack is empty and disable Forward iff the Future stack is empty.

This applies to all kinds of applications that have Back and Forward or Undo and Redo commands. For editor type applications (word processors, graphic editors, spreadsheets, etc.) you could maintain Past and Future stacks as described above. The elements in those stacks could be either Command objects, which contain the functionality to undo and redo the various operations, or Memento objects, which merely encapsulate the states of the changing object without any real concept of how the state changes happen.

It might make more sense to implement the Undo/Redo mechanism as a single stack with just a single Current pointer. However, a double stack implementation isn't out of the question.

[Ryan McGuire]

Bear Bibeault wrote:

Bert Bates wrote:so far this game-domain idea is my favorite!

While the nitty-gritty details of the rules for Magic: the Gathering would be more than you'd want to get into, the rules for that game explicitly mentions a stack for resolving multiple spells and abilities. http://www.essentialmagic.com/articles/TheStack.asp

[Martin Vashko]

What about this: in a game of chess, record the moves made by the user and the computer in a structure. When the user wants to take back moves, it is used as a stack. When the user wants to replay the game he's just finished, the structure will be used as a queue.

[Ryan McGuire]

Bear Bibeault wrote:

Mike Simmons wrote:Connect Four?

That's it.

A game that does use stacks where items are added and removed from the top is Cover Up from Out of the Box Publishing. http://boardgamegeek.com/boardgame/21457/cover-up Granted, there are three sizes of pieces and the pieces in each stack are in monotonically increasing order, so the number of items in each stack is pretty limited. However, one additional property of the games that makes it applicable to a stack discussion is that only the most recently added element in each stack is visible.

[Matthew Brown]

The Towers of Hanoi puzzle is based on (three) stacks. There must be a number of card games that would qualify as well - e.g. gin rummy. Which would be great if the readers could be assumed to know the rules, but may take some explaining otherwise.

Inspired by Martin's last post, any application where you want to be able to undo and redo actions would use a stack (e.g. text editor). You can only undo the last one (at a time), so you have a stack of undo operations. As you undo actions you also get a stack of redo operations.

[Stuart A. Burkett]

Ryan McGuire wrote:How about the back button in a web browser?

Being able to read specifications is an important skill for a programmer

Bert Bates wrote:Here's what I DON'T want:

- "Suppose you're creating the back button for a new browser" - not many folks will do that

[Jelle Klap]

Bert Bates wrote:
The example should make some sort of sense as an app that might, remotely, make some business sense or some interesting game. So it's not so much something like pancakes, which, while occurring naturally in "stacks", you would probably not automate...

That's easily solved: invent a game around pancakes!
Maybe with a western twist, where the poor saloon keeper, under pain of death of course, has to keep a horde of outlaws fed with the outlaw food of choice: pancakes.
I'd call it: Stack 'em High!

Ok, I'll stop droning on about the pancakes now

[Bear Bibeault]

Jelle Klap wrote:That's easily solved: invent a game around pancakes!
Maybe with a western twist, where the poor saloon keeper, under pain of death of course, has to keep a horde of outlaws fed with the outlaw food of choice: pancakes.
I'd call it: Stack 'em High!

OK, now that sounds like fun!

[Ryan McGuire]

Stuart A. Burkett wrote:

Ryan McGuire wrote:How about the back button in a web browser?

Being able to read specifications is an important skill for a programmer

Bert Bates wrote:Here's what I DON'T want:

- "Suppose you're creating the back button for a new browser" - not many folks will do that

Touche. :-)

Nonetheless, the later paragraphs in my post still stand:

This applies to all kinds of applications that have Back and Forward or Undo and Redo commands. ...

I suppose creating a new word processor might fall into the same category as creating a new web browser. However, there are plenty of more specialized "editors" as well. For instance, at work I use a taxonomy/ontology editor with a GUI interface on a day-to-day basis. It would benefit greatly from the addition of undo/redo. There are any number of apps that could be considered "editors". An HR data entry app could be considered a specialize DB editor. Matthew effectively +1'ed the undo/redo concept for editors as well.

In a slightly different vein, Martin used a chess game as another example of an app with undo/redo. I like the game undo/redo idea, because the order of transitions of the game from one state to the next is the interesting part of the app. In contrast, when you're editing a text document, only the end state is the exciting part. How you got the document to that state isn't as exciting. ...relatively speaking.

[Ryan McGuire]

Jelle Klap wrote:
That's easily solved: invent a game around pancakes!
Maybe with a western twist, where the poor saloon keeper, under pain of death of course, has to keep a horde of outlaws fed with the outlaw food of choice: pancakes.
I'd call it: Stack 'em High!

I'm certainly not against a game about pancakes. <-- just licking up a dribble of maple-y goodness.

However, I don't yet see why pancakes would be removed from the stack in a stack-like LIFO manner. I'd prefer a FIFO arrangement for my pancakes so that the ones at the bottom of the stack don't go to waste because they got cold.

I know... the players of the game could be hungry lumberjacks and pancakes would get added to the stack by some random timer mechanism. It's up to the lumberjack players to get the most/best/hottest pancakes from the top of the stack without going hungry. They have to balance waiting for fresh hot pancakes with the discomfort of being hungry now.

[Jayesh A Lalwani]

Well they are outlaws, and they are hungry, and you don't feed an hungry outlaw a cold pancake because he's just goin to shoot you

[Bear Bibeault]

Ryan McGuire wrote:However, I don't yet see why pancakes would be removed from the stack in a stack-like LIFO manner. I'd prefer a FIFO arrangement for my pancakes so that the ones at the bottom of the stack don't go to waste because they got cold.

The bottom pancakes stay warm because they are insulated by those above. I cannot imagine trying to treat pancakes (at least individually) as anything but a stack.

But then, I eat the whole stack like a cake. But to dole them out? A stack for sure.