Stacks is abstract data types (ADT)
We can implement stack in two ways
- Arrays
- Linked lists
We can perform following operations on stack
- push( ) Insert element at top of stack
- pop( ) Delete and return the top of stack
- IsStackEmpty( ) Return true if stack is empty
- IsStackFull( ) Return true if stack is Full
Applications of Stacks :
Web browsers store the addresses of recently visited sites on a stack
- Each time the visits a new site ==> pushed on the stack.
- Browsers allow to “pop” back to previously visited site.
The undo-mechanism in an editor
- The changes are kept in a stack.
- When the user presses “undo” the stack of changes is popped.
The function-call mechanism
- The active (called but not completed) functions are kept on a stack
- Each time a function is called, a new frame describing its context is pushed onto the stack
- The context of a method: its parameters, local variables, what needs to be returned, and where to return (the instruction to be executed upon return)
- When the function returns, its frame is popped, the context is reset to the previous method (now on top of the stack) and the program continues by executing the previously suspended method
-----------------------------------------------------------------------------------
Implementation of stack by using LinkedList
#include<stdio.h>
#include<malloc.h>
# define MAX 10
struct stack
{
int data;
struct stack *next;
};
int Count(struct stack *head)
{
int no = 0;
while(head != NULL)
{
++no;
head = head -> next;
}
return no;
}
int IsStackEmpty(struct stack *head)
{
if(head == NULL)
{
return 1;
}
else
{
return 0;
}
}
int IsStackFull(struct stack *head)
{
if(Count(head) == MAX)
{
return 1;
}
else
{
return 0;
}
}
void Display( struct stack *head )
{
if(head == NULL)
{
return;
}
while(head)
{
printf(" -> |%d| ", head->data);
head = head -> next;
}
}
int pop(struct stack **head)
{
int no = 0;
struct stack *temp1,*temp2;
temp1 = temp2 = ( *head );
if(IsStackEmpty(*head))
{
return -1;
}
else
{
while(temp1 -> next != NULL)
{
temp2 = temp2 -> next;
temp1 = temp2 -> next;
}
temp2 -> next = NULL;
no = temp1 -> data;
free(temp1);
return no;
}
}
void push(struct stack **head, int no)
{
struct stack *temp;
struct stack *newn = (struct stack*)malloc(sizeof(struct stack));
newn -> data = no;
temp = (*head);
if(IsStackFull(*head))
{
free(newn);
return;
}
if(*head == NULL)
{
newn -> next = NULL;
(*head) = newn;
}
else
{
while(temp -> next != NULL)
{
temp = temp -> next;
}
temp -> next = newn;
newn -> next = NULL;
}
}
int main(int argc, char *argv[])
{
struct stack * first = NULL;
push(&first,10);
push(&first,20);
push(&first,30);
push(&first,40);
Display(first);
printf("%d",pop(&first));
printf("%d",pop(&first));
return 0;
}
-----------------------------------------------------------------------------------
Implementation of stack by using Array
#include<stdio.h>
#include<malloc.h>
# define MAX 10
int top = -1;
int Stack[MAX];
int IsStackEmpty()
{
if(top == -1)
{
return 1;
}
else
{
return 0;
}
}
int IsStackFull()
{
if(top == MAX)
{
return 1;
}
else
{
return 0;
}
}
void Display()
{
int i = 0;
if(top == -1)
{
return;
}
for(i = top; i != -1; i--)
{
printf("%d",Stack[i]);
}
}
int pop()
{
int no = 0;
if(IsStackEmpty())
{
return -1;
}
else
{
return Stack[top--];
}
}
void push(int no)
{
if(IsStackFull( ))
{
return;
}
Stack[++top] = no;
}
int main(int argc, char *argv[])
{
push(10);
push(20);
push(30);
push(40);
Display();
printf("\n%d",pop());
printf("\n%d",pop());
Display();
return 0;
}
-----------------------------------------------------------------------------------
Important points about implementaion of Stack by using Array or LinkedList
Array
• Simple and efficient
• Assume a fixed capacity for array
• If capacity is too small, can reallocate, but expensive
• If capacity is too large, space waste
Linked Lists
• No size limitation
• Extra space per element
When know the maximum number of element, use arrays
No comments:
Post a Comment