一、线性表、栈、队列辨析

• 栈和队列是两种数据结构，从逻辑上看，他们是操作受限制的线性表，从存储上看，可以是顺序的也可以是链式的。而栈和队列又可以看成两种数据类型，从抽象数据类型角度看，它们的基本操作与线性表很不相同。
• 栈是限定仅在表尾(栈顶)进行插入或删除元素的线性表，表头又叫做栈底。实现栈关键在于编写合理的入栈和出栈函数。

二、顺序栈与链栈

1.顺序栈

#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define MAXSIZE 100

typedef int Status;
typedef int ElemType;

/*-----顺序栈结构定义-----*/
typedef struct {
	ElemType *top;	//栈顶 
	ElemType *base;	//栈底
	int size; 
}Stack;

/*-----初始化-----*/
void Init(Stack &s) {
	cout << "初始化栈" << endl; 
	s.base = new ElemType[MAXSIZE];
	s.top = s.base;
	s.size = MAXSIZE;	//栈的大小描述的是栈的最大容纳能力 
						//而非当前栈的长度 
						//似乎这样更有意义
	cout << "s.base:"<<s.base <<" s.top:"<< s.top << " s.size:"<<s.size<<endl;;
} 


/*-----压入栈-----*/
Status Push(Stack &s, ElemType e) {
	if(s.top - s.base  ==  s.size)	return ERROR;
	*s.top++ = e; // <==> *s.top=e; s.top++;
	return OK;
} 

/*-----弹出栈-----*/
Status Pop(Stack &s, ElemType &e) {
	if(s.top == s.base) return ERROR;	//栈空
	e = *--s.top; // <==> *s.top--; e=*s.top;
	return OK; 
} 

/*-----读栈顶-----*/
ElemType GetTop(Stack &s, ElemType &e) {
	if(s.top == s.base) return ERROR;	//栈空
	e = *(s.top - 1);
	return OK; 
}

/*-----建栈-----*/
Status CreateStack(Stack &s, int n) {
	s.base = new ElemType[MAXSIZE];
	s.top = s.base;
	s.size = MAXSIZE;
	ElemType e;
	while(n--)
	{
		cin >> e;
		if(s.top - s.base  ==  s.size)	return ERROR;
		*s.top++ = e;
	}
} 

/*-----打印栈-----*/
void Print(Stack s) {
	int l = s.top - s.base;
	for(int i =0; i<l; ++i)
		cout << s.base[i] << " ";	
}

int main()
{
	Stack s; 
	int n;
	cout << "请输入顺序栈长度：";
	cin >> n; 
	cout << "创建" << n << "个结点的顺序栈.." 
		<< "\n请依次输入每个元素的值: " << endl; 
	CreateStack(s, n);
	Print(s);
}

2.链栈

#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef int ElemType;

/*-----链栈结点结构-----*/ 
typedef struct Node{
	ElemType data;
	struct Node *next;
}Node, *Stack;

/*-----压入栈-----*/
Status Push(Stack &s, ElemType e) {
	Stack p = new Node; 	//生成新结点
	if (!p) exit(OVERFLOW);	//结点生成失败 
	p->data = e; 			 
	p->next = s;			// 结点*p追加栈顶 
	s = p;					//更新栈顶指针 
	return OK; 
} 

/*-----弹出栈-----*/
Status Pop(Stack &s, ElemType &e) {
	if (s) return ERROR;	//栈空
	e = s->data;	// 取出栈顶结点的值 
	Node *p = s;
	s = s->next; 	// 栈顶指针后移  
	delete p;		// 释放原栈顶结点 
	return OK;
} 
/*-----取栈顶元素-----*/
Status GetTop(Stack &s, ElemType &e) {
	if (s) return ERROR;	//栈空 栈顶无元素
	e = s->data; 
	return OK; 
} 

/*-----建立链栈-----*/ 
Status createStack(Stack &s, int n) {
	s = NULL;
	ElemType e;
	while (n--)	{	
		cin >> e;
		Stack p = new Node; 	//生成新结点
		if (!p) exit(OVERFLOW);	//结点生成失败 
		p->data = e; 			 
		p->next = s;			// 结点*p追加栈顶 
		s = p;					//更新栈顶指针 
	}
	return OK;  
}

/*-----打印链栈-----*/ 
void Print(Stack s) {
	Node *p = s;
	cout << "链栈："<< "栈顶："<<p->data<< endl ; 
	while (p) {
		cout << p->data << " ";
		p = p->next;
	}	
}

int main()
{
	Stack s; 
	int n;
	cout << "请输入链栈结点个数：";
	cin >> n; 
	cout << "创建" << n << "个结点的链栈.." 
		<< "\n请依次输入每个结点的值: " << endl; 
	createStack(s, n);
	Print(s);
	return 0;
}

三、队列

1.顺序循环队列

#include <iostream>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define M 100

//在顺序队列可能会出现假溢出因此常常设计成循环队列 
typedef struct {
	ElemType *base; //初始化的动态内存分配空间
	int front; 		//头指针
	int rear;		//尾指针 
}Queue;


/*-----循环队列入队-----*/
Status EnQueue(Queue &Q, ElemType e) {
	if ((Q.rear+1) % M == Q.front) return ERROR; //队满
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1) % M;
	return OK; 
}

/*-----循环队列出队-----*/
Status DeQueue(Queue &Q, ElemType &e) {
	if (Q.rear == Q.front) return ERROR; //队空 
	e = Q.base[Q.front];
	Q.front = (Q.front+1) % M;
	return OK; 
}

int main()
{
	Queue Q;
	ElemType e=1;
	Q.base = new ElemType[M];
	if (!Q.base) exit(OVERFLOW);
	Q.front = Q.rear = 0; //空队标志
	 
	
	for (int i=0; i<5; ++i) {
		cin >> e;
		EnQueue(Q, e);
	}
	
	for (int i=0; i<5; ++i) {
		DeQueue(Q, e);
		cout << e << " " ;
	}
	return 0;
}

2.链队列

#include <iostream>
using namespace std;
typedef int ElemType;

/*-----链队列 结点结构-----*/ 
typedef struct QNode{
	ElemType data;
	struct QNode *next; 
}QNode, *QueuePtr; 


typedef struct {
	QueuePtr front; 	//队头指针
	QueuePtr rear; 		//队尾指针 
}Queue;

void Init(Queue &Q) {
	Q.front = Q.rear = new QNode;
	if(!Q.front) exit(-2);
	Q.front->next = NULL;1
}

void EnQueue(Queue &Q, ElemType e) {
	QueuePtr p = new QNode; //新建结点 
	if(!p) exit(-2);		//内存分配失败 退出 
	p->data = e;	 		//新结点置入数据 
	p->next = NULL;			//新结点标记为表尾 
	Q.rear->next = p; 		//新结点挂在队尾 
	Q.rear = Q.rear->next;	//更新队尾指针 
	
}

void DeQueue(Queue &Q, ElemType &e) {
	if (Q.front == Q.rear) return;
	QueuePtr p = Q.front->next;		//首元结点 
	e = p->data;					//保存结点值  
	Q.front->next = p->next;		//更新队头 
	if(Q.rear == p)
		Q.rear = Q.front;			//标记空队 
	delete p;						//释放原首元结点 
} 
int main()
{
	Queue Q;
	Init(Q);
	ElemType e; 
	for (int i=0; i<3; ++i)	{
		cin >> e;
		EnQueue(Q, e);
	}
	for (int i=0; i<3; ++i)	{
		DeQueue(Q, e);
		cout << e << " "; 
	}
	return 0;
}