【数据结构】栈
1.概述1.1 简介栈是一种极为常用的数据结构，有两种基本操作：push和pop，这两种操作都限制在栈顶。push是从栈顶压入元素，即入栈；pop是弹出栈顶元素，即出栈。在出栈时，要判断栈是否为空。 可以用静态数组来模拟栈，但编译时需要指定数组的大小，即栈的大小是固定的。还可以用类似链表的struct实现，不需要指定大小。 栈在C++的<stack>容器中全封装好了：.pop( )是出栈操作， .push( )是入栈操作， .empty( )判断栈是否为空， .top( )返回栈顶元素。 1.2 入栈出栈描述：n个元素以1 2 ... n顺序入栈，求出栈序列有多少种。 元素的出栈情况比较复杂：可以一入栈就出栈，也可以入栈后等若干个元素入栈后再依次出栈。比如，有三个元素1、2、3，并按1 2 3的顺序入栈，其出栈序列：（1）1 2 3入栈后开始出栈，则出栈序列为3 2 1。（2）1 2入栈后开始出栈，2出栈后3入栈，此时栈中元素是3 1，出栈序列为2 3 1；也有可能2 1出栈后3入栈，则出栈序列为2 1 3。（3）…… n个元素的出栈序列的种数为C(2n,n)/(n+1)，该数叫做Catalan数，具体的证明参看这里。 2. 问题2.1 九度OJ 1108模拟栈，根据要求输出结果。 源代码：
#include "stdio.h"
#include "stdlib.h"
typedef struct stack
{
int data;
struct stack*next;
}stack;
static stack*top;
int is_empty()
{
return top==NULL;
}
void push(int a)
{
stack*p;
p=(stack*)malloc(sizeof(stack));
p->data=a;
p->next=top;
top=p;
}
void pop()
{
stack*q;
q=top;
top=top->next;
free(q);
}
int main()
{
int i,m,count;
char ch[10];
while(~scanf("%d",&count))
{
top=(stack*)malloc(sizeof(stack));
top=NULL;
if(count>0)
{
for(i=count;i>=1;i--)
{
scanf("%s",&ch);
if(ch[0]=='A')
{
if(is_empty())
printf("En");
else printf("%dn",top->data);
}
else if(ch[0]=='P')
{
scanf("%d",&m);
push(m);
}
else if(ch[0]=='O')
{
if(is_empty()) continue;
else pop();
}
}
printf("n");
}
else if(count==0)
break;
}
return 0;
}
2.2 POJ 1028题目大意：有两个栈，backward和forward，BACK,FORWARD 和 VISIT命令引起两个栈的push、pop操作，输出相应的结果。 实际上，可以把backward栈的top看作是current page，接下来问题迎刃而解了。 源代码：
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
string str1,str2;
stack<string>forward;
stack<string>backward;
backward.push("http://www.acm.org/");
while(cin>>str1&&str1!="QUIT")
{
if(str1=="BACK")
{
str2=backward.top(); //the top of backward stack is the current page
backward.pop();
if(backward.empty())
{
cout<<"Ignoredn";
backward.push(str2);
}
else
{
cout<<backward.top()<<endl;
forward.push(str2);
}
}
else if(str1=="FORWARD")
{
if(forward.empty())
cout<<"Ignoredn";
else
{
cout<<forward.top()<<endl;
backward.push(forward.top());
forward.pop();
}
}
else if(str1=="VISIT")
{
cin>>str2;
backward.push(str2);
while(!forward.empty())
forward.pop();
cout<<str2<<endl;
}
}
return 0;
}
2.3 POJ 1363题目大意：元素1,2,...,N依次入栈，输入一组序列，判定其是否为出栈序列。 思路：用poping表示输出的元素序列， （1）push元素1,N依次入栈，在每一次push操作后，判定栈顶元素==poping[ j ]；若相等，栈顶元素出栈，j++ ； （2）push操作完成之后，若所有栈为空，则说明所有元素出栈，此序列即为出栈序列；反之，则否。 在语句while(!st.empty()&&st.top()==poping[j]&&j<n)中少加一个判定条件?!st.empty() ，一直得不到正确结果。考虑循环结束条件时，一定要周到。 源代码：
#include <iostream>
#include <stack>
using namespace std;
#define MAX 1000
int main()
{
stack<int>st;
int poping[MAX];
int i,j,n;
while(scanf("%d",&n)&&n!=0)
{
while(scanf("%d",&poping[0])&&poping[0]!=0)
{
for(i=1;i<n;i++) //input the poping sequence
scanf("%d",&poping[i]);
while(!st.empty()) //clear the stack
st.pop();
for(i=1,j=0;i<=n;i++)
{
st.push(i);
while(!st.empty()&&st.top()==poping[j]&&j<n)
{
st.pop();
j++;
}
}
if(st.empty())
printf("Yesn");
else
printf("Non");
}
printf("n");
}
return 0;
}
2.4 POJ 2082题目大意在这篇文章中描述得非常清楚：有n个相邻的矩形，宽和高已知，求出能够组合形成新矩形的最大面积。 思路：用一个栈存储矩形，栈中保持矩形的高递增，cur表示刚输入的矩形，lasth表示栈顶元素的高（其实也不是，有点不好表达），curarea表示合并后的矩形的面积，maxarea表示最大矩形的面积 （1）若cur.h>=lasth，cur入栈； （2）若cur.h<lasth，高比cur.h小的矩形出栈；在每一次出栈的过程中，进行合并操作（即合并成新矩形）；由于maxarea可能出现在每一次出栈过程中，所以每一次循环都得对maxarea进行更新； （3）置lasth=cur.h； （4）栈可能不为空，还需要做出栈处理，操作跟（2）相类似。 源代码：
#include <iostream>
#include <stack>
using namespace std;
struct Rectangle
{
int w,h;
};
stack<Rectangle>st;
int main()
{
int i,n,lasth,totalw,curarea,maxarea;
Rectangle cur;
while(scanf("%d",&n)&&n!=-1)
{
lasth=0;
maxarea=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&cur.w,&cur.h);
/*push stack*/
if(cur.h>=lasth)
st.push(cur);
else
{
totalw=0;
while(!st.empty()&&st.top().h>=cur.h)
{
totalw+=st.top().w;
curarea=totalw*st.top().h;
if(curarea>maxarea)
maxarea=curarea;
st.pop();
}
totalw+=cur.w;
cur.w=totalw;
st.push(cur);
}
lasth=cur.h;
}
for(totalw=0;!st.empty();st.pop())
{
totalw+=st.top().w;
curarea=totalw*st.top().h;
if(curarea>maxarea)
maxarea=curarea;
}
printf("%dn",maxarea);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
