栈的创建及其操作

一·顺序栈：

1.本质是数组，特殊数组。
2.结构包含：数组指针，栈顶下标。
实现：

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef int Status;
#define MAXSIZE 50
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//栈的定义：
typedef struct
{
 ElemType elem[MAXSIZE];
 int top;
}SqStack;
//初始化:
void InitStack(SqStack &S)
{
 S.top = 0;
}
//判断栈空：
Status StackEmpty(SqStack S)
{
 if(S.top == 0)
  return OK;
 else 
  return ERROR;
}
//入栈：
Status Push(SqStack &S,ElemType e)
{
 if(S.top == MAXSIZE-1)
  return OVERFLOW;   //栈满
 else
 {
  S.top++;
  S.elem[S.top] = e;
  return OK;
 }
}
//出栈：
Status Pop(SqStack &S,ElemType &e)
{
 if(StackEmpty(S))
  return ERROR;
 else
 {
  e = S.elem[S.top];
  S.top--;
  return OK;
 }
}
//读栈顶：
Status GetTop(SqStack &S,ElemType &e)
{
 if(StackEmpty(S))
  return ERROR;
 e = S.elem[S.top];
 return OK;
}
void print(SqStack S)
{
 ElemType e;
 while(!StackEmpty(S))
 {
  Pop(S,e);
  cout<<e<<' ';
 }
}

二·链式栈：

1.是一种只能从顶进，从顶出的链表。
2.结构包含：

1. 节点结构：节点数据，next指针。
2. 栈结构：节点栈顶指针，节点栈底指针，栈容量。

实现：

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef int Status;
#define MAXSIZE 50
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef struct Node
{
 ElemType data;
 struct Node * next;
}SNode,*SNodeP;
typedef struct LinkS
{
 SNodeP top;
 SNodeP base;
 int stacksize;//栈容量
}LinkS;
//初始化：
Status InitStack(LinkS &S)
{
 S.base = new SNode;
 if(!S.base)
  exit(OVERFLOW);
 S.top = S.base;
 S.stacksize = 0;
 return OK;
}
//判断是否为空栈：
Status StackEmpty(LinkS S)
{
 if(S.top == S.base)
  return OK;
 else
  return ERROR;
}
//入栈：顶在动
Status Push(LinkS &S,ElemType e)
{
 SNodeP p = new SNode;
 p->data = e;
 p->next = S.top;
 S.top = p;
 S.stacksize++;
 return OK;
}
//出栈：顶在动
Status Pop(LinkS &S,ElemType &e)
{
 SNodeP p;
 if(StackEmpty(S))
  return ERROR;
 e = S.top->data;
 p = S.top;
 S.top = S.top->next;
 delete(p);
 p == NULL;
 S.stacksize--;
 return OK;
}