设计一种数据结构，满足栈的性质，实现下列三个操作： 1）Push(v)；将v加入到栈

Question

设计一种数据结构，满足栈的性质，实现下列三个操作：
1）Push(v)；将v加入到栈。
2）Pop()；删除栈顶元素并返回此元素。
3)Maxelement()；返回栈中最大元素。
让它们的时间复杂度均为O(1)

Answer 1

很简单。两个同步的栈，一个存储元素，一个存储当前栈中最大值。这样就能实现O(1)时间复杂度，O(n)空间复杂度

追问

怎么设计 具体代码可以写下吗

谢谢你哦

追答

用Java写还是C++写还是其他语言写？你百度的到名字的语言我都能写得出来，不过仅限一种哦，不要让我用多种语言写。

追问

伪代码就行

追答

手机打伪代码太慢，我用C语言写一下吧，两个小时之内写好给你

追问

thanks

期待你的答案

追答

#include

typedef struct
{
int year;
int mouth;
int day;
} date;

int cmp(date a, date b)
{
return a.year * 366 + a.mouth * 30 + a.day
- b.year * 366 - b.mouth * 30 - b.day;
}

#define MAXLENGTH 10000

date stack[MAXLENGTH];
date maxstack[MAXLENGTH];
int top = -1;

void push(date x)
{
stack[top + 1] = x;
if (cmp(maxstack[top], x) > 0)
{
maxstack[top + 1] = maxstack[top];
}
else
{
maxstack[top + 1] = x;
}
++top;
}

date pop()
{
return stack[top--];
}

date maxelement()
{
return maxstack[top];
}

#undef MAXLENGTH

void print(date x)
{
printf("%dyear, %dmouth, %dday\n", x.year, x.mouth, x.day);
}

int main()
{
push((date){1, 1, 1});
print(maxelement());
push((date){1, 2, 1});
print(maxelement());
push((date){1, 1, 10});
print(maxelement());
print(pop());
print(maxelement());
print(pop());
print(maxelement());
print(pop());
return 0;
}

define到undef之间是你要的代码，其他部分是为了便于你理解，给你演示的，真羡慕你，高中就学编程了，我们农村的孩子大学菜接触电脑

追问

最大元素怎么实现没看懂，你能画一下逻辑结构图吗 画在纸上拍下来就OK

追答

抱歉，我没学过画图

追问

就是画一下栈的逻辑结构啊

类似这样

对了

你会计算机组成原理么

Answer 2

用链表，只对表尾端进行数据增、删操作，可以实现这三点。

追问

可以简单说说吗

追答

已经说的很简单了啊。
建立一个链表，然后对链表最后一个数据（尾）进行操作：
增加数据即入栈，删除数据即出栈，用另外的变量保存这个数据的值。
在建立链表的同时计数，最终数值即链表的长度。

追问

这是算法设计题，不会这么简单吧，这可是2014年哈工大数据结构考研最后一题

追答

就这么简单，没什么复杂的。