首页 > 代码库 > 数据结构之栈

数据结构之栈

 

栈的基本概念

定义:栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。

  允许进行插入和删除的一端称为栈顶(top)

  不允许插入和删除的一端称为栈底(bottom)

  不含元素的栈称为空栈

  往栈中存入元素称为入栈

  从栈中删除元素称为出栈

特点:后进先出(LIFO)或先进后出(FILO)

 

技术分享

技术分享

技术分享

顺序栈的类型说明:

 

//顺序栈的类型说明:


#define  MAXSIZE  100  
typedef  struct
{
    int  data[MAXSIZE];
    int  top;
}SqStack;

 

双向栈:

 

//双向栈


//为了充分利用栈的空间,采用多个栈共享同一空间。
//双向栈用一个大数组表示。
//两个栈共享一个数组的数据结构定义如下:
#define MAX 100
 typedef struct
{
      int data[MAX];
      int top1,top2;
}SStack2;

 

链栈

   栈的链式存储结构称为链栈,它是运算受限的单链表,其插入和删除操作仅限制在表头位置上进行.

   由于只能在链表头部进行操作,故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。

 其类型说明为:

//链栈

typedef  struct  SNode
{
      int  data;
      struct SNode *next;

}SNode,*LinkStack;

LinkStack *top;

(1) 初始化栈 top=NULL;

(2) 判断空栈 top==NULL;

(3)取栈顶 top–>data;

(4)入栈:

void push(PSTACK S,int val)
{
    PNODE pNew=(PNODE)malloc(sizeof(NODE));
    if(pNew==NULL)
    {
        printf("分配失败程序终止");
        exit(-1); 
    }
    else
    {
        pNew->data=http://www.mamicode.com/val;
        pNew->pNext=S->pTop;
        S->pTop=pNew;
    }
}

(5)出栈:

 

bool pop(PSTACK S,int* val)
{
    if(empty(S))
    {
        return false;
    }
    else
    {
        PNODE p=S->pTop;
        *val=p->data;
        S->pTop=p->pNext;
        free(p);
        p=NULL;
        return true;
    }
}

 

技术分享

 

数据结构之栈