我打开了封印多年的数据结构C语言笔记——栈与队列

栈的定义

栈作为一种限定性线性表,将线性表的插入和删除运算限制为仅在表的一端进行,即LIFO表。

• 通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，表的另一端被称为栈底(Bottom)。
• 当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
关系：栈中数据元素之间是线性关系
基本操作：
Push
Pop
StackTop
InitStack
ClearStack
IsEmpty
IsFull
GetTop
…

顺序栈

顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

由于栈的操作的特殊性，还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。

用C语言定义栈的顺序存储结构

#define TRUE 1 
#define FALSE 0 
#define Stack_Size 100 
 typedef struct 
{
StackElementType  elem[Stack_Size]; 
/*用来存放栈中元素的一维数组*/ 
int  top; /*用来存放栈顶元素的下标*/ 
}SeqStack;

Push adds an item at the top of the stack.

Pop removes the item at the top of the stack.

顺序栈基本操作的实现

void  InitStack(SeqStack *S) 
{
  /*构造一个空栈S*/ 
  S->top= -1; 
}

int IsEmpty(SeqStack *S)     
/*判栈S为空栈时返回值为真，反之为假*/ 
{ 
return(S->top==-1?TRUE:FALSE); 
}

int IsFull(SeqStack *S) 
/*判栈S为满时返回真,否则返回假*/ 
{ 
return(S->top== Stack_Size-1 ? TRUE:FALSE); 
}

int Push(SeqStack *S, StackElementType x) 
{ 
if(S->top== Stack_Size-1) 
     return(FALSE);  /*栈已满*/ 
S->top++; 
S->elem[S->top]=x; 
return(TRUE); 
}

int Pop(SeqStack *S, StackElementType *x) 
{
    if(S->top==-1)  return(FALSE); 
    else 
    {
        *x= S->elem[S->top]; 
        S->top--;/*修改栈顶指针*/ 
        return(TRUE);
    } 
}

int GetTop（SeqStack *S, StackElementType *x） 
{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/ 
 if(S->top==-1)  /*栈为空*/ 
       return(FALSE); 
 else 
  {
       *x = S->elem[S->top]; 
        return(TRUE); 
  }
}

链栈

链栈是采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。

typedef struct node 
{ 
StackElementType  data; 
struct node *next; 
}LinkStackNode; 
typedef  LinkStackNode  *LinkStack;

链栈基本操作的实现

int Push(LinkStack top, StackElementType x) 
/*将数据元素x压入栈top中*/  
{
    LinkStackNode * temp; 
    temp=(LinkStackNode * )malloc(sizeof(LinkStackNode)); 
    if(temp==NULL)  return(FALSE);   /*申请空间失败*/ 
    temp->data=x; 
    temp->next=top->next; 
    top->next=temp; /*修改当前栈顶指针 */ 
    return(TRUE);
}

int Pop(LinkStack top, StackElementType *x) 
{/*将栈top的栈顶元素弹出，放到x所指的存储空间中 */ 
 LinkStackNode *temp; 
 temp=top->next; 
 if(temp==NULL) return(FALSE); 
 top->next=temp->next; 
 *x=temp->data; 
 free(temp);/*释放存储空间*/ 
 return(TRUE);
}