“3栈和队列”的版本间的差异

来自软件实验室
跳转至: 导航搜索
(创建页面,内容为“caption”)
 
出栈操作--pop
 
(未显示2个用户的20个中间版本)
第1行: 第1行:
[[File:链表.png|options|caption]]
+
== 栈的定义 ==
 +
=== 基本概念 ===
 +
定义:栈是限定仅在表尾进行插入和删除操作的线性表。栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,又称为LIFO结构。把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。
 +
 
 +
注意事项:首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。
 +
 
 +
基本操作:栈的插入操作,叫作进栈,也称压栈、入栈。栈的删除操作,叫作出找,也有的叫作弹栈。
 +
[[文件:栈的基本概念.jpg|缩略图]]
 +
 
 +
=== 进栈出栈变化形式 ===
 +
n个元素进栈共有多少种出栈顺序?
 +
 
 +
我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:
 +
                                    f(1) = 1    //即 1
 +
                                    f(2) = 2    //即 12、21
 +
                                    f(3) = 5    //即 123、132、213、321、231
 +
 
 +
然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。
 +
 
 +
分析:
 +
 
 +
1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);
 +
 
 +
2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2),    根据乘法原理,一共的顺序个数为f(1) * f(2);
 +
 
 +
3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),根据乘法原理,一共的顺序个数为f(2) * f(1);
 +
 
 +
4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即        f(3);结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);
 +
 
 +
为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:
 +
 
 +
f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)
 +
 
 +
然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:
 +
 
 +
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)
 +
[[文件:ruzhan.png|缩略图]]
 +
 
 +
== 栈的抽象数据类型 ==
 +
=== 栈的ADT定义 ===
 +
 
 +
ADT 栈(stack)
 +
 
 +
Data
 +
 
 +
    同线性表。元素具有相同的类型,相邻元素具有前驱和后堆关系。
 +
Operation
 +
 
 +
    InitStack ( *S ):初始化操作.建立一个空栈S。
 +
 
 +
    DestroyStack ( *S ):若栈存在,則销毁它。
 +
 
 +
    ClearStack (*S):将栈清空。
 +
 
 +
    StackEmpty ( S ):若栈为空,返回true,否則返回 false。
 +
 
 +
    GetTop (S,*e):若栈存在且非空,用e返回S的栈顶元素。
 +
 
 +
    Push (*S,e):若栈S存在,插入新元素e到栈S中并成为栈頂元素。
 +
 
 +
    Pop (*S,*e):删除栈S中栈顶元素,并用e返回其值。
 +
 
 +
    StackLength (S):返回回栈S的元素个数。
 +
 
 +
endADT
 +
 
 +
== 栈的顺序存储结构及实现 ==
 +
=== top指针 ===
 +
定义一个top变量来指示栈顶元素在数组中的位置,这top就如同中学物理学过的游标卡尺的游标,如上图所示,它可以来回移动,意味着栈顶的top可以变大变小,但无论如何游标不能超出尺的长度。同理,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。
 +
[[文件:top2.jpg|缩略图]]
 +
 
 +
=== 结构体定义 ===
 +
#include "stdio.h"
 +
 
 +
/* 存储空间初始分配量 */
 +
 
 +
#define MAXSIZE 20
 +
 
 +
/* SElemType类型根据实际情况而定,这里假设为int */
 +
 
 +
typedef int SElemType;
 +
 
 +
/* 顺序栈结构 */
 +
 
 +
typedef struct
 +
{
 +
    SElemType data[MAXSIZE];
 +
 
 +
    int top; /* 用于栈顶指针 */
 +
 
 +
}SqStack;
 +
 
 +
int main()
 +
 
 +
{
 +
 
 +
}
 +
 
 +
=== 进栈操作--push ===
 +
如图所示,进栈操作push大概分为两步:
 +
 
 +
1.栈顶指针 S->top 先自增1,给需要进栈的元素腾出内存空间;
 +
 
 +
2.再赋值。就是给对应的数组元素赋值:S->data[S->top]=e。
 +
代码实现:
 +
 
 +
/* 插入元素e为新的栈顶元素 */
 +
Status Push(SqStack *S,SElemType e)
 +
{
 +
    if(S->top == MAXSIZE -1) /* 栈满 */
 +
    {
 +
        return ERROR;
 +
    }
 +
    S->top++; /* 栈顶指针增加一 */
 +
    S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
 +
    return OK;
 +
}
 +
[[文件:入栈.jpg|缩略图]]
 +
 
 +
=== 出栈操作--pop ===
 +
代码实现:
 +
 
 +
/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
 +
 
 +
Status Pop(SqStack *S,SElemType *e)
 +
 
 +
{
 +
 
 +
    if(S->top==-1)
 +
 
 +
        return ERROR;
 +
 
 +
    *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */
 +
 
 +
    S->top--; /* 栈顶指针减一 */
 +
 
 +
    return OK;
 +
 
 +
}
 +
完整可实现代码:
 +
 
 +
#include "stdio.h"
 +
 
 +
#include "stdlib.h"
 +
 
 +
#define OK 1
 +
 
 +
#define ERROR 0
 +
 
 +
/* 存储空间初始分配量 */
 +
 
 +
#define MAXSIZE 20
 +
 
 +
typedef int Status;
 +
 
 +
/* SElemType类型根据实际情况而定,这里假设为int */
 +
 
 +
typedef int SElemType;
 +
 
 +
/* 顺序栈结构 */
 +
 
 +
typedef struct
 +
 
 +
{
 +
    SElemType data[MAXSIZE];
 +
 
 +
    int top; /* 用于栈顶指针 */
 +
 
 +
}SqStack;
 +
 
 +
/*  构造一个空栈S */
 +
 
 +
Status InitStack(SqStack *S)
 +
{
 +
    /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
 +
 
 +
    S->top=-1;
 +
 
 +
    return OK;
 +
 
 +
}
 +
 
 +
/* 从栈底到栈顶依次对栈中每个元素显示 */
 +
 
 +
Status StackTraverse(SqStack S)
 +
 
 +
{
 +
 
 +
    int i;
 +
 
 +
    i=0;
 +
 
 +
    while(i<=S.top)
 +
 
 +
    {
 +
 
 +
        visit(S.data[i++]);
 +
 
 +
    }
 +
 
 +
    printf("\n");
 +
 
 +
    return OK;
 +
 
 +
}
 +
 
 +
Status visit(SElemType c)
 +
 
 +
{
 +
 
 +
    printf("%d ",c);
 +
 
 +
    return OK;
 +
}
 +
 
 +
/* 插入元素e为新的栈顶元素 */
 +
 
 +
Status Push(SqStack *S,SElemType e)
 +
 
 +
{
 +
 
 +
    if(S->top == MAXSIZE -1) /* 栈满 */
 +
 
 +
    {
 +
 
 +
        return ERROR;
 +
 
 +
    }
 +
 
 +
    S->top++; /* 栈顶指针增加一 */
 +
 
 +
    S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
 +
 
 +
    return OK;
 +
 
 +
}
 +
 
 +
/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
 +
 
 +
Status Pop(SqStack *S,SElemType *e)
 +
 
 +
{
 +
 
 +
    if(S->top==-1)
 +
 
 +
        return ERROR;
 +
 
 +
    *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */
 +
 
 +
    S->top--; /* 栈顶指针减一 */
 +
 
 +
    return OK;
 +
}
 +
 
 +
int main()
 +
 
 +
{
 +
 
 +
    SqStack s;
 +
 
 +
    int opp;
 +
 
 +
    int j, value, e;
 +
 
 +
    if(InitStack(&s)==OK)
 +
 
 +
    {
 +
 
 +
        printf("顺序栈初始化成功。");
 +
 
 +
        StackTraverse(s);
 +
 
 +
    }
 +
 
 +
    printf("\n1.随机给栈赋值 \n2.栈遍历 \n3.进栈 \n4.出栈");
 +
 
 +
    printf("\n0.退出 \n请选择你的操作:\n");
 +
 
 +
    while(opp != '0'){
 +
 
 +
        scanf("%d",&opp);
 +
 
 +
        switch(opp){
 +
 
 +
            case 1:
 +
 
 +
                srand(time(0));
 +
 
 +
                for(j=1;j<=10;j++)
 +
 
 +
                {
 +
 
 +
                    Push(&s,rand()%100+1);
 +
 
 +
                }
 +
 
 +
                StackTraverse(s);
 +
 
 +
                break;
 +
 
 +
            case 2:
 +
 
 +
                StackTraverse(s);
 +
 
 +
                break;
 +
 
 +
            case 3:
 +
 
 +
                printf("请输入需要进栈的元素:");
 +
 
 +
                scanf("%d", &value);
 +
 
 +
                Push(&s, value);
 +
 
 +
                StackTraverse(s);
 +
 
 +
                break;
 +
 
 +
            case 4:
 +
 
 +
                Pop(&s,&e);
 +
 
 +
                printf("弹出的栈顶元素 e=%d\n",e);
 +
 
 +
                StackTraverse(s);
 +
 
 +
                break;
 +
 
 +
            case 0:
 +
 
 +
                exit(0);
 +
 
 +
        }
 +
 
 +
    }
 +
 
 +
}

2016年4月14日 (四) 13:19的最新版本

栈的定义

基本概念

定义:栈是限定仅在表尾进行插入和删除操作的线性表。栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,又称为LIFO结构。把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。

注意事项:首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。

基本操作:栈的插入操作,叫作进栈,也称压栈、入栈。栈的删除操作,叫作出找,也有的叫作弹栈。

进栈出栈变化形式

n个元素进栈共有多少种出栈顺序?

我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:

                                    f(1) = 1     //即 1
                                    f(2) = 2     //即 12、21
                                    f(3) = 5     //即 123、132、213、321、231

然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。

分析:

1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);
2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2),     根据乘法原理,一共的顺序个数为f(1) * f(2);
3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),根据乘法原理,一共的顺序个数为f(2) * f(1);
4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即         f(3);结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:

f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)

然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

Ruzhan.png

栈的抽象数据类型

栈的ADT定义

ADT 栈(stack)

Data

同线性表。元素具有相同的类型,相邻元素具有前驱和后堆关系。 Operation

InitStack ( *S ):初始化操作.建立一个空栈S。

DestroyStack ( *S ):若栈存在,則销毁它。

ClearStack (*S):将栈清空。

StackEmpty ( S ):若栈为空,返回true,否則返回 false。

GetTop (S,*e):若栈存在且非空,用e返回S的栈顶元素。

Push (*S,e):若栈S存在,插入新元素e到栈S中并成为栈頂元素。

Pop (*S,*e):删除栈S中栈顶元素,并用e返回其值。

StackLength (S):返回回栈S的元素个数。

endADT

栈的顺序存储结构及实现

top指针

定义一个top变量来指示栈顶元素在数组中的位置,这top就如同中学物理学过的游标卡尺的游标,如上图所示,它可以来回移动,意味着栈顶的top可以变大变小,但无论如何游标不能超出尺的长度。同理,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。

Top2.jpg

结构体定义

  1. include "stdio.h"

/* 存储空间初始分配量 */

  1. define MAXSIZE 20

/* SElemType类型根据实际情况而定,这里假设为int */

typedef int SElemType;

/* 顺序栈结构 */

typedef struct {

   SElemType data[MAXSIZE];
   int top; /* 用于栈顶指针 */

}SqStack;

int main()

{

}

进栈操作--push

如图所示,进栈操作push大概分为两步:

1.栈顶指针 S->top 先自增1,给需要进栈的元素腾出内存空间;

2.再赋值。就是给对应的数组元素赋值:S->data[S->top]=e。 代码实现:

/* 插入元素e为新的栈顶元素 */ Status Push(SqStack *S,SElemType e) {

   if(S->top == MAXSIZE -1) /* 栈满 */
   {
       return ERROR;
   }
   S->top++;				/* 栈顶指针增加一 */
   S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
   return OK;

}

入栈.jpg

出栈操作--pop

代码实现:

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */

Status Pop(SqStack *S,SElemType *e)

{

   if(S->top==-1)
       return ERROR;
   *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
   S->top--;				/* 栈顶指针减一 */
   return OK;

} 完整可实现代码:

  1. include "stdio.h"
  1. include "stdlib.h"
  1. define OK 1
  1. define ERROR 0

/* 存储空间初始分配量 */

  1. define MAXSIZE 20

typedef int Status;

/* SElemType类型根据实际情况而定,这里假设为int */

typedef int SElemType;

/* 顺序栈结构 */

typedef struct

{

   SElemType data[MAXSIZE];
   int top; /* 用于栈顶指针 */

}SqStack;

/* 构造一个空栈S */

Status InitStack(SqStack *S) {

   /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
   S->top=-1;
   return OK;

}

/* 从栈底到栈顶依次对栈中每个元素显示 */

Status StackTraverse(SqStack S)

{

   int i;
   i=0;
   while(i<=S.top)
   {
       visit(S.data[i++]);
   }
   printf("\n");
   return OK;

}

Status visit(SElemType c)

{

   printf("%d ",c);
   return OK;

}

/* 插入元素e为新的栈顶元素 */

Status Push(SqStack *S,SElemType e)

{

   if(S->top == MAXSIZE -1) /* 栈满 */
   {
       return ERROR;
   }
   S->top++;				/* 栈顶指针增加一 */
   S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
   return OK;

}

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */

Status Pop(SqStack *S,SElemType *e)

{

   if(S->top==-1)
       return ERROR;
   *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
   S->top--;				/* 栈顶指针减一 */
   return OK;

}

int main()

{

   SqStack s;
   int opp;
   int j, value, e;
   if(InitStack(&s)==OK)
   {
       printf("顺序栈初始化成功。");
       StackTraverse(s);
   }
   printf("\n1.随机给栈赋值 \n2.栈遍历 \n3.进栈 \n4.出栈");
   printf("\n0.退出 \n请选择你的操作:\n");
   while(opp != '0'){
       scanf("%d",&opp);
       switch(opp){
           case 1:
               srand(time(0));
               for(j=1;j<=10;j++)
               {
                   Push(&s,rand()%100+1);
               }
               StackTraverse(s);
               break;
           case 2:
               StackTraverse(s);
               break;
           case 3:
               printf("请输入需要进栈的元素:");
               scanf("%d", &value);
               Push(&s, value);
               StackTraverse(s);
               break;
           case 4:
               Pop(&s,&e);
               printf("弹出的栈顶元素 e=%d\n",e);
               StackTraverse(s);
               break;
           case 0:
               exit(0);
       }
   }

}