Hello everyone!
The linear arrays discussed in the previous posts allows one to insert and delete at any position in the list – at the beginning, at the middle or at the end. There are certain frequent situations in computer science when one wants to restrict insertions and deletions so that they can take place only at the beginning or at the end of the list, not at the middle. Two of the data structures that are useful in such situations are queues and stacks. In this lesson, we are going to study more about stacks!
Introduction
A stack is a linear structure in which items may be added or removed only at one end. A visual representation of a stack is given as below:
In a stack insertions and deletions occur only at one end; at the top of the stack. The first item to be added on a stack is the last item to be removed and vice versa. Hence stacks are called List-In-First-Out lists (LIFO).Although stacks may seem to be a very restrictive type of data structures, they have many useful applications in computer science.
Stacks: In detail
A stack is a data structure in which insertions and deletions of elements (data) occurs only at one place: called the TOP of the stack. This means in particular that elements are deleted in a reverse order as to the manner they are inserted into the stack.Special terminologies are used for two basic operations performed on stacks:
- Push is the term used to insert an element into the stack
- Pop is the term used to delete an element from the stack
Before learning more about stacks, let us see and understand its representation in computer.
Array Representation of Stacks
Stacks may be represented in the computer in various ways usually by means of a one-way list or a linear array. Each of our stacks will be maintained by a linear array STACK: a pointer variable TOP, which contains the location of the top element of the stack; and a variable N which gives the maximum number of elements that can be held by the stack. The condition TOP=0 or TOP=NULL will indicate that the stack is empty.The figure below pictures such an array representation of a stack.
PUSH and POP Operations in Stack
The operation of adding (inserting) an item onto the stack and the operation of removing (popping) an item from a stack may be implemented, respectively, by the following procedures, called PUSH and POP. In executing the procedure PUSH, one must first test whether there is room in the stack for the new item; if not, then we have the condition known as overflow. Analogously, in executing the procedure POP, one must first test whether there is an element in the stack to be deleted; if not, then we have the condition known as underflow.
Hence let us see the
Algorithm for PUSH Operation in a Stack
This procedure pushes an ITEM onto a stack.
PUSH(STACK, TOP, N, ITEM)
1. If TOP=N, then print: OVERFLOW and return. [Stack already fill, overflow condition]
[End of If Structure]
2. Set TOP := TOP+1 [Increase TOP by 1]
3. Set STACK[TOP] := ITEM [Inserts ITEM in the new TOP position]
4. Return.
Algorithm for POP Operation in a Stack
This procedure deletes the top element of the STACK and assigns it to the variable ITEM.
POP(STACK, TOP, ITEM)
1. If TOP=0, the print: UNDERFLOW and return. [Stack is empty, there is nothing to remove, underflow condition.]
2. Set ITEM := STACK[TOP]. [Assigns TOP element to ITEM]
3. Set TOP=TOP-1. [Decrease TOP by 1.]
4. Return.
With this we complete our analysis of stacks and its corresponding data structure operations. Let us look at the following code snippet which illustrates the C code for the above explained PUSH and POP operations in Stacks.
//Shubham Mehta, Write a program to perform Push & Pop in a stack.
#include <stdio.h>
#include <process.h>
void main()
{
int choice2=0, choice1=0, i=0, choice=0, stack[10], size=10, top=0, element=0;
do
{
printf("%s", "Please enter the correct choice for the operation you want to perform: \n\n");
printf("%s", "Enter 1 to push into the stack\n");
printf("%s", "Enter 2 to pop from the stack\n");
printf("%s", "Enter 3 to display the current stack condition\n");
printf("%s", "Press any other key to exit\n\n");
printf("%s", "Your choice: ");
scanf("%d", &choice);
if(choice==1)
{
if(top==size)
{
printf("\n\n%s\n\n", "OVERFLOW! EXITING!");
goto a;
}
printf("\n\nProceeding with pushing of element...\n\n");
printf("%s", "Please enter the element to be pushed: ");
scanf("%d", &element);
++top;
stack[top-1]=element;
printf("\n\n%s\n\n", "Element pushed successfully!");
}
else if(choice==2)
{
if(top==0)
{
printf("\n\n%s\n\n", "UNDERFLOW! EXITING!");
goto a;
}
printf("\n\nProceeding with popping of element...\n\n");
printf("%s%d\n\n%s\n%s", "The element to be popped is: ", stack[top-1], "Are you sure? (Press 1 for yes, press any other key for no)", "Your choice: ");
scanf("%d", &choice2);
if(choice2==1)
{
--top;
printf("\n\n%s\n\n", "Element popped successfully!");
}
else
printf("%s\n\n", "Fine then.");
goto a;
}
else if(choice==3)
{
printf("\n\nThe current stack status is displayed as below: ");
for(i=0; i < top; i++)
printf("%d\t", stack[i]);
printf("\n\n");
}
else
exit(0);
a:
printf("%s", "Do you want to perform any more operations? (1 for yes, press any other key to exit)\nYour choice: ");
scanf("%d", &choice1);
}while(choice1==1);
getch();
}
Now that we have completely analysed stacks and their functioning, let us have a final look at a deeper programming concept related to stacks as below.
Minimisation of Overflow in Stacks
There is an essential difference between underflow and overflow while dealing with stacks. Underflow depends exclusively upon the given algorithm and the given input data, and hence there is no direct control by the programmer. Overflow, on the other hand, depends upon the arbitrary choice of the programmer for the amount of memory space reserved for each stack, and this choice does influence the number of times overflow may occur.
Generally speaking, the number of elements in a stack fluctuates as elements are added to or removed from a stack. Accordingly, the particular choice of the amount of memory for a given stack involves a time-space tradeoff. Specifically, initially reserving a great deal of space for each stack will decrease the number of times overflow may occur; However, this may be an expensive use of the space if most of the space is seldom used. On the other hand, reserving a small amount of space for each stack may increase the number of times overflow occurs; and the time required for resolving an overflow, such as by adding space to he stack, may be more expensive than the space saved.
Various techniques have been developed which modify the array representation of stack so that the amount of space reserved for a stack may be efficiently utilised. One such technique is using pointers within the array representation of stacks, also known as the linked list representation of stack. We will study that later.
And with this we finish our lesson on stacks. Hope you enjoyed it! See you later :)
0 comments:
Post a Comment