C语言双栈实现队列时出现意外行为的问题排查

问题根源 #

代码里的st2 = st1是核心错误：结构体赋值会直接复制指针a，导致st1.a和st2.a指向同一块堆内存。操作任意一个栈的数组时，另一个栈的数组都会被同步修改，这就是出队时st1首个元素被覆盖的原因。同时，程序退出时free(st1.a)和free(st2.a)会重复释放同一块内存，触发未定义行为。

修复方案 #

给st2单独分配独立的堆内存，不要直接复制结构体：

• 替换st2 = st1;为单独的内存分配和初始化
• 确保两个栈的top各自初始化为-1，独立维护栈顶指针

修复后的完整代码 #

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct stack
{
    char name[5] ;
    int top ; 
    int *a ; 
}Stack ;
int n ; 

void push(Stack*,int) ; 
int delete(Stack*,Stack*) ;
void display(Stack*) ;
int pop(Stack*) ;

int main()
{
    printf("Enter the size of the queue: ") ;
    scanf("%d",&n) ;
    Stack st1,st2 ; 
    // 初始化st1
    st1.a = (int*)malloc(n*sizeof(int)) ;
    st1.top = -1 ; 
    strcpy(st1.name,"st1") ;
    // 单独初始化st2，分配独立内存
    st2.a = (int*)malloc(n*sizeof(int)) ;
    st2.top = -1 ; 
    strcpy(st2.name,"st2") ;

    while(1)
    {
        printf("Enter 1. to insert.\nEnter 2. to delete.\nEnter 3. to display.\nEnter anything else to exit.\n") ; 
        char c ; 
        int e ;
        scanf(" %c",&c) ; 
        switch(c)
        {
            case '1': 
            printf("Enter the no. to be inserted: ") ;
            scanf("%d",&e) ; 
            push(&st1,e) ;
            break ; 
            case '2' :
            e = delete(&st1,&st2) ; 
            printf("%d got deleted.\n",e) ;
            break ; 
            case '3' : 
            display(&st1) ;
            break ; 
            default : 
            free(st1.a) ; 
            free(st2.a) ; 
            return 0 ;
        }
    }
}

int delete(Stack *st1,Stack *st2)
{
    while(st1->top!=-1)
        push(st2,pop(st1)) ;

    int e = pop(st2) ; 

    while(st2->top!=-1)
        push(st1,pop(st2)) ;

    return e ;
}

void push(Stack *st,int e)
{
    printf("Operations on %s begin: \n",st->name) ;
    printf("Currently %s:\n",st->name) ;
    display(st) ;
    st->top++ ; 
    if(st->top==n)
    {
        printf("Queue full.\n") ;
        st->top-- ;
        return ; 
    }
    st->a[st->top] = e ;
    printf("After operations , %s:\n",st->name) ;
    display(st) ;
    printf("Operations on %s end.\n\n",st->name) ;
}

int pop(Stack *st)
{
    printf("Operations on %s begin: \n",st->name) ;
    display(st) ;
    if(st->top==-1)
    {
        printf("Queue is empty.\n") ;
        return -1 ;
    }
    int e = st->a[st->top] ; 
    st->top-- ; 
    printf("After operations , %s:\n",st->name) ;
    display(st) ;
    printf("Operations on %s end.\n\n",st->name) ;
    return e ;
}

void display(Stack *st)
{
    if(st->top==-1)
    {
        printf("Queue is empty.\n") ;
        return ;
    }
    int i ;
    for(i=0;i<=st->top;i++)
        printf("%d ",st->a[i]) ;
    printf("\n") ;
}

调试验证 #

修复后执行相同操作，出队时不会再出现元素覆盖：

Enter the size of the queue: 5
Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
1
Enter the no. to be inserted: 1
Operations on st1 begin: 
Currently st1:
Queue is empty.
After operations , st1:
1 
Operations on st1 end.

Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
1
Enter the no. to be inserted: 2
Operations on st1 begin: 
Currently st1:
1 
After operations , st1:
1 2 
Operations on st1 end.

Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
2
Operations on st1 begin: 
1 2 
After operations , st1:
1 
Operations on st1 end.

Operations on st2 begin: 
Currently st2:
Queue is empty.
After operations , st2:
2 
Operations on st2 end.

Operations on st1 begin: 
1 
After operations , st1:
Queue is empty.
Operations on st1 end.

Operations on st2 begin: 
Currently st2:
2 
After operations , st2:
2 1 
Operations on st2 end.

Operations on st2 begin: 
2 1 
After operations , st2:
2 
Operations on st2 end.

Operations on st2 begin: 
2 
After operations , st2:
Queue is empty.
Operations on st2 end.

Operations on st1 begin: 
Currently st1:
Queue is empty.
After operations , st1:
2 
Operations on st1 end.

1 got deleted.

内容的提问来源于stack exchange，提问作者M.B.