数据结构——栈和队列

摘要：栈和队列的基本概念、顺序栈/队列、链栈/队列的构成方法。

基本概念

栈的基本概念

定义

栈是一种只能在一端进行插入和删除操作的线性表。其中允许进行插入或者删除操作的一端称为栈顶（top）。栈顶由一个称为栈顶指针的位置指示器（其中就是一个变量，对于顺序栈，就是进行记录栈顶元素所在数组位置标号的一个整型变量。对于链式栈，就是记录栈顶元素所在的结点地址的指针）来指示的，它是动态变化的。表的另一端称为栈底，栈底固定不变。栈的插入和删除操作一般称为入栈和出栈。
栈的特点

由栈的定义，栈的特点是FILO。栈中的元素就好比开进死胡同的车队。
栈的存储结构

可以用顺序表和链表来存储栈，栈可以依照存储结构分为两种：顺序栈和链式栈。在栈的定义中已经说明，栈是一种在操作上稍加限制的线性表，即栈本质上是一个线性表，而线性表由两种主要的存储结构——顺序表和链表，因此栈也同样有对应的两种存储结构。
栈的数学性质

当n个元素以某种顺序进栈，并且可以在任意时刻出栈时，所获得的元素排列的数目N恰好满足Catalan（）的计算：

N = 1/（n+1）* C （上标n下标2n）组合

队列的基本概念

队列的定义

队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一段进行插入，在表的另一端进行删除。可进行插入的一端称为队尾（rear），可进行删除的一端策划归称为队头（front）。向队列中插入新的元素称为进队，新元素进队后就称为了新的队尾元素，从队列中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。
队列的特点

队列的特点概况起来就是FIFO。
队列的存储结构

可用顺序表和链表来存储队列，队列按存储结构可分为顺序队和链队两种。

栈和队列的存储结构、算法和应用

顺序栈

顺序栈的要素

对于顺序栈st，一共有四个要素，包括两个特殊状态和两个操作。

1）栈空状态

st.top== -1，这里暂时这么定义，这样不会浪费一个元素大小的空间。

2）栈满状态

st.top == max_size -1。max_size为栈中最大元素个数，则max_size-1为栈满时栈顶元素在数组中的位置，因为数组下标从0开始，所以定义top为-1时栈空，即top==0的数组位置也可以存放数据元素。

3）非法状态（上溢和下溢）

栈满的时候继续入栈就会上溢，栈空的时候出栈就会下溢。

4）元素x进栈的操作： ++（st.top); st.data[st.top] =x; 。既然规定了top为-1时栈空，则元素进栈操作必须是先移动指针，再进入元素，因为不存在下标为-1的数组。

5）元素x出栈的操作： x = st.data[st.top]; - - (st.top); 。进栈操作次序决定了出栈操作次序，由于进栈操作是先变动栈顶指针，再存入元素，因此出栈的操作必须为先取出元素再变动指针。如果上述进栈操作不变的情况下先动指针，再取出元素，则栈顶元素则会丢失，取出的是栈顶下边的元素。

顺序栈定义：

typedef struct
{
    int data[max_size];
    int top;
}sq_stack;

初始化：

//初始化栈
void initStack(sq_stack *st)
{
    st->top=-1;
}

判定栈是否为空：

//判断栈是否为空
void isEmpty(sq_stack *st)
{
    if(st->top == -1)
        printf("栈为空栈！\n");
    else
        printf("栈不为空！\n");
}

进栈以及出栈操作：

//进栈操作
int push(sq_stack *st,int x)
{
    if(st->top == max_size-1)
    {
        printf("栈已经满了！\n");
        return 0;
    }
    ++(st->top);
    st->data[st->top]=x;
    return 1;
}
//出栈操作
int pop(sq_stack *st, int *x)
{
    if(st->top == -1)
    {
        printf("栈已经空了！\n");
        return 0;
    }
    *x = st->data[st->top];
    --(st->top);
    return 1;
}

全部代码：

#include <stdio.h>
#include <stdlib.h>
#define max_size 128
//顺序栈的定义
typedef struct
{
    int data[max_size];
    int top;
}sq_stack;

//以下为顺序栈的操作

//初始化栈
void initStack(sq_stack *st)
{
    st->top=-1;
}
//判断栈是否为空
void isEmpty(sq_stack *st)
{
    if(st->top == -1)
        printf("栈为空栈！\n");
    else
        printf("栈不为空！\n");
}
//进栈操作
int push(sq_stack *st,int x)
{
    if(st->top == max_size-1)
    {
        printf("栈已经满了！\n");
        return 0;
    }
    ++(st->top);
    st->data[st->top]=x;
    return 1;
}
//出栈操作
int pop(sq_stack *st, int *x)
{
    if(st->top == -1)
    {
        printf("栈已经空了！\n");
        return 0;
    }
    *x = st->data[st->top];
    --(st->top);
    return 1;
}
int main()
{
    sq_stack *st;
    int x = 1;
    int y = 0;
    st = (sq_stack*)malloc(sizeof(sq_stack));
    initStack(st);
    printf("初始化后栈顶指针为：%d\n",st->top);
    isEmpty(st);
    push(st,x);
    isEmpty(st);
    pop(st,&y);
    printf("y的值为：%d\n",y);
    return 0;
}

简化操作

其中值得说的是，顺序栈其实可以很简单的定义以及进出栈：

定义一个栈并初始化

int stack[max_size];

int top = -1;

元素进栈

stack[++top] = x;

元素出栈

stack[top--] = x;

其中元素进出栈要根据具体情况按需判断栈的空或满；

tips:

在自增操作中 a;总是比a;来得执行效率更加高效，因此独立的自增操作总是用++a;。自减也是同样的道理。

链栈

链栈的要素

和顺序栈对应，链栈也有4个要素，包括两个特殊状态和两个操作。

（1）两个状态

栈空状态：

lst->next == NULL;

栈满状态：

不存在栈满状态（假设内存无限大）

（2）两个操作

元素（由指针p所指）进栈操作

p->next = lst->next;

lst->next = p;

其实就是头插法建立链表的插入操作。

出栈操作（出栈元素保存在x中）

p = lst->next;

x = p->data;

lst->next = p->next;

free(p);

其实就是单链表的删除操作。

基本操作

链栈结点定义：

//链栈结点的定义
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;

初始化链栈：

//初始化链栈
LNode *initStack(LNode *lst)
{
    lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
    lst->next = NULL;
    return lst;
}

判断栈空：

//判断栈空
void isEmpty(LNode *lst)
{
    if(lst->next == NULL)
        printf("栈为空栈！\n");
    else
        printf("栈不为空！\n");
}

进出栈：

//进栈
void push(LNode *lst,int x)
{
    LNode *p = (LNode*)malloc(sizeof(LNode));
    p->next = NULL;

    p->data = x;
    p->next = lst->next;
    lst->next = p;
}
//出栈
void pop(LNode * lst,int *x)
{
    LNode *p;
    if(lst->next == NULL)
        printf("栈为空栈！\n");
    else
    {
        p = lst->next;
        *x = p->data;
        lst->next = p->next;
        free(p);
    }
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
//链栈结点的定义
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
//初始化链栈
LNode *initStack(LNode *lst)
{
    lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
    lst->next = NULL;
    return lst;
}
//判断栈空
void isEmpty(LNode *lst)
{
    if(lst->next == NULL)
        printf("栈为空栈！\n");
    else
        printf("栈不为空！\n");
}
//进栈
void push(LNode *lst,int x)
{
    LNode *p = (LNode*)malloc(sizeof(LNode));
    p->next = NULL;

    p->data = x;
    p->next = lst->next;
    lst->next = p;
}
//出栈
void pop(LNode * lst,int *x)
{
    LNode *p;
    if(lst->next == NULL)
        printf("栈为空栈！\n");
    else
    {
        p = lst->next;
        *x = p->data;
        lst->next = p->next;
        free(p);
    }
}

int main()
{
    LNode *lst;
    int x = 1;
    int y = 0;
    lst = initStack(lst);
    isEmpty(lst);
    push(lst,x);
    isEmpty(lst);
    pop(lst,&y);
    printf("y的值为：%d\n",y);
    isEmpty(lst);
    return 0;
}

顺序队

循环队列

front代表头指针； rear代表尾指针；

要实现指针在递增的过程中沿着环形道路行走，就拿front举例子，可以循环执行语句front= （front+1)%max_size (max_size指的是数组长度)。
两个状态

队空状态

qu.rear == qu.front

队满状态

(qu.rear+1)%max_size == qu.front
两个操作

元素x进队操作（移动队尾指针）

qu.rear = (qu.rear + 1)%max_size;

qu.data[qu.rear] = x;

元素x出队操作（移动队首指针）

qu.front = (qu.front + 1)%max_size;

x = qu.data[qu.front];

tips:

元素入队先移动指针，后存入元素，对应元素出队时，先移动指针，再取出元素。可能有的方式不同，但是归根究底本质是一样的。

顺序队的定义

typedef struct 
{
    int data[max_size];
    int front;
    int rear;
}sq_queue;

初始化队列以及判断队列是否为空

void init_sq_queue(sq_queue *qu)
{
    qu->front = qu->rear = 0;
}
//判断队空
int isEmpty(sq_queue *qu)
{
    if(qu->front == qu->rear)
        return 1;
    else
        return 0;
}

进队以及出队

int in_queue(sq_queue *qu,int x)
{
    if((qu->rear+1)%max_size == qu->front)//判断队列是否为满
    {
        printf("队列已满！\n");
        return 0;
    }
    qu->rear = (qu->rear + 1)%max_size;
    qu->data[qu.rear] = x;
    return 1;
}
//出队
int out_queue(sq_queue *qu,int *x)
{
    if(qu->rear == qu->front)//判断队列是否为空
    {
        printf("队列为空！\n");
        return 0;
    }
    qu->front = (qu->front + 1)%max_size;
    *x = qu->data[qu.front];
    return 1;
}

全部代码

#include <stdio.h>
#include <stdlib.h>
#define max_size 128
//顺序队定义
typedef struct
{
    int data[max_size];
    int front;
    int rear;
}sq_queue;

//初始化
void init_sq_queue(sq_queue *qu)
{
    qu->front = qu->rear = 0;
}
//判断队空
void isEmpty(sq_queue *qu)
{
    if(qu->front == qu->rear)
        printf("队列为空！\n");
    else
        printf("队列不为空！\n");
}

//进队
int in_queue(sq_queue *qu,int x)
{
    if((qu->rear+1)%max_size == qu->front)//判断队列是否为满
    {
        printf("队列已满！\n");
        return 0;
    }
    qu->rear = (qu->rear + 1)%max_size;
    qu->data[qu->rear] = x;
    return 1;
}
//出队
int out_queue(sq_queue *qu,int *x)
{
    if(qu->rear == qu->front)//判断队列是否为空
    {
        printf("队列为空！\n");
        return 0;
    }
    qu->front = (qu->front + 1)%max_size;
    *x = qu->data[qu->front];
    return 1;
}
int main()
{
    sq_queue *qu;
    int x,y;
    qu = (sq_queue*)malloc(sizeof(sq_queue));
    isEmpty(qu);
    x = 5;
    in_queue(qu,x);
    isEmpty(qu);
    out_queue(qu,&y);
    printf("出队的元素y = %d\n",y);
    return 0;
}

//链队定义
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode;

hongCYu's Blog

hongCYu's Blog

数据结构——栈和队列

基本概念

栈的基本概念

队列的基本概念

栈和队列的存储结构、算法和应用

顺序栈

链栈

顺序队

城市观星指南——轻松找到北极星

python装饰器的理解与使用

Comments | 0 条评论

hongCYu's Blog