Today I am going to be writing about two data structures used with lists. In my experience I have seen these structures used most often with arrays and linked lists. They are called a stack and a queue. Stacks and queues have come up quite often in my experiences with coding, on a couple levels. I have built my own stacks and queues to achieve certain goals and I have encountered them with things that I havent built. I mean one of the most popular coding resources out there is called stack overflow for a reason.
The reason why I am talking about this today is because I was dealing with a problem earlier that I was taking a really long time to figure out. It was a rather simple problem, but for some reason I was struggling to make a solution. I honestly think I was just tired. The problem was as follows: 2 input strings would be applied to my function, and within these strings could be any number of hashtags('#'). These hashtags represented backspaces. The goal of the problem was to see if the two strings were the same after the backspaces had been applied. So you might have string1 = "a#a' and string2 = 'aa#'. When the backspace is applied to both strings you would have string1 = 'a' and string2 = 'a' as well. The output is a boolean true or false.
For a while I played around with some stuff and I think I would have eventually got it, using another method but it was turning into a lot of code. I was sure there was a more elegant way to write the function so I looked at some of the other solutions to get some insight. And boom I saw a stack method. I had totally spaced on even thinking about using a stack, and the solution was brilliant. While I dont necessarily recommend looking at solutions to solve algorithms, I think it this situation it helped me. There are many patterns in algorithms and I think that sometimes just being able to recognize where you can use a solution method is useful.
So stacks and queues. They are both similar, but not so similar in how they function. Their rules of functionality are the most important parts. A stack worths with LIFO and a queue works with FIFO. These anagrams stand for Last In First Out and First In First Out. They are very commonly used or else I would have just written out the rule. A queue(FIFO) works just like a line. You join a line at the last place and when you come up to the register or whatever, you are then served and
then exit the queue.
A stack, however, is generally a bit more difficult for people to understand, but I find I see it more often (thats just me though). I think a good way to imagine it is with my oreo analogy. You buy a pack of oreos. If you are like me, you might just call it and eat the whole pack like a beast. Or as a reasonable person you might limit yourself. So you say, I am going to eat only 5 oreos. Also being a programmer, you arent just going to grab 5 and toss em on the counter. Instead, you take one out, put it down, take another and put it on top. Once your fifth oreo is added to the stack you then eat the last one that was placed on the stack, and finally the last oreo eaten was the first one that started the stack.
So back to my algorithm problem. Using a stack to create a built string without the backspace hashes or the corresponding characters of the string that they would delete was perfect. Going through the string, the function would check whether or not we saw a hashtag, if we havent, the character is pushed in, but once we see a hashtag we pop off the last character put in. It is quite nice and I will be sure to remember this methodology in the future.
Lastly, I want to talk about a stack overflow. This might come up often in your errors. The call stack for functions is something programmers should be familiar with. When we are executing multiple functions we develop what is called a call stack. Imagine this situation:
First we will hit the one function, this will be added to the call stack. Inside it will execute the two function, this will also be added to the call stack. Then we execute everything inside the two function. Once it is complete it is removed from the call stack. Then we are back to the one function which is then completed and removed from the call stack. Then the call stack is once again empty and our functions have been executed. If we hit a stack overflow it generally means we are using too much memory in the call stack. So if a function within the call stack is taking too long we hit an overflow and break our program.
Top comments (0)