数据结构学习笔记：顺序栈与链栈

顺序栈

typedef struct    
{    
    int data[maxSize];   //存放栈中元素  
    int top;    //栈顶指针  
} SqStack;   //顺序栈类型定义

1 顺序栈要素：两个特殊状态与两个操作对于顺序栈st

（1）两个状态：

1）栈空：

st.stop == -1

2）栈满：

st.top == maxSize - 1

(2)两个操作

1）元素x进栈操作

++(st.top);
st.data[st.top] = x ;
//  也可写成一行  即  st.data[++(st.top)] = x;

2）元素x出栈操作

x = st.data[st.top] ;
-- (st.top);
//   或者   x = st.data[(st.top） -- ] ;

2 顺序栈基本操作

注意：当前栈是否为空，空时不出；是否为满，满时不进。

//初始化栈
void initStack(SqStack &st)
{
st.top = -1;
}

//判断栈空
int isEmpty(SqStack st)
{
if ( -1 == st.top )
{
return 1;
}
else
{
return 0;
}
}

//进栈
int Push(SqStack &st, int x)
{
if ( (maxSize - 1 ) == st.top )
{
return 0;
}
//先移动指针，再进栈
++ (st.top);              //<span style="color:#ff0000;"> ++a 总比 a++ 执行效率要高。在两者等效的情况下，总是使用 ++a</span>
st.data[ st.top] = x;  // st.data[ ++ (st.top)] = x;
return 1;  //
}

//出栈
int Pop(SqStack &st, int &x)
{
if ( -1 == st.top)
{
return 0;
}
//先出栈，再移动指针
x =  st.data[ st.top]; // x =  st.data[ st.top -- ];
(st.top) --;//
return 1;
}

链栈：

typedef struct LNode    
{    
    int data;    
    struct LNode *next;  //指向后继结点的指针    
}LNode;  //链栈结点定义

1 链栈要素：两个状态，两个操作对于链栈 lst

（1）两个状态

1）栈空：

lst->next = NULL

2）栈满

不存在栈满的状态。链栈可以利用的结点数与内存大小有关，当内存满时，为栈满

（2）两个操作

1）元素（由指针p所指）进栈操作

p->next = lst->next;
lst->next = p;      //头插入法建立链表的插入操作

2）出栈操作（出栈元素保存在x中）

p = lst->next;
x = p->data;
lst->next = p->next;
free(p);   // 单链表的删除操作

2 链栈基本操作

//初始化链栈
void initStack(LNode *&lst)
{
lst = (LNode*) malloc (sizeof(LNode));
lst->next = NULL;
}

//判断栈空
int isEmpty(LNode *lst)
{
if (NULL == lst->next)
{
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 (NULL == lst->next)
   {
   return 0;
   }

   p = lst->next;
   x = p->data;
   lst->next = p->next;
   free(p);
   return 1;
}

秒客网

数据结构学习笔记：顺序栈与链栈

相关文章