队列中取最大值操作_数据结构每次出队最大值

       这是一个要在队列中记录最大值的问题，但每次进队或出队又不能通过遍历去检测最大值的变化。用两个堆栈去实现一个队列是比较常见的方法，书中巧妙的用到了此方法，这样问题就转化为堆栈中取最大值操作问题。由于堆栈的变化只在栈顶，借助反向推导的思想：

       由于在Push的过程中，最大值只与某一些值有关，这些值会在Push的过程中形成一个有序的链式结构。如Push（1,2,6,4,5,2,7,4）那么这个有序序列为（1,2,6,7） 所以当7被POP时，最大值会回到6，6被POP时，最大值会回到2，整个过程与4,5无关。所以可以用一个数组记录下当堆栈中某一个数被POP后，下一个最大值在堆栈中的位置。

       "如果入栈顺序是12354,那么
        正常堆栈：12354
        最大值堆栈1235
        此时当前最大值是5，如果弹出4，当前最大值还是5，如果再弹出5，当前最大值是3，以此类推，应该没问题呀。“文中的主要思想就是按照这个思想来的，与编程之美中的想法始终感觉有点不吻合，与编程之美中的主要思想比较吻合的可以参考博客”http://blog.csdn.net/caryaliu/article/details/8097209“。

我在此给出我实现的C语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct StackNode
{
	char data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;
 
typedef struct LinkStack
{
	LinkStackPtr top;
	int count;
}LinkStack;
 
 
int InitStack(LinkStack *S)
{ 
        S->top = (LinkStackPtr)malloc(sizeof(StackNode));
        if(!S->top)
                return 0;
        S->top=NULL;
        S->count=0;
        return 1;
}
/* 插入元素e为新的栈顶元素 */
int Push(LinkStack *S,char e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
        S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */
        S->count++;
        return 1;
}
 
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
int Pop(LinkStack *S,char *e)
{ 
        LinkStackPtr p;
        if(S->count==0)
                return 0;
        *e=S->top->data;
        p=S->top;					/* 将栈顶结点赋值给p，见图中③ */
        S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
        free(p);                    /* 释放结点p */        
        S->count--;
        return 1;
}
/* 若栈不空，则用e返回S的栈顶元素，并返回1；否则返回0 */
int GetTop(LinkStack S,char *e)
{
    if (S.top==NULL)
         return 0;
    else
         *e=S.top->data;
    return 1;
}
 
/*将栈中的元素最大值压入栈中*/
int MaxPush(LinkStack *s,char e)
{
	char a;
	GetTop(*s,&a); //获取栈顶元素
	if (a<=e)
	{
		Push(s,e);
	}
	return 1;
}
 
int main() 
{
	LinkStack S,S1;
	char e=0;
	char *max="12645274";
	int i,j,len=strlen(max);
	j=InitStack(&S);
	InitStack(&S1);
	if (j==1)
	{
		for (i=0;i<len;i++)
		{
			MaxPush(&S,max[i]);  //将最大值压入栈中
			Push(&S1,max[i]);
		}
	}
	printf("最大值栈中的数据为： \n");
	for (i=S.count;S.count>0;i--)
	{
		Pop(&S,&e);
	    printf("max %c\n",e);
	}
	/*printf("保存原数据栈为：\n");
	for (i=S1.count;S1.count>0;i--)
	{
		Pop(&S1,&e);
	    printf("max %c\n",e);
	}*/
	system("pause");
	return 0;
}