//数据结构栈和队列算法总结以及测试#define MaxSize 100//初始化顺序栈：InitStack(SqStack &st)
//顺序栈判断栈空：IsEmpty(SqStack st)
//顺序栈进栈：push(SqStack &st,int x)
//顺序栈出栈：pop(SqStack &st,int &x)
//链栈初始化：InitStack(LNode *&lst)
//链栈栈空：IsEmpty(LNode *lst)
//链栈进栈：push(LNode *lst,int x)
//链栈出栈：pop(LNode *lst,int &x)
//不带头结点的链栈操作：
//InitStackl(LNode *&lst)
//IsEmptyl(LNode *lst)
//pushl(LNode *&lst,int x)
//popl(LNode *&lst,int x)
//顺序队初始化：InitQueue(SqQueue &qu)
//顺序队队空：IsQueueEmpty(SqQueue qu)
//顺序队进队：EnQueue(SqQueue &qu,int x)
//顺序队出队：DeQueue(SqQueue &qu,int &x)
//链队初始化：InitQueue(LiQueue *&lqu)
//链队队空：IsQueueEmpty(LiQueue *lqu)
//链队入队：EnQueue(LiQueue *lqu,int x)
//链队出队：DeQueue(LiQueue *lqu,int &x)typedef struct
{int data[MaxSize];int top;
}SqStack;typedef struct LNode
{int data;struct LNode *next;
}LNode;typedef struct
{int data[MaxSize];int front;int rear;
}SqQueue;typedef struct QNode
{int data;struct QNode *next;
}QNode;typedef struct
{QNode *front;QNode *rear;
}LiQueue;void InitStack(SqStack &st)
{st.top = -1;
}int IsEmpty(SqStack st)
{if(st.top == -1)return 1;elsereturn 0;
}int push(SqStack &st,int x)
{if(st.top == MaxSize-1)return 0;++(st.top); //先移动指针在入栈st.data[st.top] = x;return 1;
}int pop(SqStack &st,int &x)
{if(st.top == -1)return 0;x = st.data[st.top];--(st.top); //先取元素再移动指针return 1;
}void InitStack(LNode *&lst)
{lst = (LNode*)malloc(sizeof(LNode));lst->next = NULL;
}int IsEmpty(LNode *lst)
{if(lst->next == NULL)return 1;elsereturn 0;
}void push(LNode *lst,int x)
{LNode *p;p = (LNode*)malloc(sizeof(LNode));p->next = NULL; //可以不写，但这是避免错误的好习惯p->data = x;p->next = lst->next;lst->next = p;
}int pop(LNode *lst,int &x)
{LNode *p;if(lst->next == NULL)return 0;p = lst->next;x = p->data;lst->next = p->next;free(p);return 1;
}void InitStackl(LNode *&lst)
{lst = NULL;
}int IsEmptyl(LNode *lst)
{if(lst == NULL)return 1;elsereturn 0;
}void pushl(LNode *&lst,int x)
{LNode *p;p = (LNode*)malloc(sizeof(LNode));p->next = NULL;p->data = x;p->next = lst;lst = p;
}int popl(LNode *&lst,int x)
{LNode *p;if(lst == NULL)return 0;p = lst;x = p->data;lst = p->next;free(p);return 1;
}void InitQueue(SqQueue &qu)
{qu.front = qu.rear = 0;
}int IsQueueEmpty(SqQueue qu)
{if(qu.front == qu.rear)return 1;elsereturn 0;
}int EnQueue(SqQueue &qu,int x)
{if((qu.rear+1)%MaxSize == qu.front)return 0;qu.rear = (qu.rear+1)%MaxSize; //先移动指针qu.data[qu.rear] = x; //再存入元素return 1;
}int DeQueue(SqQueue &qu,int &x)
{if(qu.front == qu.rear)return 0;qu.front = (qu.front+1)%MaxSize;x = qu.data[qu.front];return 1;
}void InitQueue(LiQueue *&lqu)
{lqu = (LiQueue*)malloc(sizeof(LiQueue));lqu->front = lqu->rear = NULL;
}int IsQueueEmpty(LiQueue *lqu)
{if(lqu->rear == NULL || lqu->front == NULL)return 1;elsereturn 0;
}void EnQueue(LiQueue *lqu,int x)
{QNode *p;p = (QNode*)malloc(sizeof(QNode));p->data = x;p->next = NULL;if(lqu->rear == NULL){lqu->front = lqu->rear = p;}else{lqu->rear->next = p;lqu->rear = p;}
}int DeQueue(LiQueue *lqu,int &x)
{QNode *p;if(lqu->rear == NULL)return 0;elsep = lqu->front;if(lqu->front == lqu->rear) //队列中只有一个节点时的特殊处理lqu->front = lqu->rear = NULL;elselqu->front = lqu->front->next;x = p->data;free(p);return 1;
}
以下是测试代码：
#include<iostream>
#include<StackAndQueue.h>using std::cout;
using std::cin;
using std::endl;int main()
{LNode *zhan;InitStack(zhan);int tempin,tempout;cout << "Please input 10 number to push them in stack." << endl;for(int i(0);i<10;i++){cout << "This is the " << i+1 << endl;cin >> tempin;push(zhan,tempin);}cout << "The result of going out of the stack in turn!" << endl;for(int i(0);i<10;i++){pop(zhan,tempout);cout << " " << tempout ;}cout << endl <<"This is the end of the program!" << endl;
}
声明：以上内容仅用来交流学习