Lets implement the stack using the arrays. The stack shown in the below diagram may be considered as an array. Here the array is shown vertically. We can implement the stack using array. The interface will remain as push and pop methods. The user of the stack does not need to know that the stack is internally implemented with the help of array. The worst case for insertion and deletion from an array may happen when we insert and delete from the beginning of the array. We have to shift elements to the right for insertion and left for removal of an element. We face the same problem while implementing the list with the use of the array. If we push and pop the elements from the start of the array for stack implementation, this problem will arise. In case of push, we have to shift the stack elements to the right. However, in case of pop, after removing the element, we have to shift the elements of stack that are in the array to the left. If we push the element at the end of the array, there is no need to shift any element. Similarly as the pop method removes the last element of the stack which is at the end of the array, no element is shifted. To insert and remove elements at the end of the array we need not to shift its elements. Best case for insert and delete is at the end of the array where there is no need to shift any element. We should implement push() and pop() by inserting and deleting at the end of an array.
 |
In the above diagram, on the left side we have a stack. There are four elements in the stack i.e. 1, 7, 5 and 2. The element 1 is the extreme-most that means that it is inserted in the end whereas 7, 5, and 2 have been added before. As this is a LIFO structure so the element 1 should be popped first. On the right side we have an array with positions 0, 1, 2, 3 and so on. We have inserted the numbers 2, 5, 7 and 1. We have decided that the elements should be inserted at the end of the array. Therefore the most recent element i.e. 1 is at position 3. The top is the index representing the position of the most recent element. Now we will discuss the stack implementation in detail using array.
We have to choose a maximum size for the array. It is possible that the array may ‘fill-up’ if we push enough elements. Now more elements cannot be pushed. Now what should the user of the stack do? Internally, we have implemented the stack using array which can be full. To avoid this, we write isFull() method that will return a boolean value. If this method returns true, it means that the stack (array) is full and no more elements can be inserted. Therefore before calling the push(x), the user should call isFull() method. If isFull() returns false, it will depict that stack is not full and an element can be inserted. This method has become the part of the stack interface. So we have two more methods in our interface i.e. isEmpty() and isFull().
Now we will discuss the actual C++ code of these operations. These methods are part of stack class or stack factory. We have an array named A while current is its index. The code of pop() method is as:
| int pop() { return A[current--]; } In this method, the recent element is returned to the caller, reducing the size of the array by 1. The code of push method is: void push(int x) { A[++current] = x; } |
We know that ++current means that add one to the current and then use it. That also shows that element x should be inserted at current plus one position. Here we are not testing that this current index has increased from the array size or not. As discussed earlier that before using the push method, the user must call isFull() method. Similarly it is the responsibility of the user to call the isEmpty() method before calling the pop method. Therefore there is no if statement in the push and pop method.
The code of the top() method is:
| int top() { return A[current]; } This method returns the element at the current position. We are not changing the value of current here. We simply want to return the top element. int isEmpty() { return ( current == -1 ); } This method also tests the value of the current whether it is equal to -1 or not. Initially when the stack is created, the value of current will be -1. If the user calls the isEmpty() method before pushing any element, it will return true. int isFull() { return ( current == size-1); } |
This method checks that the stack is full or not. The variable size shows the size of the array. If the current is equal to the size minus one, it means that the stack is full and we cannot insert any element in it.
We have determined the cost and benefit of all the data structures. Now we will see how much time these methods take. A quick examination shows that all the five operations take constant time. In case of list, the find method takes too much time as it has to traverse the list. Whereas the add and remove methods are relatively quick. The methods of stack are very simple. There is no complexity involved. We insert element at one side and also remove from that side not in the middle or some other place. Therefore we need not to carry out a lot of work. During the usage of the array, the stack methods push, pop, top, isFull and isEmpty all are constant time operations. There is not much difference of time between them.
The complete code of the program is:
| /* Stack implementation using array */ #include <iostream.h> /* The Stack class */ class Stack { public: Stack() { size = 10; current = -1;} //constructor int pop(){ return A[current--];} // The pop function void push(int x){A[++current] = x;} // The push function int top(){ return A[current];} // The top function int isEmpty(){return ( current == -1 );} // Will return true when stack is empty int isFull(){ return ( current == size-1);} // Will return true when stack is full private: int object; // The data element int current; // Index of the array int size; // max size of the array int A[10]; // Array of 10 elements }; // The main method int main() { Stack stack; // creating a stack object // pushing the 10 elements to the stack for(int i = 0; i < 12; i++) { if(!stack.isFull()) // checking stack is full or not stack.push(i); // push the element at the top else cout <<"\n Stack is full, can't insert new element"; } // pop the elements at the stack for (int i = 0; i < 12; i++) { if(!stack.isEmpty()) // checking stack is empty or not cout << "\n The popped element = " << stack.pop(); else cout <<"\n Stack is empty, can't pop"; } } |
The output of the program is:
| Stack is full, can't insert new element Stack is full, can't insert new element The popped element = 9 The popped element = 8 The popped element = 7 The popped element = 6 The popped element = 5 The popped element = 4 The popped element = 3 The popped element = 2 The popped element = 1 The popped element = 0 Stack is empty, can't pop Stack is empty, can't pop |
However, a programmer finds the size-related problems in case of an array. What should we do when the array is full? We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements.
No comments:
Post a Comment