Stack
Stack is also called Last In First Out(LIFO) data structure because the first inserted element can be removed at last only and the last inserted element will be removed first. A stack is a linear list in which all additions and deletions are restricted to one end only. So, it is also called restrictive data structure.
If we want to remove an object from the middle of the stack,then we must remove all the objects above it.
Basic stack operations
The basic operations of the stack are:push,pop,stack top.
Push
Push adds an item at the top of the stack. After push, the new item will become the top. The element can be added into the stack only if there is enough space in the stack, if there is no space i.e., overflow state, then item can’t be added.
Pop
Pop removes an item at the top of the stack.After pop, the next older item will become the top. When we are removing the last element of the stack, then the stack must be set to its empty state i.e., underflow state.
Stack top
Stack top returns the top element of the stack to the user but it won’t delete the element from the stack.
Data structure
In this tutorial, we implement the stack as a linked list. To implement the linked list stack, we need two structures: a head node and a data node.
The head node for a stack has two attributes
- a top pointer
- a count of number of elements in the stack
typedef struct node {
void* data;
struct node* link;
}NODE;
The data node contains data along with a link pointer to the other nodes, it making it as self-referential structures.
typedef struct {
int count;
NODE* top;
}STACK;
Stack Algorithm
Create stack
Create stack allocates memory for the stack structure and initializes its metadata.
Algorithm to creates and initialize metadata structures.
- Allocates memory for stackhead
- Set count to 0
- Set top to null
- Return stackhead
Implementation
STACK* createstack(void) {
STACK* stack;
stack=(STACK*) malloc(sizeof(STACK));
if(stack)
{
stack->count=0;
stack->top=NULL;
}
return stack;
}
Push Stack
The steps to push a node into a stack is:
- Find the memory for the node to be allocated and allocate memory for the node.
- Then, assign the data to the stack node.
- Set the link pointer to point to the node currently indicated as the stack top.
- Update the stack pointer and increment count value by 1.
For pushing,we need to consider three different conditions:
- Insertion into empty stack
- Insertion into a stack with data
- Insertion when the available memory has exhausted
Algorithm pushstack(stack,data)
- Insert one element into stack
- Allocates new node
- Store data in new node
- Make current top node the second node
- Make new node the top
- Increment stack count
Implementation
bool pushstack(STACK* stack,void* datain) {
NODE* newptr;
if(!newptr)
return false;
newptr->data=datain;
newptr->link=stack->top;
stack->top=newptr;
(stack->count)++;
return true;
}
Pop Stack
Pop means the deleting the top element from the stack. After node has been logically deleted, it is physically deleted by recycling the memory i.e., returning it to dynamic memory. Then decrement count by 1.
Algorithm popstak(stack,dataout)
Removing an element from the top of the stack and return it to user
- if(stack empty)
- set success to false
- else
- set dataout to data in the top node
- make second node the top node
- decrement stack count
- set success to true
- end if
- return success
Implementation
void* popstack(STACK* stack) {
void* dataoutptr;
NODE* temp;
if(stack->count==0)
dataoutptr=NULL;
else
{
temp=stack->top;
dataoutptr=stack->top->data;
stack->top=stack->top->link;
free(temp);
(stack->top)--;
}
return dataoutptr;
}
Stack top (peek)
Algorithm stacktop(stack,dataout)
Retrives data from the top of the stack without deleting it.
- if(stack empty)
- set success to false
- else
- set dataout to data in top node
- set success to true
- end if
- return success
Implementation
void* stacktop(STACK* stack) {
if(stack->count==0)
return NULL;
else
return stack->top->data;
}
Empty stack
The algorithm for empty stack determines whether the stack is empty or not. This algorithm is used in data hiding concept.
Algorithm emptystack(stack)
Determines if stack is empty and return boolean values.
- if(stack count is 0)
- return true
- else
- return false
- end if
- end emptystack
Implementation
bool emptystack(STACK* stack) {
return (stack->count==0);
}
Full Stack
This algorithm determines whether the stack if full or not.
Algorithm fullstack(stack)
Determines if stack is full and returns a Boolean value.
- if(memory not available)
- return true
- else
- return false
- end if
Implementation
bool fullstack(STACK* stack) {
NODE* temp;
if((temp=(NODE*)malloc (sizeof(*(stack->top)))));
{
free(temp);
return false;
}
return true;
}
Stack Count
Stack count returns the number of elements currently in the stack.
Algorithm stackcount(stack)
Returns the number of elements currently in stack
- return (stack count)
Implementation
int stackcount(STACK* stack) {
return stack->count;
}
Destroy stack
Destroy stack deletes all data in a stack.
Algorithm destroystack(stack)
Deletes all nodes in stack
- if(stack not empty)
- loop (stack not empty)
- delete top node
- end loop
- loop (stack not empty)
- end if
- delete stack head
Implementation
STACK* destroystack(STACK* stack)
{
NODE* temp;
if(stack) {
while(stack->top!=NULL) {
free(stack->top->data);
temp=stack->top;
stack->top=stack->top->link;
free(temp);
}
free(stack);
}
return NULL;
}
Stack Applications
Stack applications can be classified into four broad categories:
Reversing data
Parsing data
Breaking data into independent pieces for further processing. For example, to translate a source program to machine language, a compiler must parse the program into individual parts such as keywords, names and tokens.
Parse Parenthesis Example
Parse parenthesis algorithm is for pairing the opening and closing parenthesis. If they are left alone,then it will display an error message according to the error.
Algorithm
- loop(any data is there)
- read(character)
- if(opening parenthesis is there)
- push(stack,character)
- else
- if(closing parenthesis)
- if(emptystack(stack))
- print(closing paranthesis not matched)
- else
- popstack(stack)
- end if
- if(emptystack(stack))
- end if
- if(closing parenthesis)
- end if
- end loop
- if(not emptystack(stack))
- print(opening parenthesis not matched)
Postponing data usage- conversions(evaluation of postfix expression)
Evaluation of postfix expression
Algorithm postfixevaluation(exp)
- create stack(stack)
- loop(for each character)
- if(character is operand)
- pushstack(stack,character)
- else
- popstack(stack,oper2)
- popstack(stack,oper1)
- operator=character
- set value to calculate(oper1,operator,oper2)
- pushstack(stack,value)
- if(character is operand)
- end loop
- popstack(stack,result)
- return(result)
By implementing the above algorithm we will get sample input and output as:
- Sample input:52/4+5*2+
- Sample output:32
Backtracking
Goal seeking and eight queens problem.
Eight queen problem requires that you place eight queens on the chess board in such a way that no queen can capture another queen.
In this algorithm, we place a queen in opposition in a row and then examine all positions in the next row to see if a queen can be placed there. If we can’t place a queen in the next row, we backtrack to the last positioned queen and try to position her in the next column. If there is no space in the next column, then fall back again.
Eight queen problem
Algorithm queens8(boardsize)
Position chess queen on a game board so that no queen can capture any other queen .
- createstack(stack)
- set row to 1
- set col to 0
- loop(row<=boardsize)
- loop(col<=boardsize and row<=boardsize)
- increment col
- if(not guarded(row,col))
- place queen at row-col intesection on board
- pushstack(row-col into stack)
- increment row
- set col to 0
- end if
- loop(col>=boardsize)
- popstack(row-col from stack)
- remove queen from row-col intersection on board
- end loop
- end loop
- loop(col<=boardsize and row<=boardsize)
- end loop
- printboard(stack)
- return