STACK DATA STRUCTURE
A stack is an ordered collection of items in which operations take place on the principle LIFO (Last In First Out). Items are deleted and inserted into the stack at only one end, called the top of the stack. The item, which is inserted last will be retrieved first from the stack.
Unlike an array, a stack is a dynamic, constantly changing object. The single end of the stack is designated as the stack Top. New items may be put on top of the stack or items that are at the top of the stack may be removed from the stack. Following is a representation of a stack containing items in it:
Fig.: A stack containing six items in it
In this figure, the vertical lines that extend past the items of the stack indicate the top of the stack. If any new items are added to the stack, they are placed on top of E, and if any items are deleted, E is the first item to be deleted.
Primitive Operations:
The two primary operations performed often on stack are: Insertion and Deletion of items from the stack. These two operations are termed as Push and Pop respectively. When an item is added to a stack, it is known as ‘pushing’ into the stack, and when an item is removed, it is called as ‘popping’ from the stack.
Given a stack S, and an item i, performing the operation push(s, i) adds the item i to the top of the stack. Similarly, the operation pop(s) removes the top element and returns it as a function value. Thus the assignment operation
i = pop(S);
removes the element at the top of S and assigns its value to i. Because of the push operation, which adds element to a stack, a stack is sometimes called a pushdown list.
There is no upper limit on the number of items that may be kept in a stack. Pushing another item on to a stack makes the stack to grow and popping an item from the stack shrinks the stack downwards. When there is no item in the stack, it is called as empty stack. An empty stack can’t popup any value.
Another operation that can be performed on stack is to determine what the top item on a stack is without removing it. This operation is written as
stacktop(S);
It returns the top element of stack S, when it is not empty. This operation can be implemented using the primitive operations pop followed by push. Therefore,
i = stacktop(S);
is equivalent to
i = pop(S);
push(s, i);
The result of an illegal attempt to pop or access an item from an empty stack is called stackunderflow, which can be avoided by checking the emptiness of the stack.
Representing Stacks in C:
A stack in C may be implemented using a structure containing two objects: an array to hold the elements of the stack, and an integer to indicate the position of the current stack top within the array. This may be done for a stack of integers by the declaration:
# define STACKSIZE 100
struct stack
{
int top;
int top;
int items[STACKSIZE];
} s;
Implementing the Pop operation:
To pop an element from the stack, first check whether the stack is empty. If the stack is empty, print a warning message and halt execution or else remove the top element from the stack. This operation is coded in C as follows:
pop(ps)
struct stack *ps;
{
if(empty(ps)) {
printf(“%s”, “Stack Underflow”);
exit(1);
}
return(ps-->item[ps-->top--]);
}
Implementing the Push operation:
Before pushing any element into the stack, check whether the stack is full. If there any empty space in the stack, then increment the pointer top to point the next empty element in which the new item can be stored. This operation is implemented using the following code in C:
push(ps, x)
struct stack *ps;
int x;
{
if(ps-->top == STACKSIZE-1) {
printf(“%s”, “Stack Overflow”);
exit(1);
}
else
ps-->item[++(ps-->top)] = x;
return;
}
