Let us discuss another important data structure i.e stack. Some examples of stacks in real life are stack of books, stack of plates etc. We can add new items at the top of the stack or remove them from the top. We can only access the elements of the stack at the top. Following is the definition of stacks.
“Stack is a collection of elements arranged in a linear order”.
Let’s see an example to understand this. Suppose we have some video cassettes. We took one cassette and put it on the table. We get another cassette and put it on the top of first cassette. Now there are two cassettes on the table- one at the top of other. Now we take the third cassette and stack it on the two. Take the fourth cassette and stack it on the three cassettes.
Now if we want to take the cassette, we can get the fourth cassette which is at the top and remove it from the stack. Now we can remove the third cassette from the stack and so on. Suppose that we have fifty cassettes stacked on each other and want to access the first cassette that is at the bottom of the stack. What will happen? All the cassettes will fell down. It will not happen exactly the same in the computer. There may be some problem. It does not mean that our data structure is incorrect. As we see in the above example that the top most cassette will be removed first and the new cassette will be stacked at the top. The same example can be repeated with the books. In the daily life, we deal with the stacked goods very carefully.
Now we will discuss how to create a stack data structure or a factory, going to create stack object for us. What will be the attributes of this object? During the discussion on the list, we came to know that a programmer adds values in the list, removes values from the list and moves forward and backward. In case of a stack too, we want to add things and remove things. We will not move forward or backward in the stack. New items can be added or removed at the top only. We can not suggest the removal of the middle element of the stack.
Let’s talk about the interface methods of the stacks. Some important methods are:
| Method Name | Description |
| push(x) | Insert x as the top element of the stack |
| pop() | Remove the top element of the stack and return it. |
| top() | Return the top element without removing it from the stack. |
The push(x) method will take an element and insert it at the top of the stack. This element will become top element. The pop() method will remove the top element of the stock and return it to the calling program. The top() method returns the top-most stack element but does not remove it from the stack. The interface method names that we choose has special objective. In case of list, we have used add, remove, get, set as the suitable names. However, for stack, we are using push, pop and top. We can depict the activity from the method name like push means that we are placing an element on the top of the stack and pushing the other elements down.
The example of a hotel’s kitchen may help understand the concept of stacks in a comprehensive manner. In the kitchen, the plates are stacked in a cylinder having a spring on the bottom. When a waiter picks a plate, the spring moves up the other plates. This is a stack of plates. You will feel that you are pushing the plates in the cylinder and when you take a plate from the cylinder it pops the other plates. The top method is used to get the top- most element without removing it.
When you create classes, interfaces and methods, choose such names which depicts what these method are doing. These names should be suitable for that class or factory.
Let’s discuss the working of stack with the help of a diagram.
 |
At the start, the stack is empty. First of all, we push the value 2 in the stack. As a result, the number 2 is placed in the stack. We have a top pointer that points at the top element. Then we said push(5). Now see how 2 and 5 are stacked. The number 5 is placed at the top of number 2 and the pointer top moves one step upward. Then we pushed the number 7 which is placed on the top and the number 2 and 5 are below. Similarly, we push number 1. The last figure in the first row shows the stacked values of the numbers- 1, 7, 5 and 2.
Let’s pop the elements from the stack. The first figure of second row shows the pop operation. As a result, the number 1 is popped. Than again we push the number 21 on the stack. The number 7, 5, and 2 are already in the stack and number 21 is pushed at the top. If we pop now, the number 21 is popped. Now number 7 is at the top. If we pop again, the number 7 is popped. Pop again and the number 5 is popped and number 2 remains in the stack. Here with the help of this diagram, we are proving that the values are added at the top and removed at the top in a stack.
The last element to go into the stack is the first to come out. That is why, a stack is known as LIFO (Last In First Out) structure. We know that the last element pushed in the stack is at the top which is removed when we call pop. Let’s see some other scenarios. What happens if we call pop() while there is no element? One possible way-out is that we have isEmpty() function that returns true if stack is empty and false otherwise. This is a boolean function that returns false if there is no element in the stack. Otherwise, it will return true. The second option is this that when we call pop on an empty stack, it throws an exception. This is a concept of advanced C++. Exception is also a way to convey that some unusual condition has arisen or something has gone wrong. Suppose, if we have a division method and try to divide some number with zero. This method will throw ‘division by zero’ exception. Currently we will not throw an exception but use the isEmpty() method. The user who is employing the stack is responsible to call the isEmpty() method before calling the pop. Call the pop method if isEmpty() returns false . Otherwise, there will be a problem.
For stack implementation using array, look at this article. For stack implementation through linked list, click here.
- Allocating and de-allocating memory for list nodes does take more time than pre-allocated array. Memory allocation and de-allocation has cost in terms of time, especially, when your system is huge and handling a volume of requests. While comparing the stack implementation, using an array versus a linked list, it becomes important to consider this point carefully.
- List uses as much memory as required by the nodes. In contrast, array requires allocation ahead of time. In the previous bullet, the point was the time required for allocation and de-allocation of nodes at runtime as compared to one time allocation of an array. In this bullet, we are of the view that with this runtime allocation and de-allocation of nodes, we are also getting an advantage that list consumes only as much memory as required by the nodes of list. Instead of allocating a whole chunk of memory at one time as in case of array, we only allocate memory that is actually required so that the memory is available for other programs. For example, in case of implementing stack using array, you allocated array for 1000 elements but the stack, on average, are using 50 locations. So, on the average, 950 locations remain vacant. Therefore, in order to resolve this problem, linked list is handy.
- List pointers (head, next) require extra memory. Consider the manipulation of array elements. We can set and get the individual elements with the use of the array index; we don’t need to have additional elements or pointers to access them. But in case of linked list, within each node of the list, we have one pointer element called next, pointing to the next node of the list. Therefore, for 1000 nodes stack implemented using list, there will be 1000 extra pointer variables. Remember that stack is implemented using ‘singly-linked’ list. Otherwise, for doubly linked list, this overhead is also doubled as two pointer variables are stored within each node in that case.
- Array has an upper limit whereas list is limited by dynamic memory allocation. In other words, the linked list is only limited by the address space of the machine. We have already discussed this point at reasonable length in this lecture.
Consider the expression A+B: we think of applying the operator “+” to the operands A and B. We have been writing this kind of expressions right from our primary classes. There are few important things to consider here:
Firstly, + operator requires two operators or in other words “+” is a binary operator.
Secondly, in the expression A+B, the one operand A is on left of the operator while the other operand B is on the right side. This kind of expressions where the operator is present between two operands called infix expressions. We take the meanings of this expression as to add both operands A and B.
There are two other ways of writing expressions:
- We could write +AB, the operator is written before the operands A and B. These kinds of expressions are called Prefix Expressions.
- We can also write it as AB+, the operator is written after the operands A and B. This expression is called Postfix expression.
The prefixes pre and post refer to the position of the operator with respect to the two operands.
Consider another expression in infix form: A + B * C. It consists of three operands A, B, C and two operator +,* . We know that multiplication () is done before addition (+), therefore, this expression is actually interpreted as: A + (B * C). The interpretation is because of the precedence of multiplication (*) over addition (+). The precedence can be changed in an expression by using the parenthesis. We will discuss it a bit later.
Let’s see, how can we convert the infix expression A + (B * C) into the postfix form. Firstly, we will convert the multiplication to postfix form as: A + (B C *). Secondly, we will convert addition to postfix as: A (B C *) + and finally it will lead to the resultant postfix expression i.e. : A B C * +. Let’s convert the expression (A + B) * C to postfix. You might have noticed that to overcome the precedence of multiplication operator (*) we have used parenthesis around A + B because we want to perform addition operation first before multiplication.
(A + B) * C infix form
(A B +) * C convert addition
(A B +) C * convert multiplication
A B + C * postfix form
These expressions may seem to be difficult to understand and evaluate at first. But this is one way of writing and evaluating expressions. As we are normally used to infix form, this postfix form might be little confusing. If a programmer knows the algorithm, there is nothing complicated and even one can evaluate the expression manually.
Stack Implementation: Array or Linked List
Since both implementations support stack operations in constant time, we will see what are the possible reasons to prefer one implementation to the other.- Allocating and de-allocating memory for list nodes does take more time than pre-allocated array. Memory allocation and de-allocation has cost in terms of time, especially, when your system is huge and handling a volume of requests. While comparing the stack implementation, using an array versus a linked list, it becomes important to consider this point carefully.
- List uses as much memory as required by the nodes. In contrast, array requires allocation ahead of time. In the previous bullet, the point was the time required for allocation and de-allocation of nodes at runtime as compared to one time allocation of an array. In this bullet, we are of the view that with this runtime allocation and de-allocation of nodes, we are also getting an advantage that list consumes only as much memory as required by the nodes of list. Instead of allocating a whole chunk of memory at one time as in case of array, we only allocate memory that is actually required so that the memory is available for other programs. For example, in case of implementing stack using array, you allocated array for 1000 elements but the stack, on average, are using 50 locations. So, on the average, 950 locations remain vacant. Therefore, in order to resolve this problem, linked list is handy.
- List pointers (head, next) require extra memory. Consider the manipulation of array elements. We can set and get the individual elements with the use of the array index; we don’t need to have additional elements or pointers to access them. But in case of linked list, within each node of the list, we have one pointer element called next, pointing to the next node of the list. Therefore, for 1000 nodes stack implemented using list, there will be 1000 extra pointer variables. Remember that stack is implemented using ‘singly-linked’ list. Otherwise, for doubly linked list, this overhead is also doubled as two pointer variables are stored within each node in that case.
- Array has an upper limit whereas list is limited by dynamic memory allocation. In other words, the linked list is only limited by the address space of the machine. We have already discussed this point at reasonable length in this lecture.
Use of Stack
Examples of uses of stack include- traversing and evaluating prefix, infix and postfix expressions.Consider the expression A+B: we think of applying the operator “+” to the operands A and B. We have been writing this kind of expressions right from our primary classes. There are few important things to consider here:
Firstly, + operator requires two operators or in other words “+” is a binary operator.
Secondly, in the expression A+B, the one operand A is on left of the operator while the other operand B is on the right side. This kind of expressions where the operator is present between two operands called infix expressions. We take the meanings of this expression as to add both operands A and B.
There are two other ways of writing expressions:
- We could write +AB, the operator is written before the operands A and B. These kinds of expressions are called Prefix Expressions.
- We can also write it as AB+, the operator is written after the operands A and B. This expression is called Postfix expression.
The prefixes pre and post refer to the position of the operator with respect to the two operands.
Consider another expression in infix form: A + B * C. It consists of three operands A, B, C and two operator +,* . We know that multiplication () is done before addition (+), therefore, this expression is actually interpreted as: A + (B * C). The interpretation is because of the precedence of multiplication (*) over addition (+). The precedence can be changed in an expression by using the parenthesis. We will discuss it a bit later.
Let’s see, how can we convert the infix expression A + (B * C) into the postfix form. Firstly, we will convert the multiplication to postfix form as: A + (B C *). Secondly, we will convert addition to postfix as: A (B C *) + and finally it will lead to the resultant postfix expression i.e. : A B C * +. Let’s convert the expression (A + B) * C to postfix. You might have noticed that to overcome the precedence of multiplication operator (*) we have used parenthesis around A + B because we want to perform addition operation first before multiplication.
(A + B) * C infix form
(A B +) * C convert addition
(A B +) C * convert multiplication
A B + C * postfix form
These expressions may seem to be difficult to understand and evaluate at first. But this is one way of writing and evaluating expressions. As we are normally used to infix form, this postfix form might be little confusing. If a programmer knows the algorithm, there is nothing complicated and even one can evaluate the expression manually.
No comments:
Post a Comment