#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct que
{
int *head,*tail;
};
bool empty(que *q){return q->head==q->tail;}
int size(que *q){return q->tail-q->head;}
void build(que *q,int n)
{
q->head=(int *)malloc(sizeof(int));
q->tail=q->head;
}
void push(que *q,int val){*q->tail++=val;}
int pop(que *q)
{
if(empty(q))return -1;
return *q->head++;
}
int front(que *q)
{
if(empty(q))return -1;
return *q->head;
}
int main()
{
que q;
build(&q,5);
for(int i=0;i<5;i++)
{
int x;cin>>x;
push(&q,x);
}
while(!empty(&q))cout< } 队列2 #include using namespace std; typedef long long ll; typedef unsigned long long ull; #define Status int #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }linkQueue; struct QUEUE { Status InitQueue(linkQueue &Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); return OK; } Status DestroyQueue(linkQueue &Q) { while(Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }return OK; } Status EnQueue(linkQueue &Q,int e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p;return OK; } Status DeQueue(linkQueue &Q,int &e) { if(Q.front==Q.rear)return ERROR; QueuePtr p; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); return OK; } Status Empty(linkQueue Q) { return Q.rear==Q.front; } }; int main() { QUEUE qu; linkQueue Q; qu.InitQueue(Q); for(int i=0,e;i<5;i++) { cin>>e; qu.EnQueue(Q,e); } while(!qu.Empty(Q)) { int e;qu.DeQueue(Q,e); cout< }puts(""); } 循环队列 #include using namespace std; typedef long long ll; typedef unsigned long long ull; #define Status int #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define MAXSIZE 100 typedef struct { int *base; int front ,rear; }SqQueue; struct QUEUE { Status InitQueue(SqQueue &Q) { Q.base=(int *)malloc(MAXSIZE*sizeof(int)); if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0; return OK; } Status QueueLength(SqQueue &Q) { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } Status EnQueue(SqQueue &Q,int r) { if((Q.rear+1)%MAXSIZE==Q.front)return ERROR; Q.base[Q.rear]=r; Q.rear=(Q.rear+1)%MAXSIZE; return OK; } Status DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear)return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; } Status QueueTravel(SqQueue Q) { for(int i=0;i { cout< }puts(""); } }; int main() { QUEUE qu; SqQueue Q; qu.InitQueue(Q); for(int i=0;i<5;i++) { int e;cin>>e; qu.EnQueue(Q,e); } qu.QueueTravel(Q); } 单调队列 #include #include #include #include #include using namespace std; #define N 1000005 int n,k; int minn[N],maxx[N]; int a[N]; struct qin { int num,index; }; qin Q[N],P[N]; void getmax() { int head=1,tail=0; for(int i=0;i { while(head<=tail&&Q[tail].num tail++;Q[tail].num=a[i];Q[tail].index=i; if(i>=k-1) { while(Q[head].index<=i-k)head++; maxx[i-k+1]=Q[head].num; } } } void getmin() { int head=1,tail=0; for(int i=0;i { while(head<=tail&&P[tail].num>a[i])tail--; tail++;P[tail].num=a[i];P[tail].index=i; if(i>=k-1) { while(P[head].index<=i-k)head++; minn[i-k+1]=P[head].num; } } } int main() { while(cin>>n>>k) { for(int i=0;i getmax();getmin(); for(int i=0;i<=n-k;i++)printf("%d%c",minn[i]," n"[i==n-k]); for(int i=0;i<=n-k;i++)printf("%d%c",maxx[i]," n"[i==n-k]); } } /// ©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任
