栈和队列的基本实现和应用（数据结构复习）

冷不防 2022-10-19 04:13 186阅读 0赞

# 栈 #

### 栈的基本实现 ###

1.  创建
2.  入栈
3.  出栈（查找）
4.  删除

### 栈的应用 ###

1.  函数调用及递归实现
2.  深度优先搜索
3.  回溯算法
4.  表达式求值

引言：斐波那契数列的实现

代码：[斐波那契数列的递归法和迭代法][Link 1]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70][]

### 题一 ：是否为合法序列 ###

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序

列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

1）如 IIIOOIOO是合法的

2)  如 IOOIOIIO是非法的，IIIOOIOI同样是非法的

写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）

代码：

int Judge(char A[])
    {
        int i=0;
        int sum=0;
        while(A[i]!='\0')
        {
            switch(A[i])
            {
            case 'I':
                sum++;
                break;      //用+1表示进栈，用负1表示出栈
            case 'O':
                sum--;
                if(sum<0)
                {
                    printf("序列非法\n");
                    exit(0);
                }
            }
            i++;
        }
        if(sum!=0)
        {
    
            printf("序列非法\n");
            return false;
        }
        else
        {
            printf("序列合法\n");
            return true;
        }
    }

###  题二：判断链表的数据是否中心对称 ###

设单链表的表头指针为L，结点结构由data和next两个域构成，其中data域为字

符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、XYYX都是中

心对称。

答：

算法思想：

使用栈来判断链表中的数据是否中心对称。让链表的前一半元素依次进栈。在处
    理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，
    若相等，则将链表中的下一个元素与栈中再弹出的元素比较，直至链表到尾。这时若栈是空栈，
    则得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时，结论为链表非
    中心对称，结束算法的执行。

**代码**

int Judge(LinkList L,int n)
    {
        int i;
        char s[n/2];
        LinkList p=L->next;
        for(i=0; i<n/2; i++)
        {
            s[i]=p->data;
            p=p->next;
        }
        i--;
        if(n%2==1)
            p=p->next;
        while(!p)
        {
            if(s[i]!=p->data)
            {
              break;
            }
            i--;
            p=p->next;
        }
        if(i==-1)
            return 1;
        else
            return 0;
    }
    
    
    
    /*
    while(!p&&s[i]==p->data)
    {
            
            i--;
            p=p->next;
     }
    */

###  题三：共享栈的实现  ###

设有两个栈sl、s2都采用顺序栈方式，并共享一个存储区\[O,...,maxsize-l\]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。                                                              试设计s1、s2有关入栈和出栈的操作算法。

**代码**

typedef struct ShareStack
    {
        Elementype stack[MaxSize];
        int top[2];
    } *Stack;
    //int push(int i,Elementype X);
    //int pop(int i);
    stack s;
    
    int push(int i,Elementype X)
    {
        if(i<0||i>1)
        {
            printf("栈号错误");
            exit(0);
        }
    
        if(s->top[1]+1==s->top[0])
        {
            printf("栈已经满\n");
            return 0;
        }
        switch(i)
        {
          case 0:s->stack[++s.top[0]]=X; break;
          case 1:s->stack[--s.top[1]=X;
        }
       
         return 1;                    
    }
    int pop(int i)
    {
      if(i<0||i>1)
        {
            printf("栈号错误");
            exit(0);
        }
        
         if(s->top[0]==-1&&s->top[1]==MaxSize)
        {
            printf("栈空\n");
            return 0;
        }
        switch(i)
        {
          case 0:s->stack[s.top[0]--]; break;
          case 1:s->stack[s.top[1]++];
        }
       
         return 1;  
    
    }

附注：

switch（c）语句中c可以是int、long、char、unsigned int等类型， 唯独不可以是float类型

# 队列 #

### 题一： ###

[Link 1]: https://blog.csdn.net/yaya_12345678/article/details/118729028
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70]: /images/20221005/72f161743d2d460db78aba7fa46be7c7.png