[DSA] stack

Stack, a last in first out (LIFO) type of data structure.

very similar to our STL list learned last week, there is also a STL stack.

|a|

|b|

|c|

Long long long time ago when i was still a student and still staying in the hall (Now I am still a student, constantly learning new things!). My friends always asked me why i always wear the same t-shirt from monday to sunday. Being the computer science student, I try to explain to them the reason using the stack data structure. Every time my laundry is done, it is folded nicely (assume please) into a stack. When I fold my t-shirt, and placed them in a stack. I fold them in the same order for every week and always take from the top of the stack of tshirts so that my wardrobe will not be messy(assume it is not messy).

Talking about needing randomization in folding t-shirt and putting them on a stack. Every morning wake up, I am always in a rush. So, I always choose the first t-shirt (the top in stack data structure) of the stack. The cycle repeats it self again and again. Sometimes, I do accidentally pull a tshirt out of the middle of the stack and the stack of tshirt just collapsed. Things got better when I found another person to fold my laundry when I was staying in hall!

Stack is efficient, minimal disturbance to the memory when data is inserted/deleted because only the top of the stack is modified. But when the 5th element of a 10element in a stack need to be retrieve, there is a lot of manual code needed for manipulation. Hence the efficiency and performance of the stack data structure is not satisfied.

So......what to do with the stack data structure? It can be used to store the dungeon level information. How many of you have played the game dungeons and dragons?? The assumption is that player can only go to 1 level above or 1 level below the current level of dungeon. Hence, using a stack to store is more sensible. Of course, a list can be used too. But... what are the consequences????

Have you wondered how the mouse in the micro-mouse competition know how to escape from the maze??? All movements of the mouse, eg forward, backward, left, right are stored onto the stack. When a dead end is encountered, the mouse will take a step back by simply pop off the top item on the stack. This is for navigation that requires a step back look left/right algorithm.

Other uses of stack, is in the operating system, where the system variable is stored. The stack is used to hold temporary variable of an executing program. Another stack is used to store the starting address of programs. What happens when the stack used to store variable is "overflow" ????

Drill question for the week,

1. Create a stack of 10 items.

2. retrieve the 5th item on the stack.

3. display the remaining item on the stack.

4. Modify week 4's decimal to binary conversion program and implement with stack.

4. Modify week 5's palindrome checking program and implement with stack.