本文共 3687 字，大约阅读时间需要 12 分钟。

数据结构（五）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 栈的基本操作 ——

1.题目描述

栈是一种重要的数据结构，它具有push k和pop操作。push k是将数字k加入到栈中，pop则是从栈中取一个数出来。

栈是后进先出的：把栈也看成横向的一个通道，则push k是将k放到栈的最右边，而pop也是从栈的最右边取出一个数。

假设栈当前从左至右含有1和2两个数，则执行push 5和pop操作示例图如下：

push 5          pop   栈   1 2  ------->  1 2 5 ------>  1 2

现在，假设栈是空的。给定一系列push k和pop操作之后，输出栈中存储的数字。若栈已经空了，仍然接收到pop操作， 则输出error。

1.1输入

第一行为m，表示有m组测试输入，m<100。 每组第一行为n，表示下列有n行push k或pop操作。（n<150）

接下来n行，每行是push k或者pop，其中k是一个整数。 （输入保证同时在栈中的数不会超过100个）

1.2输出

对每组测试数据输出一行。该行内容在正常情况下，是栈中从左到右存储的数字，数字直接以一个空格分隔，如果栈空，则不作输出；但若操作过程中出现栈已空仍然收到pop，则输出error。

1.3样例输入与输出

样例输入

2

4

push 1

push 3

pop

push 5

1

pop

样例输出

1 5

error

2.代码实现

c

#include 
   
    #include 
    
     #include 
     
      #include 
      
       typedef int ElemType;//栈内结构体typedef struct{
       //存储输入的数据    ElemType data;    //指向下一个输入的数据，即上一层的数据    struct node *link;}node;//永远指向栈内最上面的数据的指针typedef struct{
       //指向最上层数据节点的指针    node *top;}Stack;//创建头结点Stack* createStack(){
       Stack *head;    head = (Stack*)malloc(sizeof(Stack));    head->top=NULL;    return head;}//压栈void push(Stack *myStack, ElemType x){
       node *t, *p;    p=myStack->top;    t=(node*)malloc(sizeof(node));    t->data = x;    t->link=p;    myStack->top=t;}//判断栈内是否为空bool empty(Stack *myStack){
       if(myStack->top!=NULL)        return false;    else        return true;}//用于显示和输出栈内最上层的数据ElemType top(Stack *myStack){
       ElemType n;    n = myStack->top->data;    return n;}//出栈void pop(Stack *myStack){
       node *p;    p=myStack->top;    myStack->top=p->link;    free(p);}//销毁所有节点bool destroy(Stack *myStack){
       free(myStack);    return false;}int main(void){
       //指向最上层数据节点的指针    Stack *head;    ElemType c;    int n, m;    scanf("%d", &n);    while(n--)    {
           //判断是否已经出现错误error        int flag = 0;        //创建头结点        head = createStack();        scanf("%d", &m);        while(m--)        {
               char str[10];            scanf("\n%s", str);            //如果是push，则压栈            if(strcmp(str,"push")==0)            {
                   scanf("%d", &c);                //如果已经出现错误则不作任何操作                if(flag == 1)                    continue;                push(head, c);            }            //如果是pop，则出栈            if(strcmp(str,"pop")==0)            {
                   //如果栈内为空                if (empty(head))                {
                       //如果已经出现错误则不作出任何操作                    if(flag == 1)                        continue;                    printf("error\n");                    //栈内为空还进行pop出栈操作直接报错，且将flag改为出错状态                    flag = 1;                }                //如果栈内不空                else                {
                       //如果已经出现错误则不作出任何操作                    if(flag == 1)                        continue;                    //出栈                    pop(head);                }            }        }        int num[151];        int wal = 0;        //当没有出现错误的时候运行输出操作        if(flag == 0)        {
               //将栈内数据移存至数组内            while (!empty(head))            {
                   c = top(head);                num[wal] = c;                wal++;                pop(head);            }            //循环输出            while(wal--)            {
                   flag = 1;                printf("%d ", num[wal]);            }            if(flag == 1)                printf("\n");        }        //销毁所有节点        destroy(head);    }    return 0;}
      
     
    
   

3.代码说明

栈的储存方式是先进后出，而题目中所涉及到的几种基本操作机制如下：

3.1 入栈操作

3.2 出栈操作

在栈内还有数据节点的时候，进行数据的出栈操作：

3.3 error操作

下面展示会显示错误的操作：

如果当栈内没有数据节点的时候，如果还进行pop出栈操作，就会显示error的错误提示。

转载地址：http://pfazi.baihongyu.com/