文章共分为4个部分每一部分都包括了定义和相关操作
- 第一部分 顺序栈
- 第二部分 链栈
- 第三部分 顺序队
- 第四部分 链队
第一部分 顺序栈
//顺序栈定义
typedef struct SqStack
{
int data[maxSize];
int top;
}SqStack;
//初始化栈
void initStack(SqStack &st)
{
st.top = -1; //不设置为0 是因为在数组中data[0]也可以存放一个元素
}
//判断栈空代码
int isEmpty (SqStack st)
{
if (st.top == -1)
return 1;
else
return 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;
}
第二部分 链栈
//链栈定义 相当于操作受限的链表
typedef struct LNode
{
int data;
struct LNode * next;
} LNode;
//链栈初始化
void initStact(LNode * & lst)
{
lst = (LNode *)malloc(sizeof(LNode));
lst->next = NULL;
}
//判断栈空
int isEmpty(LNode * lst)
{
if (lst->next == NULL)
return 1;
else
return 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;
lst->next = p->next;
free(p);
return 1;
}
第三部分 顺序队
（顺序队中有些劣势在循环队列中可以避免，此处写的是循环队列，循环队列只是一种逻辑结构，与存储结构无关，此处的储存结构是循环结构）
//顺序队定义
typedef struct SqQueue
{
int data[maxSize];
int front;
int rear;
}SqQueue;
//初始化队
void initQueue (SqQueue & qu)
{
qu.front = qu.rear = 0;
}
//判断队空
int isQueueEmpty(SqQueue qu)
{
if (qu.front == qu.rear)
return 1;
else
return 0;
}
//进队
int enQueue(SqQueue & qu, int x)
{
if (qu.front == (qu.rear+1)%maxSize) //队满的条件
return 0;
qu.rear = (qu.rear + 1) % maxSize;
qu.data[qu.rear] = x;
return 1;
}
//出队算法
int deQueue (SqQueue & qu, int & x)
{
if (qu.rear == qu.front)
return 0;
x = qu.data[qu.front];
qu.front = (qu.front + 1) % maxSize;
return 1;
}
//出现问题尽量用顺序对来解决问题，尽可能避免链队，毕竟顺序队的定义操作更简单一些
第四部分 链队
//链队节点定义
typedef struct QNode
{
int data;
struct QNode * next;
}QNode;
//链队类型定义
typedef struct
{
QNode * front;
QNode * rear;
} LiQueue;
//初始化链队
void initQueue(LiQueue * & lqu)
//指针型变量在函数体中需要改变的写法，C++中的写法与C中的写法不同注意一下
{
lqu = (LiQueue *)malloc(sizeof(QNode));
lqu->front = lqu->rear = NULL;
}
//判断对空算法
int isQueueEmpty(LiQueue * lqu)
{
if(lqu->rear == NULL || lqu->front == NULL)
return 1;
else
return 1;
}
//入队
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;
else
p = lqu->front;
if (lqu->front == lqu->rear) //栈队中只有一个元素时需要特殊处理一下
lqu->front = lqu->rear = NULL;
else
lqu->front=lqu->front->next;
x = p->data;
free(p);
return 1;
}
