#include<iostream>
#include<iomanip>
#include<string>
#include<cmath>
#include<time.h>
using namespace std;
#define Maxsize 100
//顺序栈的创建及其操作代码
struct SqStack
{
int* base;
int* top;
};
bool Push(SqStack& S, int e)
{
if (S.top - S.base == Maxsize)//栈满
return false;
*(S.top++) = e;//元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e;S.top++
return true;
}//插入新的栈元素，元素e只能放在栈顶，不能忘记栈顶指针+1
bool Pop(SqStack& S, int& e)
{
if (S.base == S.top)//栈空
return false;
e = *(--S.top);//栈顶指针减1，将栈顶指针赋给e
return true;
}//删除栈
int GetTop(SqStack & S)
{
if (S.top != S.base)
return *(S.top - 1);
else
return -1;
}
//栈链的操作代码详解
struct Snode
{
int data;//数据域
struct Snode* next;//指针域
}Snode,*LinkStack;
bool InitStack(LinkStack& S)
{
S = NULL;
return true;
}//栈链的初始化直接将头节点赋给NULL
bool Push(LinkStack& S, int e)
{
LinkStack p;
p = new Snode;//生成新结点
p->data = e;//将e放在新结点数据域
p->next = S;//新结点的指针域指向S
S = p;//修改栈顶指针为p
return true;
}
bool Pop(LinkStack& S, int& e)
{
LinkStack p;
if (S == NULL)//栈空
return false;
e = S->data;
p = S;
S = S->next;//修改栈顶指针指向下一个元素
delete p;
return true;
}//栈删除元素的操作函数
int GetTop(LinkStack S)
{
if (S != NULL)//栈非空
return S->data;
else
return -1;
}
//循环队列的操作代码
struct SqQueue
{
int* base;
int front, rear;
};
bool InitQueue(SqQueue& Q)
{
Q.base = new int[Maxsize];//分配空间
if (!Q.base)
return flase;
Q.front = Q.rear = 0;//头指针和尾指针为0，队列为kong
return true;
}
bool EnQueue(SqQueue& Q, int e)
{
if ((Q.rear + 1) % Maxsize == Q.front)//尾指针后移一位等于头指针表示队满
return flase;
Q.base[Q.rear] = e;//新元素插入队尾
Q.rear = (Q.rear + 1) % Maxsize;//队尾指针+1
return true;
}
int getHead(SqQueue Q)
{
if (Q.front != Q.rear)//队列非空
return Q.base[Q.front];
return -1;
}
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + Maxsize) % Maxsize;
}
//链队列操作代码
struct Qnode
{
int data;
struct Qnode* next;
}Qnode,*Qptr;
struct
{
Qnode* front;
Qnode* rear;
}LinkQueue;
void InitQueue(LinkQueue& Q)
{
Q.front = Q.rear = new Qnode;
Q.front->next = NULL;
}
void EnQueue(LinkQueue& Q, int e)
{
Optr s;
s = new Qnode;
s->data = e;
s->next = NULL;
Q.rear->next = s;//新元素插入队列
Q.rear = s;//队尾元素后移
}
bool DeQueue(LinkQueue& Q, int& e)
{
Qptr p;
if (Q.front == Q.rear)//队空
return flase;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
delete p;
return true;
}
int GetHead(LinkQueue Q)
{
if (Q.front != Q.rear)
return Q.front->next->data;
return -1;
}
//各栈或队列调用总函数及程序的主函数接口
int SqStackmain()
{
int n, x;
SqStack S;
InitStack(S);//初始化一个顺序栈S
cout << "请输入元素个数n：" << endl;
cin >> n;
cout << "请依次输入n个元素，依次入栈：" << endl;
while (n--)
{
cin >> x;
Push(S, x);
}
cout << "元素依次出栈：" << endl;
while (S.top != S, base)//如果栈不空，则依次出栈
{
cout << GetTop(5) << "\t";//输出栈顶元素
Pop(S, x);//栈顶元素出栈
}
return 0;
}
int LinkStackmain()
{
int n, x;
LinkStackS;
InitStack(S);//初始化一个顺序栈
cout << "请输入元素个数n" << endl;
cin >> n;
cout << "请依次输入n个元素，依次入栈：" << endl;
while (n--)
{
cin >> x;
Push(S, x);
}
cout << "元素依次出栈" << endl;
while (S != NULL)
{
cout << GetTop(S) << "\t";
Pop(S, x);
}
return 0;
}//链栈的总调用函数
int SqQueuemain()
{
SqQueue Q;
int n, x;
InitQueue(Q);//初始化队列，一定不能忘记初始化，否则后面存储出错
cout << "请输入元素个数n：" << endl;
cin >> n;
cout << "请依次输入n个整形数，依次入队：" << endl;
while (n--)
{
cin >> x;
EnQueue(Q, x);
}
cout << endl;
cout << "队内元素个数，即长度：" << QueueLength(Q) << endl;
cout << "队头元素：" << GetHead(Q) << endl;
cout << "元素依次出队：" << endl;
while (true)
{
if (Dequeue(Q, x))
cout << x << "\t";
else break;
}
cout << endl;
cout << "队内元素个数，即长度：" << QueueLength(Q) << endl;
return 0;
}
int LinkQueuemain()
{
LinkQueue Q;
int n, x;
InitQueue(Q);
cout << "请输入元素个数n:" << endl;
cin >> n;
cout << "请依次输入n个整形数，依次入队：" << endl;
while (n--)
{
cin >> x;
EnQueue(Q, x);//入队
}
cout << "队头元素：" << GetHead(Q)<<endl;
cout << "元素依次出队：" << endl;
while (true)
{
if (DeQueue(Q, x))
cout << x << "\t";
else
break;
}
cout << endl;
return 0;
}//链队列的总调用函数
int main()
{
int judgenumber = 0;
char judge = '\n';
cout << endl;
labelstart:
cout << "1.顺序栈" << endl;
cout << "2.链栈" << endl;
cout << "3.循环队列" << endl;
cout << "4.链队列" << endl;
cout << endl;
cout << "键入你需要的栈或队列类型数字：" << endl;
cin >> judgenumber;
if (judgenumber == 1)
{
system("cls");
SqStackmain();
}
else if (judgenumber == 2)
{
system("cls");
LinkStackman();
}
else if(judgenumber == 3)
{
system("cls");
SqQueuemain();
}
else if (judgenumber == 4)
{
system("cls");
LinkQueuemain();
}
else
{
cout<<"输入数字有误<<endl;"
}
cout << endl;
cout << "是否继续查看其它链表或者退出（Y/N）";
cin >> judge;
if (judge == 'Y')
{
system("cls");
goto labelstart;
}
else if (judge == 'N')
{
system("cls");
exit(0);
}
else
{
cout << "键入字符有误，系统默认退出" << endl;
exit(0);
}
return 1;
}
