数据结构学习之栈、队

文章共分为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;
        
}