Stacks :
A stack of plates
There is another simple technical concept about data structures which is LIFO - Last In First Out.
Consider the stack of plates above, LIFO does apply to it right ? The plate you stack at the end is the one which is removed first.
Even in computer programing the meaning of a stack is no different, it ensures that we remove the top elements first before we remove to the ones below it.
Theoretically it sounds good, but how do you implement a stack in a program ?
There are two ways of doing the same
i) Using arrays :
We use arrays to implement a stack if we already know the size of the stack and is fixed. It is preferred were speed is of more concern than amount of elements.
ii) Using linked lists :
Linked lists are preferred over arrays when we are not aware of the maximum size of the stack and availability of data is more important than speed.
In the above code we created a stack based on Linked list which does not need any upper limit as we did in arrays version.
Queues :
Like LIFO there is another similar concept called FIFO - First In First Out.
As the name explains itself, doesn't it apply to the Queue above in the picture ?
The first person in queue gets on the bus first and the last gets on last. In computer programming it is no different it ensures that the first element gets in first and the last gets in last.
Sounds good and simple so far ?
Let us now try to implement the same in a computer program
Once again there are two ways of implementing it
i) Using Arrays :
Arrays are known for its speed of access and are preferred when speed is of more importance than space.
Code :
ii) Using Linked Lists
Linked lists are known for its efficient usage of memory and ability to handle memory demand dynamically.
Code :
http://codepad.org/W5c58vwc
1) Can we implement 3 stacks using a single array ?
Yes there is a straight forward way in which we divide the array into 3 parts and use each one for a stack. This design could be highly space inefficient, i.e one stack could be completely full and the other can be empty.
Here is a design which will make use of all the available array space
We will have two arrays one with data and the other with pointer index to each stack.
Data Array : For each pouch operation two elements will be used one to obviously store data and the other to store the index of the next element.
Pointer Array : For a pop operation we look at the index of that stack in pointer array.
An empty stack will have a value of -1 in pointer array. An empty space in data array will have a index value of -2.
The Data array will hold the value of data at every even indexed places in data array and the value of next index of that stack. In the picture above we have stack 1 starting at index 0 in Data Array.
When we push another element into Stack 0, we will have a different index in Pointer Array.
Here is how the "Data Array" and "Pointer Array" will look like when all the stacks are empty.
When a stack is empty we will have a -1 in its corresponding index in "Pointer Array", instead if we have an empty space in "Data Array" we will have a -2 in its corresponding index location.
http://codepad.org/8Slda0f3
We can do this my maintaining a single stack and a variable which will hold the minimum value of the stack. But when we pop that minimum element we need to search through the stack to look for the next minimum, which defeats the purpose of have O(1) computational complexity.
If we have two stacks to implement this algorithm we can have the O(1) computational complexity.
Lets call the actual stack as data stack and the other as minimum stack, the below picture describes the algorithm.
We keep track of the latest minimum element in the Minimum Stack and push another element only if it is less than the least element in Minimum Stack. Unlike push operation on Minimum Stack we pop an element in Minimum Stack if it is poped from the Data Stack.
Here is the code for the same
http://codepad.org/6vA4B551
In the code above we create two separate classes "baseStack" and "StackWithMin". In StackWithMin we use the base stack to create two stacks to be used as "Data Stack" and "Minimum Stack". Rest of the algorithm is straight forward. Let me know if you have any questions.
4) As shown in the first picture on this page, if we have a lot of plates in a single stack it might topple. It does not happen in a real software stack, let us imagine it does happen. Can we make a stack which operates as a normal stack but would internally create a new stack each time a set threshold is set ? It should also be capable of performing push and pop operation on a particular stack.
This will require the concept of linked list in the other section of this blog. Pictorially this algorithm will look like this
Each node has a stack in itself, the counter in each node has a number indicating the number of elements in the stack. If the counter has a value of -1 it indicates that the node is empty.
The root node is the starting node. The code below has an implementation in C++.
http://codepad.org/Cr7iZwUM
The above code includes a lot of test cases and the code is self explanatory, you can contact me if you have any questions.
5) A tower of hanoi is a classic problem in which we have 3 pegs and N disks in descending from bottom to top. The task is to move all the disks from first peg to the third peg.
Tower of Hanio is a classic problem in which we move disks from one peg to another and move all the disks from a source peg to a destination peg. Tower of Hanoi is a mathematical puzzle where we have three pegs and N disks. The objective of the puzzle is to move the entire stack to another peg, obeying the following simple rules.
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only move from a peg if it is the upper most in the peg.
3) No disk may be placed on top of a smaller peg.
I am in a hurry, I dont have time for a picture, will post the same later guys. Here is the code.
http://codepad.org/a3qBoQLd
Next coming soon....
We now know about both stacks and queues, lets try some interesting ideas.
1) Can we implement 3 stacks using a single array ?
Yes there is a straight forward way in which we divide the array into 3 parts and use each one for a stack. This design could be highly space inefficient, i.e one stack could be completely full and the other can be empty.
Here is a design which will make use of all the available array space
We will have two arrays one with data and the other with pointer index to each stack.
Data Array : For each pouch operation two elements will be used one to obviously store data and the other to store the index of the next element.
Pointer Array : For a pop operation we look at the index of that stack in pointer array.
An empty stack will have a value of -1 in pointer array. An empty space in data array will have a index value of -2.
The Data array will hold the value of data at every even indexed places in data array and the value of next index of that stack. In the picture above we have stack 1 starting at index 0 in Data Array.
When we push another element into Stack 0, we will have a different index in Pointer Array.
Here is how the "Data Array" and "Pointer Array" will look like when all the stacks are empty.
When a stack is empty we will have a -1 in its corresponding index in "Pointer Array", instead if we have an empty space in "Data Array" we will have a -2 in its corresponding index location.
http://codepad.org/8Slda0f3
2) Can we implement a queue using a stack ?
We can clearly see that both are different concepts and one cannot be implemented using the other. But if we can use 2 stacks can we do that ? Yes we can.
We can clearly see that both are different concepts and one cannot be implemented using the other. But if we can use 2 stacks can we do that ? Yes we can.
In a queue we need to remove first inserted elements out first, in a stack we remove the last inserted element first. If I turn around the stack we can implement a queue using two stacks.
Enqueue Operation looks like this
For a dequeue operation we need to empty the main stack and fill the buffer, pop an element from the buffer and again empty the buffer and fill the main stack.
Pictorially it will look like this
http://codepad.org/eII1jBAR
Above is the code which implements a queue using two stacks.
Enqueue Operation looks like this
For a dequeue operation we need to empty the main stack and fill the buffer, pop an element from the buffer and again empty the buffer and fill the main stack.
Pictorially it will look like this
http://codepad.org/eII1jBAR
Above is the code which implements a queue using two stacks.
3) Let us now see how to implement a stack which has a min function in addition to push and pop and all of them should have a complexity of O(1) which is constant time.
We can do this my maintaining a single stack and a variable which will hold the minimum value of the stack. But when we pop that minimum element we need to search through the stack to look for the next minimum, which defeats the purpose of have O(1) computational complexity.
If we have two stacks to implement this algorithm we can have the O(1) computational complexity.
Lets call the actual stack as data stack and the other as minimum stack, the below picture describes the algorithm.
We keep track of the latest minimum element in the Minimum Stack and push another element only if it is less than the least element in Minimum Stack. Unlike push operation on Minimum Stack we pop an element in Minimum Stack if it is poped from the Data Stack.
Here is the code for the same
http://codepad.org/6vA4B551
In the code above we create two separate classes "baseStack" and "StackWithMin". In StackWithMin we use the base stack to create two stacks to be used as "Data Stack" and "Minimum Stack". Rest of the algorithm is straight forward. Let me know if you have any questions.
4) As shown in the first picture on this page, if we have a lot of plates in a single stack it might topple. It does not happen in a real software stack, let us imagine it does happen. Can we make a stack which operates as a normal stack but would internally create a new stack each time a set threshold is set ? It should also be capable of performing push and pop operation on a particular stack.
This will require the concept of linked list in the other section of this blog. Pictorially this algorithm will look like this
Each node has a stack in itself, the counter in each node has a number indicating the number of elements in the stack. If the counter has a value of -1 it indicates that the node is empty.
The root node is the starting node. The code below has an implementation in C++.
http://codepad.org/Cr7iZwUM
The above code includes a lot of test cases and the code is self explanatory, you can contact me if you have any questions.
5) A tower of hanoi is a classic problem in which we have 3 pegs and N disks in descending from bottom to top. The task is to move all the disks from first peg to the third peg.
Tower of Hanio is a classic problem in which we move disks from one peg to another and move all the disks from a source peg to a destination peg. Tower of Hanoi is a mathematical puzzle where we have three pegs and N disks. The objective of the puzzle is to move the entire stack to another peg, obeying the following simple rules.
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only move from a peg if it is the upper most in the peg.
3) No disk may be placed on top of a smaller peg.
I am in a hurry, I dont have time for a picture, will post the same later guys. Here is the code.
http://codepad.org/a3qBoQLd
Next coming soon....
You blog pictures are interesting! Thanks for taking time to find them, link for http://codepad.org/CI00RKWY is not clickable.
ReplyDelete