We are interested in this part to implement a $$\texttt{stack}$$ of integers using a $$\texttt{Max-Heap}$$.

Let $$\texttt{H}$$ be a $$\texttt{Max-Heap}$$ allowing the following operations:

  • $$\texttt{Max-Heap CreateHeap();}$$ This operation creates a $$\texttt{Max-Heap}$$. The capacity of the heap is fixed and cannot increase.
  • $$\texttt{int insert(Max-Heap *H, element e);}$$ This operation inserts an element $$\texttt{e}$$ in the $$\texttt{Max-Heap}$$ if there's room left. The element $$\texttt{e}$$ could be a complex type and $$\texttt{percolate up}$$ could be performed on one of its field members.
  • $$\texttt{int deleteMax(Max-Heap *H);}$$ This operation deletes the maximum element in a $$\texttt{Max-Heap}$$ if it exists.
  • $$\texttt{int getMax(Max-Heap H, element *e);}$$ This operation returns the $$\texttt{Max-Heap}$$ maximum element in $$\texttt{e}$$ if it exists.
  • $$\texttt{int isEmptyHeap(Max-Heap H);}$$ This operation returns $$\texttt{true}$$ if the $$\texttt{Max-Heap}$$ is empty, $$\texttt{false}$$ otherwise.
  • $$\texttt{int isFullHeap(Max-Heap H);}$$ This operation returns $$\texttt{true}$$ if the $$\texttt{Max-Heap}$$ is full, $$\texttt{false}$$ otherwise.

 

  • Give the declaration of types $$\texttt{element}$$ and $$\texttt{stack}$$;
  • Implement a $$\texttt{stack}$$ using a $$\texttt{Max-Heap}$$.

 


Difficulty level
Video recording
This exercise is mostly suitable for students
typedef struct
{
	Heap h;
	int counter;
} stack;

stack CreateStack()
{
	stack s;
	s.h=CreateHeap(1,1);
	s.counter=0;
	return s;
}

int isEmptyStack(stack p)
{
	return isEmptyHeap(p.h);
}

int isFullStack(stack p)
{
	return isFullHeap(p.h);
}


void Push(stack *p, int number)
{
	element e;
	e.data=number;
	e.counter=p->counter;
	p->counter++;
	Insert(&(p->h),e);
}

int Pop(stack *p)
{
    element e;
    if (isEmptyStack(*p)) return 0;
	if(DeleteMax(&(p->h), &e))
	    return 1;
	return 0;
}

int Top(stack p, int *nb)
{
	element e;
	if(GetMaximum(p.h,&e))
	{
		*nb=e.data;
		return 1;
	}
	return 0;
}

Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Graph Edge Property