数据结构---顺序栈、链栈

特点

typedef struct Stack { int* base; //栈底 int* top;//栈顶 int stacksize //栈的容量; }SqStack;
typedef struct StackNode { int data;//数据域 struct StackNode* next; //指针域 }StackNode,*LinkStack;

顺序栈

#define MaxSize 100
typedef struct Stack { int* base; int* top; int stacksize; }SqStack;//***********************************   基本操作函数  *******************************************int InitStack(SqStack& s)
{s.base = new int[MaxSize];s.top = s.base;s.stacksize = MaxSize;return 1;}int Push(SqStack& s, int e)		// Push入栈，到XXX	eg: pushd...
{if(s.top-s.base==s.stacksize)	return 0;*(s.top++) = e;		return 1;
}int Pop(SqStack& s, int e) {if(s.top==s.base)	return 0;e = *--s.top;	 return 1;		// 1、减减		2、指向栈顶元素		3、再给e
}	bool GetTop(SqStack& s, int e) {if(s.top=s.base)	return false;else   e = *--s.top;	return true;
}//********************************功能实现函数**************************************//void PushToStack(SqStack& s) {int n; int e; int flag;printf("请输入入栈元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = Push(s, e);if (flag)printf("%d已入栈\n", e);else { printf("栈已满！！！\n"); break; }}
}void PopFromStack(SqStack& s) {int n; int e; int flag;printf("请输入出栈元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = Pop(s, e);if (flag)printf("%d已出栈\n", e);else { printf("栈已空！！！\n"); break; }}
}void GetTopOfStack(SqStack& s){int e; bool flag;flag = GetTop(s, e);if (flag)printf("栈顶元素为:%d\n", e);else printf("栈已空！！！\n");
}void memu() {printf("********1.入栈      2.出栈*********\n");printf("********3.取栈顶    4.退出*********\n");
}int main() {int choice = 0;;SqStack s;InitStack(s);switch (choice){case 1:PushToStack(s); break;case 2:PopFromStack(s); break;case 3:GetTopOfStack(s); break;;default:printf("输入错误！！！\n");break;}return 0;
}

链栈

typedef struct StackNode { int data; struct StackNode* next; }StackNode,*LinkStack;//***********************************   基本操作函数  *******************************************int InitStack(LinkStack &s)
{s = NULL;return 1;}int Push(LinkStack &s, int e)		
{StackNode* p;//生成新节点p = new StackNode;//赋值p->data = e;p->next = s;//压入栈顶s = p;return 1;
}bool Pop(LinkStack& s ,int& e)
{LinkStack p;if (s == NULL)return false;//栈空e = s->data;p = s;s = s->next;free(p);return true;
}bool GetTop(LinkStack &s, int &e) 
{if (s == NULL) return false;//栈顶为空e = s->data;return true;
}//********************************功能实现函数**************************************//void PushToStack(LinkStack& s) {int n; int e; int flag;printf("请输入入栈元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = Push(s, e);if (flag)printf("%d已入栈\n", e);}}void PopFromStack(LinkStack& s) {int n; int e; int flag;printf("请输入出栈元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = Pop(s, e);if (flag)printf("%d已出栈\n", e);else { printf("栈已空！！！\n"); break; }}
}void GetTopOfStack(LinkStack& s){int e; bool flag;flag = GetTop(s, e);if (flag)printf("栈顶元素为:%d\n", e);else printf("栈已空！！！\n");
}void memu() {printf("********1.入栈			2.出栈*********\n");printf("********3.取栈顶元素    4.退出*********\n");
}int main() {int choice = 0;;LinkStack s;InitStack(s);switch (choice){case 1:PushToStack(s); break;case 2:PopFromStack(s); break;case 3:GetTopOfStack(s); break;;default:printf("输入错误！！！\n");break;}return 0;
}