数据结构之栈的实现

根据栈的存储结构可以分为次序栈和链栈
  参考：
  次序栈的解说-CSDN博客
  次序栈

   次序栈的定义

1. typedef struct//堆栈结构体定义
2. {
3.         int top;//栈顶指针
4.         int data[MaxSize];//静态数组存放栈中元素
5. }SqStack;

复制代码

次序栈的初始化
  初始化只需把栈顶指针指向-1就可以了。

1. void InitStack(SqStack &S)//初始化栈
2. {
3.         S.top = -1;//初始化栈顶指针
4. }

复制代码

次序栈的出栈
  1.判定是否为空栈，空栈无法进行出栈操作。
  2.先赋值给x再移动栈顶指针，并且是向下移动。

1. bool Printf(SqStack &S,int &x)//出栈(删除栈顶元素)
2. {
3.                 if (S.top == -1)//判断是否为空栈
4.                         return false;
5.                 x = S.data[S.top];//让x等于此时栈顶指针所指的元素
6.                 S.top = S.top - 1;//栈顶指针往下移动一位
7.         return true;
8. }

复制代码

次序栈的入栈
  1.判定是否为栈满，栈满无法进行入栈操作。
  2.栈顶指针先向上移动，再把输入的数据放进去。

1. bool Push(SqStack &S)//入栈（在栈顶位置插入元素）
2. {
3.         printf("请输入%d个数:", MaxSize);
4.         for (int i = 0; i < MaxSize; i++)
5.         {
6.                 if (S.top == MaxSize - 1)//判断栈满了没有
7.                         return false;
8.                 S.top = S.top + 1;//栈顶指针往上移动一位
9.                 scanf("%d", &S.data[S.top]);//把这次输入的元素放入此时栈顶指针指向的位置
10.         }
11.                 return true;
12. }

复制代码

  判定栈空
  只须要判定栈顶指针指向的是不是-1，由于一开始空栈的时候栈顶指针指向的是-1。

1. int testStack(SqStack &S)//判断栈空
2. {
3.         return (S.top == -1);//空栈返回1，反之返回0。
4. }

复制代码

判定栈满
  由于栈顶指针指向的是-1，所以一开始放入的位置是0，栈满的时候就会是MaxSize-1，只需判定栈顶指针指向的是不是MaxSize-1就好了。

1. int IsFull(SqStack &S)//判断栈满
2. {
3.         return (S.top == MaxSize-1);//满栈返回1，反之返回0。
4. }

复制代码

读取栈顶元素
  取栈顶元素的操作和一次出栈类似，但是不须要进行栈顶指针的移动。

1. bool GetTop(SqStack &S)//读取栈顶元素，操作和出栈类似，top不需要减1。
2. {
3.         if (S.top == -1)//判断空栈
4.                 return false;
5.         int x = S.data[S.top];
6.         printf("栈顶元素是：%d\n", x);
7.         return true;
8. }

复制代码

取有效元素个数
  栈顶指针+1就可以了。

1. int lenth(SqStack &S)//求有效元素的个数
2. {
3.         return S.top + 1;
4. }

复制代码

遍历
  遍历是进行多次的出栈操作，并把每次出栈的数据打印出来。给出栈操作加上循环和输出即可。
  暂略。
    其实次序栈就是个操作受限的次序表。 
  链栈

   参考：链栈及其基本操作-CSDN博客
    链栈定义

1. typedef int elemtype;  //数据域数据类型
3. typedef struct LinkedStackNode
4. {
5.         elemtype data;
6.         LinkedStackNode *next;
7. }LinkedStackNode,*LinkedStack;

复制代码

初始化

1. LinkedStack Init_LinkedStack()
2. {
3.         LinkedStack top = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));  
4.                                       //栈顶指针变量
5.         if(top != NULL)
6.         {
7.                 top->next = NULL;
8.         }
9.         return top;
10. }

复制代码

判定是否为空

1. int LinkedStack_Empty(LinkedStack top)
2. {
3.         if(top->next == NULL)//如果栈顶的指针域指向空，则栈空
4.         {
5.                 return 1;
6.         }
7.         else
8.         {
9.                 return 0;
10.         }
11. }

复制代码

入栈

1. int Push_LinkedStack(LinkedStack top,elemtype x)
2. {
3.         LinkedStackNode * node = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));
5.         if(node == NULL)
6.         {
7.                 return 0;
8.         }
9.         else
10.         {
11.                 node->data = x;
12.                 node->next = top->next;
13.                 top->next = node;
14.                 return 1;
15.         }
16. }

复制代码

出栈

1. int Pop_LinkedStack(LinkedStack top,elemtype *x)
2. {
3.         LinkedStackNode *node;
4.         if(top->next == NULL)
5.         {
6.                 return 0;
7.         }
8.         else
9.         {
10.                 node = top->next;
11.                 *x = node->data;
12.                 top->next = node->next;
13.                 free(node);
14.                 return 1;
15.         }
16. }

复制代码

读取栈顶元素

1. int Get_LinkedStack(LinkedStack top,elemtype *x)
2. {
3.         if(top->next == NULL)
4.         {
5.                 return 0;
6.         }
7.         else
8.         {
9.                 *x = top->next->data;
10.                 return 1;
11.         }
12. }

复制代码

其实链栈就是个操作受限的单链表

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。