精华内容
下载资源
问答
  • 栈的定义(特点:FILO) 是一种只能在一端进行插入或删除操作的线性表。 其中允许进行插入或删除操作的一端称为栈顶(Top),栈顶由一个称为栈顶...栈的插入和删除操作一般称为入栈和出栈。 栈的数学性质 当n...

     

    栈的定义(特点:FILO

    是一种只能在一端进行插入或删除操作的线性表。

    其中允许进行插入或删除操作的一端称为栈顶(Top),栈顶由一个称为栈顶指针的位置指示器(对于顺序栈,就是记录栈顶元素所在数组位置标号的一个整型变量;对于链式栈,就是记录栈顶元素所在结点地址的指针)来指示,它是动态变化的。表的另一端称为栈底,是固定不变的。栈的插入和删除操作一般称为入栈和出栈。

    栈的数学性质

    当n个元素以某种顺序进栈,并且可在任意时刻出栈(在满足先进后出的前提下),所获得的元素排列数目N恰好满足函数Catalan()的计算,即

                                                                             N=\frac{1}{n+1}C_{2n}^{n}

    队列的定义(特点:FIFO

    仅允许在表的一端进行插入,在表的另一端进行删除。可 进行插入的一段称为队尾(Rear),可进行删除的一端称为队头(Front)。

    A.顺序栈(较为重要70%)

    /*顺序栈定义*/
    typedef struct
    {
        int data[maxSize];
        int top;
    }SqStack;

    几个状态:1)栈空状态st.top==-1;2)栈满状态st.top==maxSize-1;3)非法状态(上溢和下溢)

    两个操作:1)元素x进栈操作++(st.top);st.data[st.top]=x;    2)元素x出栈操作x=st.data[st.top];--(st.top);

    /*初始化栈*/
    void initStack(SqStack &st)
    {
        st.top=-1;
    }
    
    /*判断栈空*/
    int isEmpty(SqStack st)
    {
        if (st.top==-1)
            return 1;
        else
            return 0;
    }
    
    /*进栈*/
    int push(SqStack &st,int x)
    {
        if (st.top==maxSize-1)
            return 0;
        ++(st.top);
        st.data[st.top]=x;
        return 1;
    }
    
    /*出栈*/
    int pop(SqStack &st,int &x)
    {
        if (st.top==-1)
            return 0;
        x=st.data[st.top];
        --(st.top);
        return 1;
    }
    
    /*简写形式*/
    int stack[maxSize];
    int top=-1;
    
    
    stack[++top]=x;    //元素x进栈
    
    x=stack[top--];    //元素x出栈

    B.链栈(次要30%)

    /*链栈结点定义*/
    typrdef struct LNode
    {
        int data;  //数据域
        struct LNode *next;  //指针域
    }LNode;

    两个状态:1)栈空 lst->next==NULL  2)栈满 不存在栈满的情况

    两个操作:1)元素(由p指针所指)进栈  p->next=lst->next; lst->next=p;  //头插法建立链表中的插入操作

                      2)出栈(出栈元素保存在x中)p=lst->next; x=p->data; lst->next=p->next; free(p);  //单链表的删除操作

    /*链栈的初始化*/
    void initStack(LNode *&lst)
    {
        lst=(LNode*)malloc(sizeof(LNode));
        lst->next=NULL;
    }
    
    /*判空*/
    int isEmpty(LNode *lst)
    {
        if (lst->next==NULL)
            return 1;
        else
            return 0;
    }
    
    /*进栈*/
    void push(LNode *lst,int x)
    {
        LNode *p;
        p=(LNode*)malloc(sizeof(LNode));
        p->next=NULL;
        /*以下为链表的头插法*/
        p->data=x;
        p->next=lst->next;
        lst->next=p;
    }
    
    /*出栈*/
    int pop(LNode *lst,int &x)
    {
        LNode *p;
        if (lst->next==NULL)
            return 0;
        /*以下为单链表的删除操作*/
        p=lst->next;
        x=p.data;
        lst->next=p->next;
        free(p);
        return 1;
    }

    顺序队

    /*顺序队列定义*/
    typedef struct
    {
        int data[maxSize];
        int front;  //队首“指针”
        int rear;  //队尾“指针”
    }SqQueue;  //顺序队类型定义

    循环队列的要素

    两个状态:1)队空状态 qu.rear==qu.front    2)队满状态 (qu.rear+1)%maxSize==qu.front

    两个操作:

    /*元素x进队*/
    qu.rear=(qu.rear+1)%maxSize;
    qu.data[qu.rear]=x;
    /*元素x出队*/
    qu.front=(qu.front+1)%maxSize;
    x=qu.data[qu.front];
    /*初始化队列*/
    void initQueue(SqQueue &qu)
    {
        qu.front=qu.rear=0;  //队首和队尾指针重合并且指向0
    }
    
    /*判空*/
    int isQueueEmpty(SqQueue qu)
    {
        if (qu.rear==qu.front)  //不论队首、队尾指针指向数组中的哪个位置
            return 1;           //只要两者重合,即为队空
        else
            return 0;
    }
    
    /*进队*/
    int enQueue(SqQueue &qu,int x)
    {
        if ((qu.rear+1)%maxSize==qu.front)  //队满的判断条件
            return 0;
        qu.rear=(qu.rear+1)%maxSize;  //先移动指针
        qu.data[qu.rear]=x;  //再存入元素
        return 1;
    }
    
    /*出队*/
    int deQueue(SqQueue &qu,int &x)
    {
        if (qu.front=qu.rear)  //队空的判断条件
            return 0;
        qu.front=(qu.front+1)%maxSize;  //先移动指针
        x=qu.data[qu.front];  //保存出队元素
        return 1;
    }

    链队定义

    /*1).队结点类型定义*/
    typedef struct QNode
    {
        int data;
        struct QNode *next;
    }QNode;
    
    /*2).链队类型定义*/
    typedef struct
    {
        QNode *front;  //队头指针
        QNode *rear;   //队尾指针
    }LiQueue;  //链队类型定义

     

    展开全文
  • 队列的基本概念

    2020-07-26 16:41:29
    栈和队列的基本概念 一、 栈的基本概念 1.栈的定义 栈是一种只能在一端进行插入或...栈的插入和删除操作一般 称为入栈和出栈。 2.栈的特点 由栈的定义可以看出,栈的主要特点就是先进后出(FILO)。栈中的元素就好比开进

    栈和队列的基本概念

    一、 栈的基本概念

    1.栈的定义
    栈是一种只能在一端进行插入或删除操作的线性表。其中允许进行插入或删除操作的一端称为栈顶(Top)。栈项由一个称为栈顶指针的位置指示器(其实就是一个变量,对于顺序栈,就是记录栈项元素所在数组位置标号的一个整型变量:对于链式栈,就是记录栈顶元素所在结点地址的指针)来指示,它是
    动态变化的。表的另一端称为栈底,栈底是固定不变的。栈的插入和删除操作一般 称为入栈和出栈。
    2.栈的特点
    由栈的定义可以看出,栈的主要特点就是先进后出(FILO)。栈中的元素就好比开进一个死胡同的车队,最先开进去的汽车只能等后进来的汽车都出去了,才能出来。
    3.栈的存储结构
    可用顺序表和链表来存储栈,栈可以依照存储结构分为两种:顺序栈和链式栈。在找的定义中已经说明,栈是一种在操作上稍加限制的线性表,即栈本质上是线性表,而线性表有两种主要的存储结构——顺序表和链表,因此栈也同样有对应的两种存储结构。
    4.栈的数学性质
    当n个元素以某种顺序进栈,并且可在任意时刻出栈(在满足先进后出的前提下)时,所获得的元素排列的数目N恰好满足函数Catalan()的计算,即
    在这里插入图片描述

    二、队列的基本概念

    1.队列的定义
    队列简称队,它也是一种操作受限的线性表,其限制为仅允许在表的一端进行插入,在表的另一端进行删除。可进行插入的一端称为队尾(Rear), 可进行删除的一端称为队头(Front)。向队列中插入新的元素称为进队,新元素进队后就成为新的队尾元素:从队列中删除元素称为出队,元素出队后,其后继元素就成为新的队头元素。
    2.队列的特点
    队列的特点概括起来就是先进先出(FIFO)。 打个比方,队列就好像开进隧道的一列火车, 各节车厢就是队中的元素,最先开进隧道的车厢总是最先驶出隧道。
    3.队列的存储结构
    可用顺序表和链表来存储队列,队列按存储结构可分为顺序队和链队两种。

    展开全文
  • 顺序栈

    2021-04-12 22:35:40
    3.1 顺序栈的建立 1.建立一个字符栈,从键盘输入若干个字符,以回车...注意入栈出栈时栈顶指针TOP的不同变化及栈空的判断条件。建立一个头文件SeqStack.h,包含顺序栈的定义、初始化等。 3.参考程序 // 头文件SeqStac

    3.1 顺序栈的建立

    1.建立一个字符栈,从键盘输入若干个字符,以回车键结束,实现元素入栈操作;然后依次输出栈中的字符元素,实现元素出栈操作

    2.实验要求和说明
    参考程序中,由InitStack_Seq函数分配一个指定大小的字符数组空间,在分配成功地情况下,从键盘输入若干个字符,实现进栈操作。然后依次输出栈中元素的值,其输出顺序恰与输出顺序相反。注意入栈,出栈时栈顶指针TOP的不同变化及栈空的判断条件。建立一个头文件SeqStack.h,包含顺序栈的定义、初始化等。
    3.参考程序

    // 头文件SeqStack.h
    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    //#include <string.h>
    #define  STACK_INIT_SIZE 50          // 存储空间初绐分配量
    #define  STACKINCREMENT 50   // 存储空间分配增量
    #define  OK 1
    #define  ERROR -1
    #define  OVERFLOW 0
    
    typedef struct SeqStack
    { // 顺序栈类型定义
        int   MAXSIZE;       // 栈中最大元素的个数(即栈空间的大小)
        int   top;           // 栈顶指针
    	char *selem;         
    }SeqStack,*PSeqStack;
    
    //typedef struct SeqStack *PSeqStack;
    
    int InitStack_Seq(PSeqStack S)    // 初始化顺序栈,见图3-11
    {
    	S->selem = (char*)malloc(STACK_INIT_SIZE*sizeof(char));
    	if(!(S->selem))
    		exit(OVERFLOW);
    	S->top=-1;
    	S->MAXSIZE=STACK_INIT_SIZE;
    	return OK;
    }
     
    
    int IsEmptyStack_Seq(PSeqStack S)
    {// 判栈是否为空
    	return( S->top == -1 ? OK : ERROR);
    }
    
    int IsFullStack_Seq(PSeqStack S)
    {// 判栈是否满
    	return(S->top >= S->MAXSIZE-1 ? OK : ERROR);
    }
    
    int Push_Seq(PSeqStack S, char x)
    {// 元素进栈
    	if(S->top >= S->MAXSIZE-1)
    	{ 
    		printf("Overflow!\n");
            return ERROR;
    	}
            S->top++;
            S->selem[S->top] = x;
            return OK;
    }
    
    int Pop_Seq(PSeqStack S, char *e)
    {// 元素出栈
    	if(S->top == -1)
    	{
    		printf("Underflow!\n");
            return ERROR;
    	}
    	*e = S->selem[S->top]; 
        S->top--;
        return OK;
    }
    
    int GetTop_Seq(PSeqStack S, char *e)
    {// 取栈顶元素
    	if(S->top == -1)
    	{ 
    		printf("Underflow!\n");
    		return ERROR;
    	}
        *e = S->selem[S->top];
    	return OK;
    }
    // 头文件SeqStack.h 结束
    
    void main( )
    {
    	SeqStack S_seq;
    	PSeqStack S;
    	char ch;
    	S = &S_seq;
    	
    	InitStack_Seq(S);
    	printf("Input the datas to the stack, end Input \\n: ");
        ch = getchar();
        while( ch != '\n' && Push_Seq(S, ch)) 
    	{
            ch = getchar();    
    	} 
    	printf("Output the datas in the stack: ");
    	for(;S->top != -1; S->top--)    // 栈中元素出栈
    		printf("%c", S->selem[S->top]);
    	printf("\n");
    
    3.思考题
    (1)如果栈中的元素为结构类型,如何建立一个顺序栈?
    
    typedef struct SeqStack
    {
    	int MAXSIZE;		//栈中最大元素的个数(即栈空间的大小) 
    	int top;			//栈顶指针 
    	struct Student *selem;		 //结构体类型的元素指针
    }SeqStack,*PSeqStack;
    
    //定义一个Student结构体,只需要把结构体地址传给栈的selem就可以了,为了方便,用结构体数组来存储。
    typedef struct Student
    {
    	int id;		//学号 
    	char sex;	//性别 F/M 
    	char name[11];	//名字 
    }Student,*Stu;
    
    
    int Push_Seq(PSeqStack S,Student x) { ......}    //函数里边内容不变
    
    int Pop_Seq(PSeqStack S,Student *e){......}
    
    int GetTop_Seq(PSeqStack S,Student *e){......}
    
    int main()
    {
    	SeqStack S_seq;
    	PSeqStack S;
    	S = &S_seq;	int i=-1,n;
    	InitStack_Seq(S);
    	
    	struct Student stu[50];
    	
    	do{
    		i++;
    		printf("请输入第%d个学生的信息 id sex name(0 0 0 结束):", i);
            scanf ("%d %c %s",&stu[i].id, &stu[i].sex, stu[i].name);
    	}
    	while(stu[i].id != 0 && Push_Seq(S,stu[i]));
    	
    	
    	printf("Output the datas in the satck:");
    	for(;S->top != -1; S->top--)
    	{
    		*stu = S->selem[S->top];
    		printf("id: %d ,sex: %c ,name: %s \n",stu->id,stu->sex,stu->name);
    	}
    		
    	printf("\n");
    	
    	return 0;
    }
    

    (2)设计一个算法,利用栈的基本运算,返回指定顺序栈中的栈底元素。

    int GetSelem_Seq(PSeqStack S,char *e)
    {
    	//取栈底元素、若栈i非空,用变量*e返回栈顶元素
    	int i;
    	printf("top = %d\n",S->top);
    	if(S->top <= -1)	
    	{
    		printf("The Stack is NULL!\n");
    		return ERROR;
    	}
    	else
    		*e = S->selem[0];
    
    	return OK;
    }
    

    3.2 顺序栈的共享共用

    1.建立两个迎面增长的共享栈Stack0,Stack1,栈元素为char类型。分别完成建栈、取栈顶元素及求栈的长度(栈元素的个数)操作。建栈时,支持字符元素连续输入。
    2.实验要求及说明
    顺序栈共用,即使多个顺序栈共用一个足够大的数组空间,并利用栈的动态特性使其存储空间互补。下面实现的两个顺序栈共用算法可以推广到多个共用栈。
    参考程序中设置了一个结构类型:DseqStack,用于描述两个迎面增长的共享栈的状态。程序中利用整型变量i控制对不同栈的操作。注意两个共享栈Stack0,Stack1的栈底位置的不同和栈顶指针变化的差异。两个顺序栈共用结构示意图如图所示。

    3.参考代码

    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    #define   STACK_INIT_SIZE 10
    #define   OK 1
    #define   ERROR -1
    #define   OVERFLOW 0
    
    typedef struct DSeqStack
    { // 共用栈的结构定义
    	char  *selem[2];      // 两个栈的栈底指针
    	int    top[2];         // 两个栈的栈顶指针
        int   MAXSIZE;         // 共用栈的大小
    }DSeqStack, *PDSeqStack;/
    
    int InitStack_DSeq(PDSeqStack S) 
    { // 初始化共享栈DSeq
      // 分别设置 Stack0、Stack1 的栈底指针selem[0]、selem[1]
    	S->selem[0]=(char *)malloc(STACK_INIT_SIZE*sizeof(char));  
    	if(!S->selem[0])
    		exit(OVERFLOW);
        S->MAXSIZE = STACK_INIT_SIZE;
    	S->selem[1]= S->selem[0]+S->MAXSIZE-1;     // 设置 Stack1 的栈底指针selem[1]//
    	S->top[0] = -1;                 		  // 栈 Stack0 的初始状态
    	S->top[1] = S->MAXSIZE;                   // 栈 Stack1 的初始状态///
    	return OK;
    }
    
    int CreateStack_DSeq(PDSeqStack S, int i)
    { // 建立顺序字符栈i
    	char ch;
    	if(i==0)
    	{ // 建立栈Stack0
    		while((ch = getchar())!='\n')
    		{
    			S->top[0]++;
    			if(S->top[0] >= S->top[1])
    			{
    				printf("The stack is full!\n");
    				exit(OVERFLOW);
    			}
               else 
                    S->selem[0][S->top[0]] = ch;//
    		}
    	}
    	if(i==1)                                 			
    	{ // 建立栈Stack1
    		while((ch = getchar())!='\n')
    		{
    			S->top[1]--;
    			if(S->top[1] <= S->top[0])
    			{
    				printf("The stack is full!\n");
    				exit(OVERFLOW);
    			}
                else 
    				S->selem[1][S->top[1]] = ch;//
    		}
    	}
    	return OK;
    }
    
    int GetTop_DSeq(PDSeqStack S, int i, char *e)     
    { // 取栈顶元素。若栈 i 非空,用变量 *e 返回栈顶元素
        if(i==0)
    	{
            if(S->top[0] <= -1)//
    		{
                printf("The stack%d is NULL!\n",i);
                return ERROR;
            }
            else 
                *e = S->selem[0][S->top[0]];///
    	}
        if(i==1)
    	{
    	    if(S->top[1] >= S->MAXSIZE)///
    		{
                printf("The stack%d is NULL!\n",i);
                return ERROR;
            }
            else 
                *e = S->selem[1][S->top[1]];///
    	}
    	return OK;
    }// end GetTop_DSeq
    
    
    int GetDepth_DSeq(PDSeqStack S, int i)    
    {  // 求栈i中元素的个数。
    	int t,p1,p2;
    	p1 = S->top[0];//
    	p2 = S->top[1];//
    	if(i==0)
    	{
    		for(t=0; p1 >-1; t++,p1--);
    	}
    	if(i==1)
    	{
    		for(t=0; p2<S->MAXSIZE; t++,p2++);
    		
    	}
    	return t;
    }
    
    void main( )
    {
    	DSeqStack s;
        PDSeqStack S;
    	int i,t,k;
    	char e;
    	S = &s;
    	InitStack_DSeq(S);
    	printf("Enter 0 for the left stack0 operation\n");
    	printf("Enter 1 for the right stack1 operation:");
    	for(;;)
    	{
    		printf("\n1: createstack, 2: gettop, 3: getlength. please enter k=");
    		scanf("%d",&k);
    		//fflush(stdin);         // 清除回车键
    		switch(k)
    		{
    		   case 1: printf("\n now begin CreateStack_DSeq: please Enter i=");
    			       scanf("%d",&i);
                       fflush(stdin); 
    		           if(i==0)
    				   {
    			           printf("Input the datas of char to the stack 0: ");
    			           CreateStack_DSeq(S,0);
    				   }
    				   if(i==1)
    				   {
                           printf("Input the datas of char to the stack 1: ");
    			           CreateStack_DSeq(S,1);
    				   }
    				   break;
    		   case 2: printf("\n now begin GetTop of stack. please Enter i=");
    			       scanf("%d",&i);
    				   //fflush(stdin); 
                       if(i==0)
    				   {
    			           if(GetTop_DSeq(S,0,&e))
    					       printf("\nThe data on the top  of the left stack0 is %c",e);
    					   else
    						    printf("The left stack0 is empty!\n");
    				   }
    				   if(i==1)
    				   {
                           if(GetTop_DSeq(S,1,&e))
    						   printf("\nThe data on the top  of the left stack1 is %c",e);
    					   else
                               printf("The left stack1 is empty!\n");
    				   }
    				   break;
    		   case 3: printf("\n now begin GetDepth of stack. please Enter i=");
    			       scanf("%d",&i);
                       //fflush(stdin); 
    				   if(i==0)
    				   {
    			           t=GetDepth_DSeq(S,0);
    					   printf("the depth of the left stack0 is %d\n",t);
    				   }
    				   if(i==1)
    				   {
                           t=GetDepth_DSeq(S,1);
    			           printf("the depth of the right stack1 is %d\n",t);
    				   }
    				   break;
    		   default: exit(0);
    		}//endswitch
    	}//endfor
    }//endmain
    
    

    4.思考题
    (1)如何用函数实现栈中元素的出栈操作?试修改上述程序,对于一个非空栈,实现删除栈顶元素,并由变量e返回其值的算法

    int DeleteTop_DSeq(PDSeqStack S,int i,char *e)
    {
    	//取栈顶元素、若栈i非空,用变量*e返回栈顶元素
    	if(i==0)
    	{
    		if(S->top[0] <= -1)
    		{
    			printf("The stack%d is NULL!\n",i);
    			return ERROR;
    		 }
    		else
    			*e = S->selem[0][S->top[0]];
    			S->top[0]--;
    	}
    	if(i==1)
    	{
    		if(S->top[i] >= S->MAXSIZE)
    		{
    			printf("The stack%d is NULL!\n");
    			return ERROR;
    		}
    		else
    			*e = S->selem[1][S->top[1]];
    			S->top[0]++;
    	}
    	return OK;
    }//end DeleteTop_DSeq
    
    
    Int main()
    {
      ......
         While ....
                .......
                case 4:printf("\n now begin DeleteTop of stack.please Enter i= ");
    				scanf("%d",&i);
    				//fflush(stdin);
    				if(i==0)
    				{
    					if(DeleteTop_DSeq(S,0,&e))
    						printf("\nThe data on the top of the left stack0 is %c",e);
    					else
    						printf("The left stack0 is empty!\n");
    				}
    				if(i==1)
    				{
    					if(DeleteTop_DSeq(S,1,&e))
    						printf("\nThe data on the top  of the left stack1 is %c",e);
    					else
    						printf("The left stack1 is empty!\n");
    				}
    				break;
    }
    

    (2)在栈的操作中,栈满时仍进行入栈操作称为“上溢”,栈空时仍进行出栈操作称为“下溢”,试分析这两种溢出中的哪一种是正常现象?哪一种是错误状态。

    栈溢出属于系统重大漏洞,这种漏洞将会产生相当严重网络安全事件。

    展开全文
  • 1.1 栈和队的基本概念 1.1.1 栈的基本概念 栈的定义 栈是只能在一段进行数据插入和...插入数据和删除数据被称为入栈和出栈。 2. 栈的特点 栈的特点是先进后出。栈的数据形态就好比是叠放成一列的盘子,最先...

    1.1 栈和队的基本概念

    1.1.1 栈的基本概念

    1. 栈的定义

           栈是只能在一段进行数据插入和删除的线性表。允许进行数据插入和删除的一端称为栈顶(top),栈顶由一个成为栈顶指针的位置指示器来表示,是动态变化的。表的另一端成为栈底,是固定不变的。插入数据和删除数据被称为入栈和出栈

        2. 栈的特点

          栈的特点是先进后出。栈的数据形态就好比是叠放成一列的盘子,最先放入的在底端,最后放入的在顶端,拿取时也是后放入的先被拿出。

        3. 栈的存储结构

            可用顺序表和链表来存储,即按照存储结构的不同,分为顺序栈和链表栈。

        4. 栈的数学性质

            当n个元素以某种顺序进栈,并且可以在任意时刻出栈(在满足先进先出的前提下),所获得的元素排列的数目N恰好满足函数Catalan() 的计算。

    1.2 栈的储存结构、算法和应用

    1.2.1栈的结构体定义

          1. 顺序栈的定义

    typedef struct
    {
        int data[MaxSize]; //MaxSize为已被定义的const常量;
        int top; //栈顶指针
    }sqStack;

          2. 链栈节点定义

    typedef struct LNode
    {
        int data;   // 数据域
        struct LNode *next //指针域
    }LNode;//链栈节点定义

    1.2.2 顺序栈

    1. 顺序栈的要素

    顺序栈st有两个特殊状态

    1)栈空状态

    st.top == -1;

       栈空就是继续出栈会出现下溢的情矿

     

    2)栈满状态

    st.top = maxSize-1; //maxSize为栈中最大元素的个数,maxSize-1为栈满时栈顶元素在数组中的位置;

      栈满就是就是继续入栈会出现上溢的状态。

    顺序栈st的两个操作

    1)元素x进栈操作

    ++(st.top); //先移动指针,因为规定top=-1时为空栈;
    st.data[st.top] = x;
    

    2)元素x出栈操作

    x= st.data[st.top];//进栈操作决定了出栈操作的次序
    --(st.top);

    2. 初始化栈

    只需要将栈顶指针置为-1

    void initStacke(SqStacke &st)
    {
        st.top = -1;
    }

    3. 判断栈是否为空

    void isEmpty(SqStack &st)
    {
        if(st.top == -1)
            return 1;    //栈为空时返回1
        else
            
            return 0;
    }

    4. 进栈代码

    void push(SqStack &st, int x)
    {
        if(st.top == maxSize-1) //如果栈满则不能进栈;
            return 0;
        ++(st.top);            //先移动指针,再进栈;
        st.data[st.top] = x;
        return 1;
    }

     5. 出栈代码

    void pop(SqStack &st, int &x)
    {
        if(st.top == -1)   //如果栈空,则不出栈
            return 0;
        x = st.data[st.top];
        --(st.top);
     }
    

    6. 简单且使用的栈的定义方式

    //定义一个栈,且初始化,类型为int
    
    int stack[maxSize];
    int top = -1;
    
    // 进栈
    stack[++top] = x;
    
    //出栈
    x = stack[top--];
    

    1.2.3 链栈

    1. 链栈的要素

    两个状态:

    1)空栈状态

    lst->nest == NULL;

     2) 栈满状态

    假设内存无限大,不存在栈满的情况

    两个操作:

    1)元素(由指针P所指)进栈

    p->nest = lst->nest;
    list->nest = p;

    2)出栈,出栈元素保存在x

    P = lst->nest; //其实就是单链表的删除操作;
    x = p->data;
    lst->next = p->nest;
    free(p);

    2. 链栈的初始化代码

    void initStack(LNode *&lst)
    {
        lst = (LNode*)malloc(sizeof(LNode))
        lst->next = NULL;
    }

    3. 判断栈空代码

    void isEmpty(LNode *lst)
    {
        if(lst->next == NULL)
            return 0;
        else
            return 1;
    }

    4. 进栈代码

    void push(LNode *lst,int x)
    {
        LNode *p;
        p = (LNode*)malloc(sizeif(LNOde)); //为进栈元素申请结点空间
        p->next = NULL; //此函数中不写此句也正确,但每当申请新结点时,将其指针域设置为NULL是可以避免一些错误的好习惯;
        p->data = x; //以下三句是链表的头插法;
        p->next = list->next;
        lst->next = p;
    }

    5. 出栈代码

    int pop(LNode *lst, int &x)
    {
        LNode *p;
        if(Lst->next == NULL)
            return 0;
        p = lst->next; //以下是单链表的删除操作
        x = p->data;
        lst->next = p->next;
        free(p);
        return 1;
    }

    1.2.4 栈的应用

    1.顺序栈的应用

    /*题目1:判断一个表达式中的括号是否配对出现(C语言表达式中只有小括号)
    
      表达式已经存入字符数组exp[]中,表达式的字符个数是n
    */
    int match(char exp[],int n)
    {
        char stack[maxSize];
        int top = -1;
        
        int i;
        for(i = 0; i <n;i++)
        {
            if(exp[i] == '(')
                stack[++top] = exp[i]
            if (exp[i] == ')' 
            {
                if(top == -1)
                    return 1;
                else
                    --top;
            }
        }
        
        if(top== -1) //栈空,表示所有括号都匹配被划掉
            return 0;
        else 
            return 1;//括号不匹配
    }

    2. 链栈的应用

    /* 题目2 用不带头结点的单链表存储链栈,设计初始化栈,判断栈是否为空,进栈和出栈等相应的算法
       分析:不带头结点的单链表lst为空的条件是lst == NULL,进栈和出栈操作都是在表头进行的
    */
    //初始化栈
    void initStack(LNode *&lst)
    {
        lst = NULL;
    }
    
    //判断栈是否为空
    int isEmtpy(LNode *lst)
    {
        if(lst == NULL)
            return 0;
        else 
            return 1;
    }
    
    //进栈
    void push(LNode *&lst, int x)
    {
        LNOde *P;
        p = (LNode *)malloc(sizeof(LNode));
        p->next = NULL;
        p->data = x;
        
        p->next = lst;
        lst = p;
    }
    
    //出栈
    int pop(LNode *&lst, int &x)
    {
        LNode *p;
        if(lst == NULL)
            return 0;
        p = lst;  //P指向第一个数据结点
        x = p->data;
        lst = p->next;
        free(p);
        return 0;
    }
    

     

    展开全文
  • 顺序栈的建立及基本操作 栈的定义 栈是一种只能在一端进行插入和删除操作的线性表。其中允许进行插入和删除操作的一...栈的插入和删除操作一般称为入栈和出栈。 栈的特点 栈的主要特点就是先进后出(FILO)。...
  • 2020-02-14 11:09:36
    (而栈顶是随着插入删除而变化的,可以用一个整形变量top存放栈顶的指针,数据入栈出栈时使整形变量 top分别加1或减1。) 2.栈的基本操作: (1)初始化栈 stackvis ,定义一个栈 (2)入栈 vis.push(x) (3)...
  • 栈的基本操作

    2018-10-04 17:01:05
    1.栈的基本概念 栈是一种只能在一端进行插入或者删除操作的...栈的插入和操作一般称为入栈和出栈。 2.栈的特点 先进先出 3.栈的存储结构 顺序栈和链栈 4.栈的数学性质(稍后会有相关习题) 当n个编号元素以某...
  • C/C++ Stack (栈)

    千次阅读 2020-01-08 13:59:26
    在数组上实现时,栈底位置可以设置在数组的任一个端点,而栈顶是随着插入删除而变化的,可以用一个整形变量 top 存放栈顶的指针,数据入栈出栈时使整形变量 top 分别加1或减1。 Code 注意:部分题目 top-- 之前....
  • 栈的基本操作(一)

    千次阅读 2016-10-15 15:56:04
    1.栈的基本概念栈是一种只能在一端进行插入或删除操作的线性表。其中允许进行插入或删除操作的一端称为(Top),栈顶由一个称为栈顶指针的...栈的插入和操作一般称为入栈和出栈。本篇文章以顺序栈为主。栈的特点先进先
  • 栈这块的知识我卡了好久,最终...在数组上实现时,栈底位置可以设置在数组的任一个端点,而栈顶是随着插入删除而变化的,可以用一个整形变量top存放栈顶的指针,数据入栈出栈时使整形变量 top分别加1或减1。 重...
  • 概念 1.栈的定义 栈是一种只能在一端进行插入...栈的插入和删除操作一般称为入栈和出栈。 2.栈的特点 由栈的定义可以看出,栈的主要特点就是先进后出(FILO).栈中的元素就好比开进一个死胡同的车队,最先开进去的..
  • 栈顶(Top):允许插入删除的一端,为 变化的一端。称为栈顶 栈底(Bottom):另一端为 固定的一端,称为栈底 单向链表如图所示: 解题:栈的实现可以用数组、链表来实现 定义一个数据存储类型,栈顶指针 入栈...
  • 类似于顺序表的定义,栈中的数据元素用一个预设的足够长度的一维数组来实现:datatype data[MAXSIZE],栈底位置可以设置在数组的任一个断点,而栈顶是随着插入删除而变化的,用一个 int top来作为栈顶的指针,指明...
  • 队列

    2020-08-23 20:50:34
    栈(stack)作为一种限定性线性表,是将线性表的插入删除运算限制为仅在表的一端进行,通常将表中允许进行插入、删除操作的一端称为栈顶(Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置...
  • 栈限制其元素只能在线性表的同一端进行插入和删除操作,允许变化的这一端被称为栈顶(Top),固定的一端称为栈底(Bottom),栈的基本操作有入栈(push)和出栈(pop) 图示: 用数组实现栈 图示: 由于栈的...
  • 顺序栈:利用顺序存储方式实现的栈。 顺序栈的定义: (1):栈中元素用一个预设的足够长度的一维数组来实现:DataType data[MAXSIZE]。 (2):栈底位置可以设置...入栈时栈顶指针+1,出栈时栈顶指针-1。 顺序栈的存储结构
  • 目录 3.栈 4.队列 3.栈 (1)定义 栈是一种只能在一端进行插入或删除操作的线性表,因此根据存储结构的...栈的插入和删除操作一般称为入栈(push)和出栈(pop)。栈最主要的特点就是先进先出。 (2)声明...
  • 限定性线性表——栈

    2018-04-21 22:36:55
    栈作为一种限定性顺序表,是将线性表的插入删除操作限制为仅在表的一端进行,通常将表中允许插入、删除操作的一端称为栈顶(Top),因此栈顶的位置是动态变化的,它由一个称为栈顶指针的位置指示器来表示。...
  • 3.1栈的定义

    2020-05-28 17:20:23
    栈顶:通常将表中允许进行插入、删除操作的一端称为栈顶 (Top),因此栈顶的当前位 置是动态变化的,它由一个称为栈顶指针的位置指示器指示。 栈底:同时表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。...
  • C语言-栈

    2019-10-07 20:57:35
      栈作为一种限定性线性表,是将线性表的插入删除操作限制在仅在表的一端进行,通常将表中允许进行插入、删除操作的一端称为栈顶(Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置指示器来...
  • 将允许进行插入删除操作的一端称为栈顶(Top),栈顶的当前位置是动态变化的,由一个称为栈顶指针的位置指示器指示 表的另外一端叫做栈底,没有元素叫做空栈 插入元素叫做:入栈、进栈 删除元素叫做:出栈、退...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

入栈和出栈top指针变化