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

  1. a top pointer
  2. a count of number of elements in the stack
</>
Copy
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.

</>
Copy
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.

  1. Allocates memory for stackhead
  2. Set count to 0
  3. Set top to null
  4. Return stackhead

Implementation

</>
Copy
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:

  1. Find the memory for the node to be allocated and allocate memory for the node.
  2. Then, assign the data to the stack node.
  3. Set the link pointer to point to the node currently indicated as the stack top.
  4. 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)

  1. Insert one element into stack
  2. Allocates new node
  3. Store data in new node
  4. Make current top node the second node
  5. Make new node the top
  6. Increment stack count

Implementation

</>
Copy
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

  1. if(stack empty)
    1. set success to false
  2. else
    1. set dataout to data in the top node
    2. make second node the top node
    3. decrement stack count
    4. set success to true
  3. end if
  4. return success

Implementation

</>
Copy
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.

  1. if(stack empty)
    1. set success to false
  2. else
    1. set dataout to data in top node
    2. set success to true
  3. end if
  4. return success

Implementation

</>
Copy
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.

  1. if(stack count is 0)
    1. return true
  2. else
    1. return false
  3. end if
  4. end emptystack

Implementation

</>
Copy
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.

  1. if(memory not available)
    1. return true
  2. else
    1. return false
  3. end if

Implementation

</>
Copy
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

  1. return (stack count)

Implementation

</>
Copy
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

  1. if(stack not empty)
    1. loop (stack not empty)
      1. delete top node
    2. end loop
  2. end if
  3. delete stack head

Implementation

</>
Copy
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

  1. loop(any data is there)
    1. read(character)
    2. if(opening parenthesis is there)
      1. push(stack,character)
    3. else
      1. if(closing parenthesis)
        1. if(emptystack(stack))
          1. print(closing paranthesis not matched)
        2. else
          1. popstack(stack)
        3. end if
      2. end if
    4. end if
  2. end loop
  3. if(not emptystack(stack))
    1. print(opening parenthesis not matched)

Postponing data usage- conversions(evaluation of postfix expression)

Evaluation of postfix expression

Algorithm postfixevaluation(exp)

  1. create stack(stack)
  2. loop(for each character)
    1. if(character is operand)
      1. pushstack(stack,character)
    2. else
      1. popstack(stack,oper2)
      2. popstack(stack,oper1)
      3. operator=character
      4. set value to calculate(oper1,operator,oper2)
      5. pushstack(stack,value)
  3. end loop
  4. popstack(stack,result)
  5. 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 .

  1. createstack(stack)
  2. set row to 1
  3. set col to 0
  4. loop(row<=boardsize)
    1. loop(col<=boardsize and row<=boardsize)
      1. increment col
      2. if(not guarded(row,col))
        1. place queen at row-col intesection on board
        2. pushstack(row-col into stack)
        3. increment row
        4. set col to 0
      3. end if
      4. loop(col>=boardsize)
        1. popstack(row-col from stack)
        2. remove queen from row-col intersection on board
      5. end loop
    2. end loop
  5. end loop
  6. printboard(stack)
  7. return