关于栈和队列的相关操作

1、栈分为顺序栈和链栈对应数组和链表

top指向栈顶元素，设置空栈为-1；存在一个元素时top=0

栈的长度为StackSize

定义栈的结构体：

 1 #include "stdio.h"
 2 
 3 /* 存储空间初始分配量 */
 4 #define MAXSIZE 20
 5 
 6 /* SElemType类型根据实际情况而定，这里假设为int */
 7 typedef int SElemType;
 8 
 9 /* 顺序栈结构 */
10 typedef struct
11 {
12     SElemType data[MAXSIZE];
13     int top; /* 用于栈顶指针 */
14 }SqStack;
15 
16 int main()
17 {
18 }

进栈操作：push

1 int Push(SqStack * S, SElemType e){
2     if(S->top == MAXSIZE-1){
3         //栈满
4         return 0;
5     }
6     S->top++;
7     S->data[S->top] = e;
8     return 1;
9 }

初始化一个空栈：

//初始化栈
int InitStack(SqStack S){
    S->top = -1;
    return 1;
}

栈的遍历：

 1 /* 从栈底到栈顶依次对栈中每个元素显示 */
 2 Status StackTraverse(SqStack S)
 3 {
 4     int i;
 5     i=0;
 6     while(i<=S.top)
 7     {
 8         visit(S.data[i++]);
 9     }
10     printf("
");
11     return OK;
12 }
13 
14 Status visit(SElemType c)
15 {
16     printf("%d ",c);
17     return OK;
18 }

注：S->top代表着栈对应数组的下标0，1,2 。。。

出栈：

1 int Pop(SqStack* S, SElemType* e){
2     if(-1 == S->top){
3         return 0;
4     }
5     *e = S->data[S->top];
6     S->top--;
7     return 1;
8 }

获取栈顶元素：

1 /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
2 Status GetTop(SqStack S,SElemType *e)
3 {
4     if (S.top==-1)
5         return ERROR;
6     else
7         *e=S.data[S.top];
8     return OK;
9 }

判断栈是否为空：

1
/* 若栈S为空栈，则返回TRUE，否则返回FALSE */

2
Status StackEmpty(SqStack S)

3
{

4
    if (S.top==-1)

5
        return TRUE;

6
    else

7
        return FALSE;

8
}

置空栈：

1
/* 把S置为空栈 */





2
Status ClearStack(SqStack *S)





3
{





4
    S->top=-1;





5
    return OK;




6
}

2、链栈
链栈对应不含头结点的单链表
top代表指向栈顶的指针，这里和链表中的next合并为一个，当top=null时，链栈为空
定义链栈的结构体：
下面是单链表的结构体：

typedef struct Node
{
   ElemType data;
   struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
相似的链栈的结构体为：

/* 链栈结构 */
typedef struct StackNode
{
   SElemType data;
   struct StackNode *next;
} StackNode,*LinkStackPtr;
这只是链栈一个节点的定义，还需要添加链栈的栈顶指针：

typedef int Status;
/* SElemType类型根据实际情况而定，这里假设为int */
typedef int SElemType;

/* 链栈结构 */
typedef struct StackNode
{
   SElemType data;
   struct StackNode *next;
} StackNode,*LinkStackPtr;

typedef struct
{
   LinkStackPtr top;
   int count;
} LinkStack;
其中count是用来计算栈中元素的个数的，也可以根据需要添加属性等
入栈，其实就是添加新的节点，下面这张图描述的很清楚：
实际上就两步：1、将新的节点next指向原栈顶元素  2、将top指针指向新的节点

int Push(LinkStack* L, SElemType e){
   //首先分配节点
   LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
   p->data = e;
   p->next = S->top;
   S->top = p;
   S->count++;
   return 1;
}
初始化空栈：条件count=0，且top为null

/*  构造一个空栈S */
Status InitStack(LinkStack *S)
{
   S->top = (LinkStackPtr)malloc(sizeof(StackNode));
   if(!S->top)
       return ERROR;//分配失败
   S->top=NULL;
   S->count=0;
   return OK;
}
遍历的过程和链表完全类似，这里不再赘述：

Status StackTraverse(LinkStack S)
{
   LinkStackPtr p;
   p=S.top;
   while(p)
   {
       visit(p->data);
       p=p->next;
   }
   printf("
");
   return OK;
}

Status visit(SElemType c)
{
   printf("%d ",c);
   return OK;
}
出栈操作：这里主要注意一点就是删除的节点要释放掉 核心代码就是S->top = S->top->next;

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
   LinkStackPtr p;
   if(StackEmpty(*S))
       return ERROR;
   *e=S->top->data;
   p=S->top;                    /* 将栈顶结点赋值给p，见图中① */
   S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中② */
   free(p);                    /* 释放结点p */
   S->count--;
   return OK;
}
注：这里的Status是预定义的，这里简化表示int
置空链栈会比顺序栈稍微复杂一些：置空顺序栈只需一步S->top = -1即可，而对于链栈置空实质上就是删除整个链表所有的节点，这里关键的问题就是移动待删除节点指针到下一个位置后，没法直接free掉，这样说起来不好理解，直接看代码：

/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{
   LinkStackPtr p,q;
   p=S->top;
   while(p)
   {
       q=p;
       p=p->next;
       free(q);
   }
   S->count=0;
   return OK;
}
其实就是先将待删除节点付给一个临时指针，然后当前指针移动到下一个位置后，就可以将这个临时指针给free掉
那这里来分析一下顺序栈和链栈的区别：两者的时间复杂度都为O(1)
顺序栈定位元素更加方便，需提前分配内存区域；链栈在内存充足的情况下大小是无限的，存取定位没有顺序栈快，每个节点还有指针域，某种程度上增加了空间开销
所以根据不同情况选择