The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

30

There is one aspect not yet mentioned, though the first two answers are excellent. Libraries usually contain only the most common data structures and those that can be used in some generic way (pun intended, I guess). But there are other data structures that you may need in your work that aren't in the library you have available. The tools you need for ...

27

Note: Initially my answer was just about computational complexity, but then it grew a bit, so I broke it into multiple sections and tweaked each a bit. Thanks to commenters for pointing out the details to fix. Understanding computational complexity That may be covered by your "understand better how these structures behave", but it important enough to ...

21

I once had to implement a limited undo function (undo changes to the current field, or addition/deletion of records). The lists of undo deltas (one for field changes and one for records) were stored as stacks.

15

A rather interesting analogy is that of a firearms magazine. if we look at this picture: It is easy to see that bullets can be inserted from the top, and only the topmost bullet is accessible. Such is a stack. A magazine works by LIFO (Last In First Out), and so does a Stack. Furthermore, the four (five1) basic operations of a Stack are applicable: ...

14

A stack of trays in a cafeteria. I also like the pole of rings analogy. With the trays, you can pop (take a tray) and push (return it when you're done). You can see what the top tray (first item) is (ex. what color), and see if the stack is empty. Non-stack operations such as getting a count of the trays are non-trivial. It is also impossible to insert or ...

12

The back button on a web browser is an excellent example of a stack implementation that is easily understood even by non-experts and easily demonstrated in a class. You can illustrate the stack in diagrams, and you can show it in action in a browser. When a user visits a new web page, the current page gets pushed onto the stack. When the user clicks the ...

12

In my experience, it is typical to have students make their own implementation first so that they understand what is going on "under the hood," so that they can make better choices for which structure to use when they need to use a standard library. It helps them to understand the complexity of an algorithm. I have seen where the standard implementation ...

10

Check whether a string of parentheses is balanced or not. For example, return True for these input strings: (()()) ([]{{}}[]) but False for these strings: (() ([)(]) You can solve this using recursion, but a very efficient and clear solution would be to iterate over the string, whenever you encounter an opening symbol, you push it into the stack. ...

9

I like the pez dispenser. Also the stack of papers (where the actual human interaction is never to take the top item but rather to take the second from the top. At some point you have to talk about pancakes and the fact that people don't actually eat them as a stack -- they frequently destroy stack integrity by cutting top to bottom. I personally use a ...

8

One example I've used for students in the past is a shared printer. If I have five people using a printer all at once I will have a problem if two of the five attempt to print at the same time. What can I do? I can put up a sign on the printer--"Only One User At A Time Please" and hope everyone sees and follows it. Of course then the users need to ...

7

Link to real life “Who has came to school by bicycle?” “OK so we need to know how to make a bicycle” “What time did you get up? It must have taken a long time to build the bicycle?” Take it to the limit; be absurd. So the pupils tell you “You don't need to know all this to get to school.” Agree with them. “Any one here ever fix a bicycle?” — “yes” “So you ...

7

The "real-life" examples are pretty clearly delineated here already, but since you asked for examples in programming as well, I'll add one to the list. Stacks can be used to build calculators. There's a great assignment in CS50 AP called Calc 2.0. Students build a command-line calculator in C using a stack to store the numbers passed in by the user. ...

5

In practice, many calculators employ the Shunting Yard algorithm to evaluate mathematical expressions as per the rules of BODMAS. The algorithm makes use of stacks to push and pop operators based on precedence and position.

5

Sorry, but digging in your heels or telling the students to wake the hell up is going to get you exactly nowhere. When a small percentage of your students fail to successfully complete a project it is likely their own lack of background or application. But when only about a third are able to successfully complete it, it is a problem with the course, not with ...

4

Much of what has been said already is wonderful. I would like to point out that Mike's Pez dispenser visualization is brilliant, and lends itself to a direct lesson with manipulables. You can take a few of them into an actual classroom, mix up various Pez colors, and show all of the standard operations of a stack in a way that they can physically play with....

4

Here are couple of examples which don't employ objects resembling real-life stack: Russian doll (matryoshka). It is a stack if you use the relationship contained_in(BiggerDoll, SmallerDoll) as a model for stack. push in this context would be equivalent to encasing a stack of Russian dolls in a yet bigger Russian doll, pop would be equivalent to opening ...

4

This won't work for all students, but some will likely be familiar with the very popular collectable card game Magic: The Gathering. In this game, spells are cast to "the stack", with the last spell cast resolving first. During resolution of the stack, more spells may be cast to the top of the stack.

4

Trial and error, as well as practice, are usually the best way to get students to be comfortable with anything. "All" you have to do is give them time and plenty of opportunities to use multiple layers of abstraction. They will find it difficult at first, but after a while they'll become noticeably better at it, and eventually they would be quite ok with ...

4

Yes, you should at least introduce the idea to your students. That said, it is also a truism of education that you need not explain every concept at the same level of detail. In this particular case the first couple of paragraphs of the Wikipedia article on the subject is probably enough. A couple of minutes could be well-spent. Students need to know ...

4

Let me answer from the perspective of someone who recently completed a Data Structures and Algorithms course. Background My Data Structure course was taught using java applets two years ago. My design pattern course last year was the first class many of my peers were exposed to Git (or any version control for that matter), and SOLID design principles were ...

4

I've seen too many students implementing linked lists, and then using linked lists of chars as buffers... Of course at some point students have to understand how things work. But novice programmers have to learn to think first in terms of abstractions they need in their programs (Example: I have to add/remove/etc. names, so I need some representation of a "...

4

Assuming they will have a career in C#, you're right to assume that your students will likely never have to make their own queue or stack. However, that's not the point of the lesson. The point of the lesson is to learn how to make a tool. Think of it this way: Every programmer starts off with a "Hello World" application. There is likely never ...

4

The Shunting Yard Algorithm To go along with your example of evaluating RPN, you can convert infix notation into RPN with the Shunting Yard algorithm It uses both a stack and a queue, although the queue is really only used as an FIFO output; the algorithm never reads from it. This algorithm has the benefit of being practical, and its use is immediately ...

4

Ideally, I would like some simpler problems which can be presented with even lesser background. Fortunately, queues are used often in everyday scenarios. If you're just trying to teach the general First In First Out (FIFO) concept of a queue (and not necessarily how it solves more complex computing problems), then there are a lot of opportunities to show ...

3

tl;dr Build the layers with appropriate scaffolding, either top-down or bottom-up. The goal is to understand an abstraction layer architecture. The teaching method is to have students build it layer by layer. Here is a suggestion that you can adapt to quite a few situations, though it takes some work as well as some consideration of tradeoffs. The basic ...

3

Students are better able to handle structured information when they understand, at the start, what that structure is. Explain the situation to your students. You are about to present a series of deeply interconnected systems, and though they form a beautiful system together, they essentially can't do anything until they're all moving in tandem. That means ...

3

In my view, a good computer science example for stack-oriented processing is the PostScript language. The Hello world example from the Wikipedia page shows the Reverse Polish (postfix) notation used in PostScript (similar to the CS50 AP Calc 2.0 Peter showed in his answer that uses prefix notation): %!PS /Courier % name the desired font 20 ...

3

It find it extremely important to teach them the principles behind those (or similar) data structures first, and I'd go so far as to pick any one of the more complex ones as well (0/1-trees or even B-Trees etc.), just for fun (maybe skipping some details, if time is an issue). I'd also stress some "outliers" like ones that have O(1) in some of their ...

3

Understanding the structures is indeed important. They will often use a library, but should then have a good idea of what the library does. The only argument I see against coding basic structures in programming exercises, is if the time could be better spent doing something else. But my experience is that students starting at "too high a level", tend to make ...

3

While uniform collections are the obvious example, you can also build or use a Pair class in which the types of the two components are given by generic arguments. If you don't want to build it, there is a built-in class with this property: $Pair<K,V>$ But building one like it is simple enough if that is your goal. Once you have your desired class, ...

Only top voted, non community-wiki answers of a minimum length are eligible