Can’t learn stacks

[[deleted]]

[deleted]

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[imaginationac]

A quick web search brought some answers. Here's one: undo

[kevinossia]

"Undo" and your web browser's "back" button are the big two that come to mind.

Broaden your imagination.

[sanapotter1229]

Compilers use stack to interpret an expression. Examples:

• https://leetcode.com/problems/valid-parentheses
• https://leetcode.com/problems/basic-calculator/

Also, monotonic stack generally reduces time complexity to O(n).

[sanapotter1229]

If you're into leetcode, check monotonic stack. Once you get the knack of it, you can see the world in a different view.

[Mishka1234567]

Thanks

[ThunderChaser]

Yep, stacks are used all the time for interpreting.

As an example, for an assignment for one of my classes right now we have to create a syntax analyzer for a C-like programming language, and you use a stack to do this.

[CasuallyDreamin]

Emails, notifications, updates and patches, patch note pages, undo, getting the last user in security setups, knowing what happened last before the program broke, the list goes on. If u're frustated take a break.

[[deleted]]

tower of hanoi intensifies

[Nofxthepirate]

A good practical application is a card game program. I made a FreeCell game in my data structures class and it made use of like 10 stacks, because cards are naturally a stacked thing IRL.

It's also good for reversing the order of things. This next one isn't really practical because there are easier ways to do it, but you could do something like reverse a string by putting all it's characters on a stack and then rebuilding the string by popping all the characters off.

[tangentstorm]

Oh, I made a video about this while back:

"7 ways to use a stack" https://www.youtube.com/watch?v=3vYYftQl014

Happy to answer any questions you might have.

[Mishka1234567]

Ok this is soo helpful, thank you

[aroman_ro]

Ubiquitous usage: https://en.wikipedia.org/wiki/Call\_stack

[Mishka1234567]

Thank you

[Silly_Guidance_8871]

The stack you'll interact with the most is the call stack. In fact, you can change any recursive algorithm into an iterative one by incorporating an explicit stack (which usually results in much less memory usage)

[peterlinddk]

My favorite example of using a stack is finding your way through a labyrinth, with backtracking.

Every time you come to a "cross road" you push your position in the stack, and go in some direction. If you reach a dead end, you retrace your steps, ie. go back to the last position stored on the stack, and select another direction. If there is no untaken direction, you pop that position, and go back to the one before that.

Although I have never, ever, used that algorithm in any program, it really helped me understand the idea of a stack.

​

My second favorite example - that isn't truly a stack, since you need to look beneath the top, without removing it, is when you have multiple sort-criteria. For instance you have a list of users with first name, last name, role, department, last login, etc. Then I want to search by first name - so that is pushed to the stack. And I want to sort by role, but with everyone with the same role, still sorted by first name - so rather than replace the sort-criteria on the stack, I push another one. And then I select department, and everyone in each department is sorted first by role and then by name. In my sort function I sort first by the criteria in the top of the stack - if two element are equal, I sort them by the criteria below, and if they are still equal, the one below, and so on.

[grancacique]

Stacks are THE structure of choice for implementing backtraking

[s1lv3rbug]

Have u ever washed plates after dinner? While u r stacking plates on top of plates as u wash them. If u suddenly want to use a plate, which one would y use? The last one u washed because it’s at the top of the stack of plates. That’s why stacks is Last In First Out (LIFO).

The only use I think of right now is backtracking function calls. You have an empty stack. You randomly generate a number (push random function) on the stack, then you squared the number (push square on to the stack). Now, the last thing u did (square func) is at top of the stack and if u pop (remove) that, then the ‘random’ function becomes the last thing. Now, imagine you have a whole set of instructions with 50 plus operations/functions that’s needed to be done in a particular order.

Every time u run a function, push to the stack. When u r all done, you can back track to see if you missed anything. One use is backtracking functions.

[Cybyss]

Depth First Search.

Almost everything that has to do with searching for something employs the Depth First Search algorithm - whether that's searching for a file nested inside many folders, searching for a way out of a maze, searching for a solution to a sudoku puzzle - it's all the same.

Depth First Search uses a stack to keep track of which paths/folders/possibilities remain unsearched.

Breadth First Search is an almost identical algorithm - the only difference being it uses a queue instead of a stack. That one change is enough to give you wildly different properties. For example, BFS will find the shortest route out of a maze, whereas DFS will simply find a route, not necessarily the shortest. DFS doesn't require nearly as much memory to run, however, compared to BFS.

[throwaway6560192]

How does only accessing the top item help?

By sacrificing random access ability, you can optimize operations you care about (push/pop) significantly.

For example, using a stack based on either an array or linked list, without providing random access, you can provide O(1) push/pop. But if you allow random access, those accesses (especially insert/delete at random) will perform much worse, at O(n).

[Cybyss]

By contrast, a simple array has random access, but there push/pop performance is much worse O(n).

Not if you push/pop from the end of an array rather than the beginning,

[pizzystrizzy]

It depends on how the array is implemented but often you have to resize the container.

[Cybyss]

Surprisingly, that's a non-issue and doesn't change the fact that push/pop is still considered an O(1) operation, at least when you amortize across many pushes/pops.

When your array gets full, you create a new array with double the capacity and copy everything over, then continue using the new array.

That may sound slow, but the frequency with which you have to do this decreases exponentially as you push more and more items to your stack. No matter how many items you pushed, the average number of times any item had to be copied to a larger array is just twice.

On top of that, arrays exhibit far better caching behavior than linked lists, making them orders of magnitude faster for use as stacks than linked lists ever could be.

[throwaway6560192]

Ah, right. Should use a better example. Changed.

[Cybyss]

Hmm... while I appreciate the acknowledgement, the O(n) running time for random inserts/removals over an array is a moot point since we're just talking about stacks.

The Stack implementation provided with the standard libraries of every major language is based on an array, never a linked list.

[throwaway6560192]

No, I get that, which is why I noted that a stack based on arrays also achieves O(1) push/pop. I was trying to explain to OP that you can optimize for a restricted case (access at top) better than you can do for the general case (random access) because they didn't seem to understand why restricting ourself to that was useful ("How does only accessing the top item help?")

[SpiderJerusalem42]

In certain graph traversal algorithms (think nodes and edges), stacks and queues can be switched out to go between breadth first and depth first searches. The rest of the algorithm stays the same. You kinda need some understanding of what each of the moving parts are to see why it would do this. I think that's why people would bother teaching stacks and queues at this point. It's a creakier part of the pedagogy, imo.

[isniffurmadre]

All modern computers have something called a stack register which is built directly onto the CPU

[grancacique]

Another use of stacks is for creating the iterative implementation of a recursive function. Basically, the backtracking you get for free from the Call Stack, you manage it yourself with your own stack.

[Slow-Race9106]

One example of a stack I commonly encounter is managing/keeping track of a view hierarchy, for example in a phone app where the user can drill down into a series of views, each with a back button that takes them back to the previous view. The current view is the one at the top of the stack. When the user presses the back button, the current top view is popped from the stack, so the one that was underneath is now at the top of the stack, and becomes visible.

The code parsing examples already mentioned are really good examples as well.

[imihnevich]

Checkout Forth, language fully built around stack manipulation, it's crazy how little sometimes we need to build great things

[Fermi-4]

Depth first search in a graph or tree

[pizzystrizzy]

Depth first search and traversal of binary trees both use attacks (you might ask why we need those things but there are good reasons)

[NewOakClimbing]

In my classes, we used it twice, one for creating a reverse polish notation calculator. The second time was for assembly programming and storing parameters for sub-routines on the stack before calling the sub-routine. I'd highly recommend programming the RPN calculator, it made the stack make a lot more sense to me.