Introduction

In this article we will discuss one of the most useful linear data structure – Stack as well as its implementation in C language and C++ languages. Firstly we will implement the algorithms used in stacks in C language and then we will study stacks in C++ using templates. We will also discuss why stacks play an important role in computer science.

Definition and Examples

A stack is a collection of elements in which all insertions and deletions are made at one end, called the top of the stack. It means that new elements are inserted at the ‘top’ of stack and elements are also deleted from the ‘top’ of the stack. Therefore it is the ‘top’ of stack that changes whenever an element is inserted or deleted. A stack of trays or of plates is a simple example of stack, as shown in figure-1.

Figure 1

When we use the word ‘stack’ in a programming context then one should remember that the elements of a stack should be of similar data types and these elements can be of either built-in data types or user-defined data types. Figure-2 is a motion picture of a stack as it expands and shrinks with the passage of time. If a stack has five elements, say A, B, C, D and E, then it is represented as shown in figure-2(a). From this figure it is clear that the element ‘E’ is at the topmost position of stack and ‘A’ is at the bottom most position.Now if we want to insert a new element ‘F’ then after the insertion, the element ‘F’ will be the top element of the stack as shown in figure-2(b).

Again if we want to insert another element then it will be placed on the top of ‘F’. Figure-2(c) represents insertion of two new elements ‘G’ and ‘H’ respectively. Now if we want to delete any element from the stack then ‘H’ will be the first element to be deleted. Figure-2(d) shows the deletion of a element from the stack. From the pictorial representation of figure-2, it is clear that the last element to be inserted into a stack is the first element to be deleted. That’s why the stack is also called as Last-In First-Out (LIFO) data structure.

Figure 2

Operations on Stacks

Generally we perform two basic operations onto a stack – push and pop. When we insert a new element to a stack, it is called as pushed onto the stack and when we delete an element, it is called as popped from the stack. Because of this operation, a stack is also called as Push-down lists. For example, if ‘S’ represent a stack and ‘item’ represents an element to be pushed then the push operation is written as:

 

Push(S, item); 

Similarly when we pop an element from a stack, it is represented as:

item = Pop(S) 

where ‘S’ represents a stack. For example, if ‘S’ is the stack of figure-2(a) we perform the following operations from 2(b) to 2(d).

Push(S, ‘F’);
Push(S, ‘G’);
Push(S, ‘H’);
Pop(S) 

However we can also perform some other operations on stacks as:

Intialize(S) – Initializes a stack S as an empty stack

StackTop(S) – returns the top element of stack S without removing it from the stack

IsStackFull(S) – checks whether  the stack is full or not. If the stack is full then returns 1; otherwise returns 0.

IsStackEmpty(S) - checks whether  the stack is empty or not. If the stack is empty then returns 1; otherwise returns 0.

The StackTop(S) function returns the top element of stack, only when the stack is not empty. If the stack is empty then it is not possible to return the top element. Similarly a Pop(S) function is possible only when the stack is not empty. Actually the StackTop() is not a new operation since it can be decomposed into a Pop() and Push(). Thus

item = StackTop(S); 

is decomposed into following two operations:

item = Pop(S);
 Push(S, item); 

Therefore before performing these two operations, we must ensure that the stack is not empty by invoking IsStackEmpty() function. Likewise a new element is inserted only when the stack is not full and it is ensured by invoking IsStackFull() function.

Therefore when we build a stack then it is necessary to implement these six operations.

Implementation of Stacks in C

In this section we will study how to represent a stack in a programming language ‘C’. However there are several ways to represent a stack in ‘C’. We can use either an array or a linked list while implementing a stack. Firstly we will see array implementation of stacks.

Array Implementation of Stacks

A stack is an ordered collection of elements. We know that an array contains an ordered collection of elements. Therefore a stack may be represented as a linear array in the computer memory that will store the elements in the stack. Therefore whenever we use array implementation of stack, we attempt to begin a program by declaring a variable ‘Stack’ as an array. We will also use a counter variable ‘top’ to indicate the current top element’s position within array. One end of the array is fixed, say bottom of the stack, while the value of ‘top’ constantly changes as elements are pushed and popped. In this type of implementation, we will also use another simple variable ‘Size’ to indicate the maximum number of elements that can be held by the stack.

A stack in ‘C’ is represented as

 

#define Size 50
int top;
datatype Stack[Size]; 

Here we have used ‘Stack’ as an array name. However a stack and an array ‘Stack’ are two entirely different things. In general, one can not change the number of elements in an array because it is fixed and assigned by the declaration for the array. On the other hand, a stack is fundamentally a dynamic object whose size is constantly changing as items are pushed and popped. So we declare an array as there is enough space for the maximum size of the stack because the stack may grow and shrink within the space reserved for it.

In the above declaration, ‘Size’ is a constant giving the maximum number of elements allowed for stack, such that the stack will at no time contains more than Size elements (50 elements). In this example, the stack can contain 50 elements (from stack[0] to Stack[49]). The datatype is the type describing the data that will be put into the stack and ‘top’ is an integer variable to indicate the location of the top element of the stack. If the value of top is equal to –1 then it means that the stack is empty; otherwise not. Similarly if the value of top is equal to (Size-1), that is 49, then it means that the stack is full; otherwise not.

Here is the declaration for a stack of 50 integers:

 

#define Size 50
int top;
int Stack[Size]; 

There is, of course, no reason to restrict a stack to contain only integers, we can also declare as:

 

float Stack[Size];
char Stack[Size]; 

We can even construct a stack of user-defined data types, such as struct, as:

 

#define Size 50
int top;
struct Employee
{ 
 char name[25];
int age;
float salary;
};
struct Employee Stack[Size]; 

In fact, should the need arise, a stack can contain objects of different types by using ‘C’ unions. But for the sake of simplicity we will consider a stack of integers only. Figure-3 shows an array implementation of such stack.

Figure 3

Here the value of ‘top’ is 5. It means that there are six elements in the stack. It is because in ‘C’ and C++ array numbering starts from 0 and since Size is equal to 50 therefore we can push forty four more elements in the stack.

Now let us see some routines that are to be performed on stacks.

Initializing an Empty Stack

The Initialize() function is used to initialize a stack to empty before it is first used in a program. A stack is initialized by assigning value –1 to ‘top’ variable.

Here is the function that implements this task.

Initialize()
{
 top=-1;
}

Is Stack Full or Not

When we insert an element onto the stack, then firstly we check whether the stack is full or not. If the stack is not full then the new element is inserted successfully; otherwise an error message is reported. Therefore while implementing this task we must check the value of ‘top’. If the value of ‘top’ is equal to (Size-1) then it means that the stack is full; otherwise not.

Here is the function that implements this task.

IsStackFull()
{
 if (top==Size-1)
 return 1;
 else
 return 0;
}

Is Stack Empty or Not

This condition is tested whenever we attempt to perform a pop operation. An element is removed from the stack only when the stack is not empty. Here again while implementing this task we must check the value of ‘top’. If the value of ‘top’ is equal to -1 then it means that the stack is empty;  otherwise not.

Here is the function that implements this task.

IsStackEmpty()
{
 if (top==-1)
 return 1;
 else
 return 0;
}

Now the question arises – what is the need to define the function IsStackEmpty() when we could just as easily write if (top == -1) each time we want to test for the empty condition? There is no complicated reason behind this. Of course one can write if (top == -1) each time, but a good programmer wishes to make his/her program more comprehensible as well as concern with the readability of his/her code. It will definitely save a large amount of time in debugging the program because large-and-medium sized program will almost never be correct the first time they are run. Therefore if you want to be a mature programmer then concern with the proper balance of code economy and code clarity.

Pop Operation

When we implement Pop() operation we should consider the situation where we try to perform the pop operation on an empty stack. If our stack is empty and we perform pop operation then it should display just an error message that “Stack is Underflow” and the control is returned back. However if the stack is not empty then the top element of the stack is stored in a temporary local variable and the value of the ‘top’ is decremented. Finally this retrieved value is returned back.

Here is the algorithm that pops an element from the non-empty stack.

Algorithm : Pop

Pop(Stack)

Here ‘Stack’ contains the base address of the array ‘Stack’.

• Step-1 : Check whether Stack is empty or not. If Stack is empty then flash an error message – Stack underflow and go to step-4 otherwise go to step-2
• Step-2 : Access the top element of the stack as: Item = Stack[top]
• Step-3 : Decrement the value of top as top = top-1
• Step-4 : Exit

Here is the ‘C’ implementation of this algorithm.

Implementation : Pop

Pop(int Stack[])
{
 int item;
 if (IsStackEmpty())
 {
 printf("\nStack Underflow. ");
exit(0);
 }
 item=Stack[top];
 top--;
 return (item);
}

This Pop() function can be used as:

item = Pop(Stack); 

Here ‘item’ contains the value popped from the stack. Of course the programmer should ensure that the stack is not empty when the Pop() operation is called. If the programmer is not known to the state of the stack, its status may be determined by the coding

if (!IsStackEmpty())
 item = Pop(Stack);
else
/* Take some remedial action because stack is empty */

However if programmer calls Pop() function knowingly or unknowingly with an empty stack then it will definitely terminate the execution of a program in the middle of its execution. Therefore it is totally programmer’s responsibility to consider the possibility of error and diagnose this error.

Testing for Exceptional Condition

However it might be more desirable for the Pop() function to signal the calling program that an underflow has occurred. The calling function upon detecting this signal can take appropriate remedial action. For this we will take another variable ‘flag’ which is initially set to 0. This variable is set to 1 only when we try to pop an element from an empty stack.

Let we name such function PopAndTest. Here is the definition of PopAndTest() function which pops and returns an indication whether an underflow has occurred.

PopAndTest(int Stack[], int *item, int *flag)
{
 if (IsStackEmpty())
 {
 *flag = 1;
 return;
 }
 *flag = 0;
 *item = Stack[top];
 top --;
}

The following code segment uses this above function as:

PopAndTest(Stack, &item, &flag);
if (flag == 1)
{
 /* Take some remedial action because stack was empty */
}
else
 /* Use value of item */
….

Push Operation

When we push an element onto a stack then we must first check whether the stack is full or not. If the stack is full then there is no place in the stack and the result of such an attempt is called an overflow. Therefore it should display just an error message – Stack is overflow and the control is returned back. If the stack is not full then the value of ‘top’ is incremented first and in last the new element is inserted at this new top position of the stack.

Here is the algorithm that pushes an item into a stack.

Algorithm : Push

Push(Stack, item)

Here ‘Stack’ contains the base address of the array ‘Stack’ and ‘item’ be the item to be pushed.

• Step-1 : Check Stack is full or not.  If Stack is full then flash an error message – Stack  overflow and go to step-4;otherwise go to step-2
• Step-2 : Increment the value of top as top = top+1
• Step-3 : Store the value of ‘item’ at top position a Stack[top] = item
• Step-4 : Exit

Here is the ‘C’ implementation of this algorithm.
Implementation : Push

Push(int Stack[], int item)
{
 if (IsStackFull())
 {
 printf("\nStack Overflow");
 exit(0);
 }
 top++;
 Stack[top]=item;
}

In this function, we have called another function IsStackFull() which is used to test whether the stack is full or not. Here again if and when an overflow is detected, nothing could be pushed onto stack and execution of the program terminates immediately after an error message is displayed. In such case, the programmer must take some remedial action as we have seen in PopAndTest function. Let we call such push function as PushAndTest. Here is the implementation of PushAndTest().

PushAndTest(int Stack[], int item, int *flag)
{
 if (IsStackFull())
 {
 *flag = 1;
 return;
 }
 *flag = 0;
 top++;
 Stack[top]=item;
}

The following code segment uses this above function as:
PushAndTest(Stack, item, &flag);
if (flag == 1)
{
/* Take some remedial action because item was not pushed on stack */
}
else
/* Item was successfully pushed on the stack */
….
Accessing Top Element of Stack

Sometimes we need to retrieve the top element of the stack without removing it from the stack. This operation is also called as ‘peek’ operation. Here it is also necessary to check firstly that the stack is empty or not. If not, then the topmost element is retrieved immediately; otherwise an error message is reported.

Remember that accessing top most element is not a primitive operation, because it can be decomposed into two operations as:

item=Pop(Stack);
 Push(Stack,item); 

But it does not look good to retrieve the top element first and then push it back. Therefore we must write another function StackTop() to access the top most element.

Here is the algorithm that returns the topmost element of the stack. 

Algorithm : StackTop

StackTop(Stack)

Here ‘Stack’ contains the base address of the array ‘Stack’.

• Step-1 : Check Stack is empty or not. If Stack is empty then flash an error message – Stack underflow and go to step-3; otherwise go to step-2
• Step-2 : Access the topmost value of the Stack as: Item = Stack[top] and return it.
• Step-3 : Exit

Here is the ‘C’ implementation of this algorithm.
Implementation : StackTop

StackTop(int Stack[])
{
 int item;
 if (IsStackEmpty())
 {
 printf("\nStack Underflow. ");
 exit(0);
 }
 item=Stack[top];
 return (item);
}

We can also write StackTopAndTest() function in order to consider the case when the stack is empty and we try to know top most element of the stack.

Here is the function that implements this task.

StackTopAndTest(int Stack[], int *item, int *flag)
{
 int item;
 if (IsStackEmpty())
 {
 *flag = 1;
 return;
 }
 *flag = 0;
 *item = Stack[top];
}

Traversing a Stack

While traversing a stack we process each element of a stack exactly once.

Here is the algorithm that traverse a stack.

Algorithm : Traverse

Traverse(Stack)

Here ‘Stack’ contains the base address of the array ‘Stack’.

• Step-1 : Check Stack is empty or not. If Stack is empty then flash an error message – Stack underflow and go to step-6; otherwise go to step-2
• Step-2 : Initialize i=top
• Step-3 : Repeat through step-5 while (i>=0)
• Step-4 : Access the value stored at ith position as: tem = Stack[i]
• Step-5 : Decrement the value of ‘i’ as i=i-1
• Step-6 : Exit

Here is the ‘C’ implementation of this algorithm:

Implementation : Traverse

Traverse(int Stack[])
{
 int i;
 if (IsStackEmpty())
 {
 printf("\nStack Underflow. ");
 return;
 }
 for(i=top; i>=0; i--)
 printf("\n%d",Stack[i]);
}

Linked List Implementation of Stacks

We have already studied – array implementation of a stack. Since an array is a static data structure, so when a stack uses an array, it automatically inherits this static image of array. Therefore there is always a limit while we are inserting new elements. So in that implementation we have to declare how many elements can be inserted into the stack? This limitation is overcome by implementing a stack using a linked list.

The operation of inserting a new element as a first node is quite similar to that of pushing an element onto a stack. Similarly the deletion of a first element is similar to that of popping an element from a stack. Therefore a linked list can also represent a stack and such a stack is known as a linked stack.

While studying a singly linked list, we have used the header (a pointer variable) ‘first’ for a linked list which contains either a NULL value (if the list is empty) or the address of first node of the list. While implementing a stack using linked list we call this header as a ‘top’ pointer variable, which contains either a NULL (if stack is empty) or address of topmost node.

Declaration of a Stack Node

Like linked list, each element contains not only the item of information but also a pointer to the next element in the linked stack. The node of a linked stack is defined as:

struct StackNode
{
 int data;
 struct StackNode *link;
};
typedef struct StackNode StackNode;

and the ‘top’ pointer variable is declared as:

 StackNode *top; 

Initially the value of ‘top’ is set to NULL as:

top = NULL; 

Like linked list, we can easily find the end of a linked stack. Since each node contains a pointer to the next node, the link field of last node contains a special value NULL. So we can easily go through one node to next until it encounters a NULL value.

Figure-4 shows a stack implementation as a linked list. This linked stack consists of four nodes. In a linked stack there is no limitation on number of elements. Now let us see various operation performed on a linked stack.

Figure 4

Initializing an Empty Stack

The InitializeStack() function is used to initialize a stack to empty before it is first used in a program. A stack is initialized by assigning a value NULL to ‘top’ pointer variable. Here is the function that implements this task.

InitializeStack(StackNode **top)
{
 (*top)=NULL;
}

Is Stack Full or Not

Since a linked stack is implemented by using a linked list which can expand and shrink according to the situation. So as far as the memory space is available there is no need to worry about the number of elements to be inserted. However if there is no enough memory space then it is not possible to insert a new element. In such case, the function should return a value 1; otherwise 0.

This task is implemented as:

IsStackFull(StackNode *t)
/* This function returns 1, if the linked stack is full; otherwise return 0 */
{
 if (t==NULL)
 return 1;
 else
 return 0;
}

Is Stack Empty or Not

The linked stack is said to be empty only when the value of ‘top’ variable contains a NULL value. If it contains a NULL value then it returns a value 1; otherwise a value 0 is returned. Here is the function that implements this task.

IsStackEmpty(StackNode *t)
/* This function returns 1, if the linked stack is empty; otherwise return 0 */
{
 if (t==NULL)
 return 1;
 else
 return 0;
}

Popping a Node

It is equally simple to pop a node from a linked stack. In popping the stack we will firstly check whether the stack is empty or not. If the stack is empty then it displays an error message and the control is returned back. If the stack is not empty then we store the value ‘top’ variable in a temporary pointer variable ‘temp’, update the value of top and free the memory space occupied by the pointer variable ‘temp’.

Here is the algorithm, which pops a node from a non-empty linked stack.

Algorithm : PopNode

PopNode(&top)

Here ‘top’ is address of topmost node of the linked stack. Parameter ‘top’ is passed by reference (pointer to pointer) to allow it to change during insertion into an empty linked stack.

• Step-1 : Check whether the stack is empty of not. If the stack is empty then flash an error messag “Stack is Underflow” and go to step-6; otherwise go to step-2
• Step-2 : Store value of topmost node in a temporary, Pointer variable ‘temp’ as temp = (*top);
• Step-3 : Access the data field of ‘temp’ node as item = temp->data
• Step-4 : Update the value of ‘top’ as (*top) = (*top)->link;
• Step-5 : Free the memory space occupied by the temp  node as freenode(temp);
• Step-6 : Exit

Here is the function that implements this task:

Implementation : PopNode

PopNode(StackNode **top)
{
 StackNode *temp;
 int item;
 if (IsStackEmpty(*top))
 {
 printf("\nStack Underflow");
exit(0);
 }
 temp=(*top);
 item=temp->data;
 (*top)=(*top)->link;
 freenode(temp);
 return (item);
}

Like PopAndTest(), PopNode() must also consider the situation where item was not popped from stack successfully due to its underflow condition. So I leave the implementation of PopNodeAndTest() as an exercise for the students.

Pushing a Node

When we push (insert) a node onto a stack, we pass the address of ‘top’ pointer variable and the value of ‘item’. The value of top is either a NULL or address of topmost node and ‘item’ is the item of information we want to push onto a stack. To achieve this we will firstly create a new node and then insert at the top position of the linked stack.

Here is the algorithm that pushes a node into a linked stack.

Algorithm : PushNode

PushNode(&top, int item)

Here ‘top’ is address of topmost node of the linked stack and ‘item’ be the item to be pushed into the stack. Parameter ‘top’ is passed by reference (pointer to pointer) to allow it to change during insertion into a linked stack and ‘item’ is passed by value.

Step-1 : Create a new node ‘temp’
Step-2 : Set the data field of ‘temp node to item as
temp->data = item
Step-3 : Store the value of ‘top’ variable in the link field of new node as temp->link = (*top)
Step-4 : Update the value of ‘top’
Step-5 : Exit

Here is the ‘C’ implementation of this algorithm.

Implementation : PushNode

PushNode(StackNode **top, int item)
{
 StackNode *temp;
 temp = getnode();
 temp->data=item;
 temp->link=(*top);
 (*top)=temp;
}

Accessing Top Element of Stack

We can also access the top element of the linked stack without removing it from the stack. Here we will also consider the situation whether the stack is empty or not. If the stack is empty then we can not access the top element of it.

Here is the algorithm that implements this task.

Algorithm : StackTopNode
StackTopNodee(top)

Here ‘top’ is value of topmost node of the linked stack.

• Step-1 :     Check whether the stack is empty of not. If the stack is empty then flash an error messa ge “Stack is Underflow” and go to step-6;  otherwise go to step-2
• Step-2 : Store value of topmost node in a temporary. Pointer variable ‘temp’ as temp = (*top);
• Step-3 : Access the data field of ‘temp’ node as
• item = temp->data and return it.
• Step-4 : Exit

The ‘C’ implementation of this function is as:

Implementation : StackTopNode

StackTopNode(StackNode *top)
{
 int item;
 if (IsStackEmpty(top))
 {
 printf("\nStack Underflow");
exit(0);
 }
 item=top->data;
 return (item);
}

I leave the implementation of StackTopNodeAndTest() for the student.

Traversing a Linked Stack

While traversing a linked stack we process each element of a stack exactly once.
Here is the algorithm that traverses a linked stack.

Algorithm : Traverse
Traverse(top)

Here ‘top’ is address of topmost node of the linked stack. Parameter ‘top’ is passed by value. 

• Step-1 : Check whether the stack is empty of not. If the stack is empty then flash an error message “Stack is Underflow” and go to step-5;otherwise go to step-2
• Step-2 : Repeat through step-  while (top != NULL)
• Step-3 : Access the data field of ‘top’ node as
• item = top->data
• Step-4 : Update the value of ‘top’ as top = top->link;
• Step-5 : Exit

Here is the function that implements this task:

Implementation : Traverse

Here is the ‘C’ implementation of this algorithm:

Traverse(StackNode *top)
{
 if (IsStackEmpty(top))
 {
 printf("\nStack is empty. ");
 return;
 }
 while (top!=NULL)
 {
 printf("\n%d",top->data);
 top=top->link;
 }
}

Disposing a Linked Stack

As stated earlier a linked stack is a collection of dynamically allocated nodes. Therefore we must free the memory occupied by these nodes, if not in use.

Here is the algorithm which disposes a linked list.

Algorithm : DisposeStack

DisposeStack(&top)

Here ‘top’ is address of topmost node of the linked stack. Parameter ‘top’ is passed by reference (pointer to pointer) to allow it to change during its disposal of stack nodes. 

• Step-1 : Store value of topmost node in a temporary
• pointer variable ‘current’ as current = (*top)
• Step-2 : Repeat through step-5  while (current != NULL)
• Step-3 : Update the value of ‘current’ as:
• current = current->link;
• Step-4 : Free the memory space occupied by the temp  node as freenode(*top);
• Step-5 : Set (*top) = current
• Step-6 : Exit

Here is the ‘C’ implementation of this algorithm:

Implementation : DisposeStack

DisposeStack(StackNode **top)
{
 StackNode *current;
 current = (*top);
 while (current != NULL)
 {
 current = current->link;
 freenode(*top);
 (*top) = current;
 }
}

Applications of Stacks

In this section we will study some applications of stacks.

Stack Frames for Subprograms/Functions

Stacks are more commonly used within the computer system when functions are called. When a function is called within another function then the system should remember the location from where the call was made, so that it can return thereafter the called function is completed. Here it is also needed to remember the parameters and local variables of the calling function so that their values will not be lost while its execution resumes.

Suppose that we have four functions first(), second(), third() and forth() and suppose that first calls second, second calls third and third calls forth. The execution of third will not have completed until forth has finished and return. Similarly the execution of second will not have completed until third has finished and return. In the same fashion, the execution of first will not have completed until second has finished and return. 

Similar process takes place when a program uses recursion. In recursion whenever a function call is made, it is necessary to save the current values of parameters, local variables, and the return address of each successive call.

Now let us see another practical application of stacks – evaluation of arithmetic expression.

Evaluation of Arithmetic Expressions

Let we have an arithmetic expression as:
A+B*C

here A, B and C are one letter operands and ‘+’ and ‘*’ are operators. You can also have any legal variable name or constant in a programming language. The value of these operands must be consistent with the operations performed on them. As far as the operators are concerned, the ‘C’ language provides five basic arithmetic operators: plus(+), minus (-), multiply (*), divide (/) and modulus (%). However some other languages may also have an exponential (**) operation.

In a simple expression, such as

A+B

there occurs no problem with understanding the meaning of operation. The problem comes when an expression an expression has two or more than two operators as:

A+B*C

here the system faces a problem in deciding the order of the execution of the operators. It means that either addition operation is performed first and then multiplication or multiplication operation is performed first and then addition. To overcome this problem, the compiler sets a priority level for each arithmetic operator as shown in table-1.

Operators    Priority
*              2
/              2
%             2
+             1
-               1

Therefore while evaluating the expression

A+B*C

The multiplication operation (B*C) is carried out first and then its result is added to A. Let we have an expression where two adjacent operators have the same priority, such as A/B*C then generally the operators are evaluated left to right, that is A/B is evaluated first and then its result is multiplied by C. But one should remember that parentheses can override these rules.

For example, in the expression (A+B)*C the expression A+B is evaluated first and then its result is multiplied with C. If we have nested parentheses as A*(B/(C+D)) then innermost parenthesized expression is evaluated first. But within parentheses, the same rule of precedence applies. It means that in following expression

A*(B+C/D)

The expression C/D is evaluated first, then addition is performed and finally the result is multiplied to A.

Generally when we write an expression, the operator is placed between its two operands (as we have seen so far). Such an expression is called as ‘infix’ expression and this notation is called as infix notation. Here are some examples of infix expressions:

A*B
A+B/C
(A+B)*(C-D)
A-B/(C*D) 

The infix expressions are evaluated according to standard operator-precedence rule. Now the question arises-how can a compiler produce correct code of this infix expression? Actually when a compiler encounters an infix expression, it firstly translates this infix expression into a ‘postfix’ expression. In postfix expression the operator follows its two operands. In other words you can say that in postfix notation the operator is placed after its two operands. The process of writing the operators of an expression either before their operands or after them is called ‘Polish’ notations in honor of its discoverer, the Polish mathematician Jan Luksiewicz.  When we convert an infix expression to a postfix expression we need to remember that highest precedence is converted first and then lower precedence.

Consider the following scenario in which a simple infix expression is converted into a postfix expression.

A+B*C            Infix expression
A+(BC*)        Converting the multiplication
A(BC*)+        Converting the addition
ABC*+            Postfix expression

Now let us see how to convert a bit complex ‘infix’ expression into a ‘postfix’ expression, such as:

A * B / C + D – E * F

Here firstly we will parenthesize this expression according to the operator priority precedence as:

( ( ( ( A * B ) / C ) + D ) – ( E * F ) )

Now we move all operators to their corresponding right parenthesize and in last we delete all parentheses.

Here the arrows head point to the right parenthesize of the corresponding operator. Therefore the resulting postfix expression is as….

A B * C / D + E F * -

Converting an Expression from Infix to Postfix

As stated earlier the expressions within innermost parenthesis must first be converted to postfix. So when we devise an algorithm we need to remember two things – firstly read the expression and parenthesize it correctly and secondly moves the operators to their right parentheses. Now let us see the function InfixToPostfix() that implements this task.

InfixToPostfix(char infix[], char postfix[])
{
 int in=0,out=0,length;
 char ch;
 length=strlen(infix);
 while (in < length)
 {
 if (infix[in]== ' ' || infix[in]=='\t')
 {
 in++;
 continue;
 }
 else if (IsOperand(infix[in]))
 {
 postfix[out]=infix[in];
 out++;
 in++;
 }
 else if (infix[in]=='(')
 {
 Push(Stack,infix[in]);
 in++;
 }
 else if (infix[in] == ')')
 {
 ch = pop(Stack);
 while (ch != '(')
 {
 postfix[out]=ch;
 out++;
 ch=Pop(Stack);
 }
 in++;
 }
 else if (IsOperator(infix[in]))
 {
 if (IsStackEmpty())
 Push(Stack,infix[in]);
 else
 {
 ch=StackTop(Stack);
 while ((top>-1)&&(GetPrec(ch)>=GetPrec(infix[in])))
 {
 postfix[out]=Pop(Stack);
 ch=StackTop(Stack);
 out++;
 }
 Push(Stack,infix[in]);
 }
 in++;
 }
 }
 while (!IsStackEmpty())
 {
 postfix[out] = Pop(Stack);
 out++;
 }
 postfix[out]='\0';
}

Here we have assumed that the stack holds character data items. In this function we have used three functions IsOpertor(), IsOperand() and getprec(). The IsOperator() is used to check whether the specified character is an operator or not. If not then it just displays an error message - Illegal Operator and the control is returned back; otherwise a value 1 is returned back.

Here is the function that implements this task.

IsOperator(char ch)
{
 switch (ch)
 {
 case '*':
 case '+':
 case '-':
 case '/':
 case '%':
 return 1;
 default :
 printf("\nIllegal Operator. ");
 exit(0);
 }}

The IsOperand() is used to check whether the specified character is an operand or not. If not then it returns 0; otherwise a value 1 is returned back. Here is the function that implements this task.

IsOperand(char ch)
{
 if (isdigit(ch) || isalpha(ch))
 return 1;
 else
 return 0;
}

The GetPrec() operator is used to return the precedence of the given character if it is an operator, otherwise it displays an error message - Illegal Operator. This function returns the value ‘2’ for multiplicative operators, ‘1’ for additive operators and –10 for left parentheses. 

Here is the function that implements this task.

GetPrec (char op)
{
 switch (op)
 {
 case '*':
 case '/':
 case '%':
 return (2);
 case '+':
 case '-':
 return (1);
 case '(':
 return (-10);
 default :
 printf("\nIllegal Operator. ");
 exit(0);
 }
}

Now let us see the behavior of this InfixToPostfix() function by considering the following expression

Thus the compiler firstly converts the infix expression into postfix expression and then during execution, the system evaluates this postfix expression by using a stack. Now let us see-how stack helps in evaluating a postfix expression.

Evaluating a Postfix Expression

When a postfix expression is evaluated then we must remember following main things-

• when an operand is encountered it is pushed onto stack.
• when an operator is encountered its operands will be the top two elements on the stack, thus two topmost operands are popped and the specified operator is used with these two popped operands and the result is pushed back onto the stack.

Let we have a postfix expression

A B C * +

Here the first character is an operand, so we push A, then B and in last C as:

The next symbol is a operator (*) , therefore we pop B and C and perform the multiplication operator (*) as:

T1 = B * C

And push T1 on stack as:

Next symbol is +, so again we pop A and T1 and perform the addition operation as:

T2 = A + T1

And push T2 on stack as:

Since there is no other symbol left, so T2 will contain the result.

Now let us implement this task of evaluating the value of an arithmetic postfix expression.

Evaluate(char postfix[])
{
 int post=0,length,value,num;
 int t1,t2;
 char ch;
 length=strlen(postfix);
 while (post < length)
 {
 if (postfix[post]== ' ' || postfix[post]=='\t')
 {
 post++;
 continue;
 }
 else if (isdigit(postfix[post]))
 {
 num=(int) (postfix[post]-'0');
 Push(Stack,num);
 }
 else
 {
 t2=Pop(Stack);
 t1=Pop(Stack);
 switch (postfix[post])
 {
 case '+': value = t1+t2;
 break;
 case '-': value = t1-t2;
 break;
 case '*': value = t1*t2;
 break;
 case '/': value = t1/t2;
 break;
 case '%': value = t1%t2;
 break;
 default :
 printf("\nIllegal operator.");
 exit(0);
 }
 Push(Stack,value);
 }
 post++;
 }
 value=Pop(Stack);
 return value;
}

Till now we have discussed infix expressions and postfix expression. We can also have another type of notation –  prefix notation, in which the operator precedes its two operands. In other words we can say that in prefix notation the operator is placed before its two operands. Here also when we convert an infix expression into a prefix expression, we follow the precedence rule, that is highest precedence is converted first and then lower precedence.

Consider the following scenario in which a simple infix expression is converted into a prefix expression.

A+B*C            Infix expression
A+(*BC)        Converting the multiplication
+A(*BC)        Converting the addition
+A*BC            Prefix expression

However if we have a complex expression, such as:
A * B / C + D – E * F
then firstly we will parenthesize this expression according to the operator priority precedence as:

( ( ( ( A * B ) / C ) + D ) – ( E * F ) )

Now we move all operators to their corresponding left parenthesize and in last we delete all parentheses.

Here the arrows head point to the left parenthesize of the corresponding operator. Therefore the resulting prefix expression is as….

- + / * A B C  D * E F 

One should remember that the prefix form of a complex expression is not mirror image of a postfix expression. However as far as simple infix expression, such as A+B, A/B etc., it may be true, but not always.

Multiple Stacks

As stated earlier an array implementation of a stack suffers from a serious limitation of its static size. If the size is less then the stack full message announces much frequently. However if the size is large then it may result in wastage of memory space, if we use only a few number of memory locations. Some times we need to have several stacks in a programming environment. Therefore arrays may result in a lot of memory wastage.

To overcome this limitation to some extent we divide the same area space in several stacks as shown in figure-5. Figure-5(a) divides the same memory space into two arrays and figure-5(b) divides into five stacks.

Figure 5

Figure-5(a) represents two stacks of size 25 each and figure-5(b) represents five stacks of size 10 each. Here it is assumed that each stack occupies the same amount memory space. However you can also have different sizes of stacks. If you have different sizes of several stacks then there will be no efficient way to represent them sequentially (in array). Therefore in such cases we will use linked stacks.

A stack node for a linked stack is defined as:

struct StackNode
{
 int data;
 struct StackNode *link;
};
typedef struct StackNode StackNode; 

Now if we want to represent ‘n’ number of stacks then we declare an array of pointers as:

StackNode *top[n]; 

here top[i] contains the address of the topmost node of ith stack, such that  n > i ≥ 0. The process of initializing an ith stack is as:

top[i] = NULL; 

Now let us discuss two basic operation on multiple stacks.

Pushing a Node in Multiple Stacks

When we push (insert) a new node then we need to mention the stack number, say ith stack and ‘item’ of information.

Here is the algorithm, which pushed a mode in multiple stacks.

Algorithm : PushNodes

PushNodes(i, item)

Here ‘item’ is pushed into the ‘i’th stack.

• Step-1 : Create a new node ‘temp’
• Step-2 : Set the data field of ‘temp node to item as
• temp->data = item
• Step-3 : Store the value of ‘top’ variable in the link field of new node as temp->link = top[i]
• Step-4 : Update the value of ‘top[i]’
• Step-5 : Exit

Here is the ‘C’ implementation of this algorithm.

Implementation : PushNodes

PushNodes(int i, int item)
{
 StackNode *temp;
 temp = getnode();
 temp->data = item;
 temp->link = top[i];
 top[i] = temp;
}

Popping a Node from Multiple Stacks

When we pop (delete) a node from multiple stacks then it is necessary to mention the stack number. Once we have a stack number we can easily pop topmost mode from this stack, only if it is not empty.

Here is the algorithm which pops topmost node from the given stack number.

Algorithm : PopNodes

PopNodes(i)

Here item is popped from ‘i’th stack.

• Step-1 :  Check whether the stack is empty of not. If the stack is empty then flash an error message “Stack is Underflow” and go to step-6; otherwise go to step-2
• Step-2 : Store value of topmost node of ‘i’th stack in a  temporary pointer variable ‘temp’ as temp = top[i]
• Step-3 : Access the data field of ‘temp’ node as item = temp->data
• Step-4 : Update the value of top[i]as top[i]=top[i]->link
• Step-5 : Free the memory space occupied by the temp  node as freenode(temp);
• Step-6 : Exit

Here is the ‘C’ implementation of this algorithm.

Implementation : PopNodes

PopNodes(int i)
{
 StackNode *temp;
 int item;
 if (IsStackEmpty(top[i]))
 {
 printf("\nStack Underflow");
exit(0);
 }
 temp = top[i];
 item=temp->data;
 top[i] = top[i]->link;
 freenode(temp);
 return (item);
}

In multiple stacks one must also consider the case that we have seen during the implementation of  PopAndTest function. I leave the implementation of the remaining operations on multiple stacks as an exercise for the reader.

Implementation of Stacks in C++

Like C, C++ provides two different ways to implement the stacks – either using arrays or using linked lists. Let us firstly study the implementation of stacks using an array.

Array Implementation of Stacks

When we implement the stack using an array we will define a class ‘Stack’ which contains data members and member function relating to the data structure ‘stack’. The structure of a class ‘Stack’ looks like this:

class Stack
{
 private :
 // data members

 public :
 // member functions
};

The data member part of the class ‘Stack’ consists of an array and a top variable as:

int st[Size];
int top; 

Since st[] is an array, therefore it is necessary to declare its Size before its use as:

#define Size 10

In this class we will define all the member functions, such as:

IsStackFull()
IsStackEmpty()
Push(int)
int Pop()
void Pop(int &, int &)
void StackTop(int &, int &)

Here the Pop() is overloaded in order to handle the function of PopAndTest. We have already defined the behavior of these functions in earlier section of array implementation of stacks in C. In C++ we will also take the advantage of constructor while initializing the value of ‘top’ variable, instead of defining another function InitializeStack(). The Stack() constructor is used to initialize a stack to an empty stack before it is firstly used in a program.

Now the body of a class ‘Stack’ may looks like this:

class Stack
{
 private :
 int st[Size];
int top;
 public :
 Stack();
int IsStackFull();
int IsStackEmpty();
void Push(int);
int Pop();
void Pop(int &, int &)
void StackTop(int &, int &);
};

All these member functions are defined either inside a class or outside a class using a scope resolution operator (::) as:
Stack() is a constructor that initializes a newly created stack to an empty stack.

Stack :: Stack()
{
 top=-1;
}

IsStackFull() determines if a stack is full.

int Stack :: IsStackFull()
{
 if (top==Size-1)
 return 1;
 else
 return 0;
}

IsStackEmpty() determines if a stack is empty.

int Stack :: IsStackEmpty()
{
 if (top==-1)
 return 1;
 else
 return 0;
}

Push(item) pushes an item onto the stack, only if the stack is not full.

void Stack :: Push(int item)
{
 if (IsStackFull())
 {
 cout << "\nStack Overflow";
exit(0);
 }
 top++;
 st[top]=item;
}

Pop() pops an item from the stack, only if the stack is not empty.

int Stack :: Pop()
{
 int item;
 if (IsStackEmpty())
 {
 cout << "\nStack Underflow. ";
exit(0);
 }
 item=st[top];
 top--;
 return (item);
}

Pop(int &, int &) pops an item from the stack, only if the stack is not empty; otherwise it indicates the calling function by setting the flag. If the flag is set (1) then it means that the stack is empty; otherwise not.

void Stack :: Pop(int &item, int &flag)
{

 if (IsStackEmpty())
 {
 flag=1;
return;
 }
 flag=0;
 item=st[top];
 top--;
}

StackTop(int ,& int &) returns the top element of the stack, only if the stack is not empty.

void Stack :: StackTop(int &item, int &flag)
{
 if (IsStackEmpty())
 {
 flag=1;
 return;
 }
 flag=0;
 item=st[top];
}

Linked List Implementation of Stacks

On similar track we will implement a stack in C++ using a linked list. When we implement a linked stack we define the node of a linked stack first as:

struct StackNode
{
 int data;
 StackNode *link;
};

The class ‘LinkedStack’ is defined as:

class LinkedStack
{
 private :
 StackNode *top;
 public :
 LinkedStack();
int IsStackFull(StackNode *)
int IsStackEmpty()
 void PushNode(int);
 int PopNode();
 void PopNode(int &, int &);
 void StackTopNode(int &, int &);
 void display();
 ~LinkedStack();
};

The LinkedStack() constructor is used to initialize the value of ‘top’ pointer variable. The value of ‘top’ is asigned to NULL value and ~LinkedStack() destructor is used to free the memory occupied by all the nodes of linked stack. We can define these member functions either inside the class body or outside the class body. Let us see the definition of the member functions defined outside the class body.

LinkedStack() is constructor that initializes a newly created stack to the empty stack.

LinkedStack :: LinkedStack()
{
 top=NULL;
}

~LinkedStack() is the destructor that traverses the nodes of a linked stack, freeing them one by one.

LinkedStack :: ~LinkedStack()
{
 SatckNode *current;
 while (top != NULL)
 {
 current = top->link;
 delete top;
 top = current;
 }
}

IsStackFull() determines whether there is sufficient memory space for dynamically created node.

int LinkedStack :: IsStackFull(StackNode *t)
{
 if (t==NULL)
 return 1;
 else
 return 0;
}

IsStackEmpty() determines if the linked stack is empty.

int LinkedStack :: IsStackEmpty() 
{
 if (top == NULL)
 return 1;
 else
 return 0;
}

PushNode() inserts a new node at the top of the stack.

void LinkedStack :: PushNode(int item)
{
 StackNode *temp;
 temp = new StackNode; 
 temp->data = item;
 temp->link = top;
 top = temp;
}

PopNode() removes the top node of the linked stack, if the linked stack is not empty.

int LinkedStack :: PopNode()
{
 StackNode *temp
 if (IsStackEmpty())
 {
 cout << "\nStack Underflow";
exit(0);
 }

 int item=top->data;
 temp = top;
 top = top->link;
 delete temp;
 return item;
}

PopNode(int &, int &) removes the top node of the linked stack, if the linked stack is not empty; otherwise indicate the calling function by setting the flag.

void LinkedStack :: PopNode(int &item, int &flag)
{
 StackNode *temp
 if (IsStackEmpty())
 {
 cout << "\nStack Underflow";
flag=1;
return;
 }
 flag=0;
 item=top->data;
 temp = top;
 top = top->link;
 delete temp;
}

StackTopNode()retrieves the top node of the linked stack, if the linked stack is not empty.

void LinkedStack :: StackTopNode(int &item, int &flag)
{
 if (IsStackEmpty()) 
 {
flag=1;
return;
 }
 flag=0;
 item=top->data;
}

Stack in C++ using Templates

Till now the purpose of defining a stack in C and C++ looks alike. In these implementations, we have created only a single stack of type int. What will you do if you need two stacks of different types, say one stack of type ‘int’ and one for ‘char’. In that case you must declare two stacks separately. In each type of stack we need to define separate set of primitive operations, such as Push(), Pop(), etc. To overcome this limitation there is no provision in ‘C’, but fortunately C++ provides the concept of ‘templates’.

We know that templates come in two flavors – function templates and class templates. Let us see the use of class templates in defining a stack. When templates are used in conjunction with classes, they bind the type of the class to the class itself until a class of a particular type is actually created. This process of creation of a class of a particular type is called instantiation.

A class template starts with the following statement

template 

here ‘T’ is any built-in data type or user-defined data type. For the sake of convenience we will consider only the built-in data type. Of course you may use user-defined data type but for that case you have to explicitly modify some operations.

The class ‘Stack’ is now defined as:

template 
class Stack
{
 private :
 T St[Size];
 int top;
 public :
Stack();
 int IsStackFull();
 int IsStackEmpty();
 void Push(T item);
 T Pop();
 void Pop(T &, int &);
void StackTop(T &, int &);
};

Now if you define these member functions outside the class body then it is necessary to prefix the following statement template to every member function of the class Stack as:

template  Stack  :: Stack()
{
 top=-1;
}
template  int Stack :: IsStackFull()
{
 if (top==Size-1)
 return 1;
 else
 return 0;
}
template  int Stack ::IsStackEmpty()
{
 if (top==-1)
 return 1;
 else
 return 0;
}
template  void Stack :: Push(T item)
{
 if (IsStackFull())
 {
 cout << "\nStack Overflow. ";
 exit(0);
 }
 top++;
 St[top]=item;
}
template  T Stack :: Pop()
{
 T item;
 if (IsStackEmpty())
 {
 cout << "\nStack Underflow. ";
 exit(0);
 }
 item = St[top];
 top--;
 return item;
}
template  void Stack :: Pop(T &item, int &flag)
{
 if (IsStackEmpty())
 {
flag=1;
 return;
 }
 flag=0;
 item = St[top];
 top--;
}
template  void Stack :: StackTop(T &item, int &flag)
{
 if (IsStackEmpty())
 {
flag=1;
return;
 }
 flag = 0;
 item = St[top];
}

Now if we want to instantiate one stack of type ‘int’ and one of type ‘char’ then we use the following statements:

Stack  IStk;
Stack  CStk; 

As I mentioned earlier, one set of routines for a template class Stack is sufficient to manipulate a stack of any type.

A stack is a collection of elements in which all insertions and deletion are made at one end, called the top of the stack. The stack is also called as Last-In First-Out data structures. Typical operations that can be performed on stack are – push and pop. In C/C++ stacks can be implemented either by using arrays or linked lists. One must handle overflow and underflow conditions if stacks are implemented as arrays.

Stacks are more frequently used in functions calls and evaluation of an infix expression. typically an infix expression is converted into a postfix expression and then postfix expression is evaluated using stacks.

 

---

Like it on Facebook, Tweet it or share this article on other bookmarking websites.