数据结构实验之栈与队列八：栈的基本操作

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

Input

首先输入整数t（1 <= t <= 10），代表测试的组数，以后是 t 组输入。

对于每组测试数据，第一行输入两个正整数 m（1 <= m <= 100)、n（1 <= n <= 1000)，其中m代表当前栈的最大长度，n代表本组测试下面要输入的操作数。 而后的 n 行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示栈顶元素出栈；如果是'A'，表示询问当前栈顶的值'。

Output

对于每组测试数据，根据其中的命令字符来处理堆栈；

（1）对所有的'P'操作，如果栈满输出'F'，否则完成压栈操作；

（2）对所有的'A'操作，如果栈空，则输出'E'，否则输出当时栈顶的值；

（3）对所有的'O'操作，如果栈空，则输出'E'，否则输出栈顶元素的值，并让其出栈；

每个输出占据一行，每组测试数据（最后一组除外）完成后，输出一个空行。

Sample Input

2

5 10

A

P 9

A

P 6

P 3

P 10

P 8

A

P 2

O

2 5

P 1

P 3

O

P 5

A

Sample Output

E

9

8

F

8

3

5

Hint

建议： 用串的方式（%s）读入操作字符。

栈的几个基本操作，没有什么好说的，看代码就好，注意输入由于单个字符容易输入错误，所以建议用字符串读入。

注意输出。

#include 
    
     #include 
     
      #include 
      
       typedef struct node{    int data;    struct node *next;}Node;typedef struct stack{    Node *base,*top;    int len;}Stack;struct num{    int data,next;}s[100050];Node *newnode()//建立节点{    Node *t;    t = (Node *)malloc(sizeof(Node));    t->next = NULL;    return t;};Stack *Newstack()//建立新栈{    Stack *t;    t = (Stack *)malloc(sizeof(Stack));    t->top = newnode();    t->base = t->top;    t->len = 0;    return t;}void push(Stack *t,int x)//入站{    Node *p = newnode();    p->data = x;    p->next = t->top->next;    t->top->next = p;    t->base = p;    t->len++;}int top(Stack *t)//询问栈顶元素{    return t->top->next->data;}void pop(Stack *t)//出栈{    Node *p;    p = t->top->next;    t->top->next = t->top->next->next;    free(p);    t->len--;}int empty(Stack *t)//询问栈是否为空{    if(t->top->next==NULL)        return 1;    return 0;}void del(Stack *t)//清空栈{    while(!empty(t))        pop(t);}int main(){    int t,i,m,n,x;    char s[10];    Stack *q;    q = Newstack();    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        while(!empty(q))            pop(q);        for(i=0;i
       
        len==n)                    printf("F\n");                else                    push(q,x);            }            else if(s[0]=='O')            {                if(empty(q))                    printf("E\n");                else                {                    printf("%d\n",top(q));                    pop(q);                }            }        }        if(t!=0)            printf("\n");    }    return 0;}
       
      
     
    

线性表

#include 
    
     #include 
     
      #include 
      
       typedef struct Static{    int *top,*base;    int len;}Static;Static newStatic(){    Static t;    t.top = (int *)malloc(100050*sizeof(int));    t.base = t.top;    t.len = 0;    return t;}int top(Static t){    return *(t.top-1);}void pop(Static *t){    t->top--;    t->len--;}void push(Static *t,int x){    t->len++;    *(t->top++) = x;}int empty(Static t){    if(t.base==t.top)        return 1;    return 0;}void clear(Static *t){    while(!empty(*t))        pop(t);    t->len = 0;}int main(){    Static k;    k = newStatic();    int n,t,m,x;    char s[5];    scanf("%d",&t);    while(t--)    {        if(!empty(k))            clear(&k);        scanf("%d%d",&n,&m);        while(m--)        {            scanf("%s",s);            if(s[0]=='A')            {                if(empty(k))                    printf("E\n");                else                    printf("%d\n",top(k));            }            else if(s[0]=='P')            {                scanf("%d",&x);                if(k.len==n)                    printf("F\n");                else                    push(&k,x);            }            else if(s[0]=='O')            {                if(empty(k))                    printf("E\n");                else                {                    printf("%d\n",top(k));                    pop(&k);                }            }        }        printf("\n");    }    return 0;}