UC知道求C++完整代码，高手请进，成功运行还有加分
来源：百度知道 编辑：UC知道 时间：2024/09/20 12:04:33
In this lab, you would be implementing a template class for the data structures stack and test its behavior by writing some sample test program. To give you a little background, Stack is a data structure that follows Last In First Out (LIFO) principle i.e., the element you added last will be the first one to come out. Following are the basic operations on Stack:
Push – Add an element onto the stack (to the top of the stack)
Pop ‐ Remove an element from the stack (from the top of the stack)
Peek ‐ Look at the element that is on top of the stack. (DO NOT remove it)
isEmpty – Check whether the stack is empty or not
It is important to note that all the push and pop operations are done on top of the stack.
Stack can be implemented in many ways. Here, we consider implementing using an array of
fixed size i.e., there is a limit on number of objects the stack can hold. Size of the stack should be provided when creating the stack. Refer to the class note
Push – Add an element onto the stack (to the top of the stack)
Pop ‐ Remove an element from the stack (from the top of the stack)
Peek ‐ Look at the element that is on top of the stack. (DO NOT remove it)
isEmpty – Check whether the stack is empty or not
It is important to note that all the push and pop operations are done on top of the stack.
Stack can be implemented in many ways. Here, we consider implementing using an array of
fixed size i.e., there is a limit on number of objects the stack can hold. Size of the stack should be provided when creating the stack. Refer to the class note
利用堆来操作
#include<iostream>
using namespace std;
#define MAX 0x0fffffff
#define parent(i) (i)>>1
#define left(i) (i)<<1
#define right(i) ((i)<<1)+1
int a[MAX];
int len;
int size;//堆中元素长度
void maxheapify(int i)//维护最大堆的性质 O(lgn)
{ int l=left(i);
int r=right(i);
int large=i;
if(l<=size&&a[l]>a[i])
large=l;
if(r<=size&&a[r]>a[large])
large=r;
if(large!=i)
{ int tmp=a[i];
a[i]=a[large];
a[large]=tmp;
maxheapify(large);
}
}
void build()//建堆 O(nlgn)
{ size=len;
int i;
for(i=(len>>1);i>=1;i--)
{ maxheapify(i);
}
}
int heap_max_heapify()//维护最大优先级，返回最大元素
{ int maxx;
maxx=a[1];
a[1]=a[size];
size--;
maxheapify(1);
return maxx;
}
void heap_c