Структуры данных — стеки и очереди

искусственный интеллект алгоритм задняя часть

предисловие

Эта глава начинает вторую часть структур данных, стеков и очередей:
куча:

  • структура хранения стека
  • Основные операции стека

очередь:

  • Структура хранения очереди
  • Основные операции с очередями

куча

Мы называем структуру данных «первым пришел — последним вышел», похожую на журнал, стеком, и стек ограниченВставка и удаление операций только в конце таблицыМы называем конец стека, допускающий вставку и удаление, вершиной стека, а другой конец — его низом. Стек без каких-либо элементов данных называется пустым стеком.

Стек — это, прежде всего, линейная таблица, то есть элементы стека имеют линейное отношение, то есть отношение предшественника и преемника, но это особая линейная таблица.

Особенность стека в том, что он ограничивает размер линейного списка.Позиции вставки и удаления всегда выполняются только в верхней части стека.. Это также делает: нижняя часть стека фиксирована, а самый продвинутый стек может быть только внизу стека.

Операция вставки в стек называется push, удаление стека называется pop.

1. Структура хранения стека

Структура хранения данных, соответствующая элементам данных стека, называется структурой хранения стека.

1.1 Структура последовательного хранения стека

Стек — это частный случай линейной таблицы, поэтому последовательная структура хранения стека на самом деле является аббревиатурой последовательной структуры хранения линейного списка, которую мы для краткости называем последовательным стеком. Линейная таблица реализована с помощью массива.Для линейной таблицы типа стека, который можно вставлять и удалять только с одного конца, конец массива с индексом 0 (дно стека не меняется, нужны только для отслеживания изменений в верхней части стека) используется в качестве стека, нижняя часть больше подходит.

Последовательный стек определяется следующим образом:

typedef struct
{
    int data[maxsize];    //定义一个数组大小为maxsize的数组,用来存放栈中数据元素
    int top;              //栈顶指针
}SqStack;                 //顺序栈定义

1.2 Цепная структура хранения стека

ПучокВершина стека помещается в начало односвязного списка., структура данных, которая использует связанный список для хранения стека, называется связанным стеком.

Узлы стека ссылок определяются следующим образом:

typedef struct LNode
{
    int data;                //数据域
    struct LNode *next;      //指针域
}LNode;                      //链栈结点

2. Работа со стеком

2.1 Работа последовательного стека

Для последовательного стека всего 4 элемента, включая два специальных состояния и две операции.

Особый статус:
1) Пустое состояние стека:st.top == -1, также используетсяst.top = 0Указывает, что стек пуст, а верхняя позиция стека в это время равна 0.
2) Полное состояние стека:st.top == maxsize-1Указывает, что стек заполнен. maxsize — это максимальное количество элементов в стеке, а maxsize-1 — это позиция верхнего элемента в массиве, когда стек заполнен, поскольку позиция массива начинается с 0.

работать:
Операции проталкивания и извлечения последовательного стека выполняются на вершине стека, поэтому вам нужно только изменить положение вершины стека, чтобы достичь цели проталкивания и извлечения из стека.

1) Инициализировать стек:

void initStack(SqStack &st)    //初始化栈
{
    st.top = -1;               //栈顶指针设置为-1
}

2) Операция стека:

int push(SqStack &st,int x)
{
    if(st.top == maxsize-1)    //判断栈是否满,如果满,则不能进栈
        return 0;
    ++(st.top);                //栈顶指针位置加1
    st.data[st.top] = x        //x进栈,放在st.top位置
        return 1;
}

3) Поп-операция:
Выталкивание и нажатие являются соответствующими операциями

int push(SqStack &st,int x)
{
    if(st.top == -1)           //判断栈是否为空,如果空,则不能进行出栈
        return 0;
    x = st.data[st.top]     //先把栈顶元素取出来
    --(st.top);                 //栈顶指针位置减1
    return 1;
}

4) Работа упрощенной версии:

/*初始化栈*/
int stack[maxsize];
int top = -1;

/*元素x进栈*/
stack[++top] = x

/*元素x出栈*/
x = stack[top--]

/*注意++top和top++的区别*/
top = 1
a = ++top
b = top++

a = 2
b = 1

2.2 Работа цепного стека

Аналогично последовательному стеку, цепной стек также имеет 4 элемента, включая два состояния и две операции.

государство:
1) Стек пуст:lst -> next == NULL, то есть, когда в стеке нет узлов-последователей, стек пуст.
2) Стек заполнен: если пространство для хранения бесконечно, стек не будет заполнен.

работать:
Проталкивание цепного стека — это операция вставки связанного списка, установленного методом вставки головы, всплывающее окно — удаление односвязного списка.

链栈的插入操作
Вставить операцию цепного стека

栈的删除操作
операция удаления стека

1) Инициализация стека цепочки:

void initStack(LNode *&lst)
{
    lst = (LNode*)malloc(sizeof(LNode));    //制造一个头结点
    lst -> next = NULL;                     //初始头结点指向为NULL
}

2) Нажмите на стек:

void push(LNode *lst,int x)
{
    LNode *p;
    p = (LNode*)malloc(sizeof(LNode));    //为进栈元素申请结点空间
    p -> next =NULL;                      //初始化结点不指向任何元素

    /*进栈,相当于链表的头插法*/
    p -> data = x;    //将x赋值给p结点的值域
    p -> next = lst -> next;    //p指针指向原lst指向的结点
    lst -> next = p;            //lst指向结点p
}

3) Вскройте стек:

int pop(LNode *lst,int &x)
{
    LNode *p;
    if(lst -> next == NULL)    //栈空则不能出栈,返回0;而栈不会满,所以在进栈的时候未作判断
        return 0;
    /*出栈,相当于链表的删除结点*/
    p = lst -> next;
    x = p -> data;
    lst -> next = p -> next;
    free(p);
    return 1;
}

4) Упрощенная версия:

/*元素(指针p所指)进栈操作*/
/*类似于头插法建立链表*/
p -> next = lst -> next;    //将空栈的头结点指向p
lst -> next = p;            //将指针p指向空栈头结点


/*出栈操作(出栈元素保存在x中)*/
/*类似于单链表的删除操作*/
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);

очередь:

Очередь разрешена толькоВставьте операции на одном конце и удалите операции на другомОчередь представляет собой линейную таблицу по принципу «первым поступил — первым вышел», называемую FIFO, конец, который позволяет вставку, называется задним (задним), а конец, допускающий удаление, называется началом очереди (передним). Вставка элемента в очередь называется входом в очередь, а новый элемент, поступающий в очередь, становится новым хвостовым элементом; удаление элемента из очереди называется удалением из очереди, и после удаления элемента из очереди его последующий элемент становится новым головным элементом. .

1. Структура хранения очереди

Структура данных, используемая для хранения элементов данных очереди.

1.1 Структура последовательного хранения очереди:

При использовании таблицы последовательности для хранения очереди элемент очереди удаляется из очереди в начале очереди, то есть там, где нижний индекс равен 0. голова очереди всегда находится в позиции, где нижний индекс равен 0, что значительно увеличивает временную сложность.


Структура данных, которая использует таблицу последовательности для хранения элементов очереди, называется структурой хранения последовательности очереди, которая определяется следующим образом:

typedef struct
{
    int data[maxsize];        //定义数组
    int front;                //队首指针
    int rear;                 //队尾指针
}SqQuene;                     //顺序队列定义

1.2 Цепная структура хранения очереди:

Структура данных, которая использует связанный список для хранения элементов очереди, называется структурой хранения очереди с цепочкой, которая определяется следующим образом:


Определение типа узла очереди:

typedef struct QNode
{
    int data;                //数据域
    struct QNode *next;      //指针域
}QNode;                      //队结点类型定义

Определение типа цепной команды:

typedef struct
{
    QNode *front;        //队头指针
    QNode *rear;         //队尾指针
}LiQuene;                //链队类型定义

2. Работа с очередью

2.1 Круговая очередь

Поскольку временная сложность последовательной очереди высока, всегда есть проблемы, требующие решения.Почему голова очереди должна стоять на позиции с нижним индексом 0? Поэтому кто-то предложил не ограничивать условие, что элементы очереди должны храниться в первых n элементах массива, так что головной элемент не обязательно должен находиться в нулевой позиции нижнего индекса. Однако по мере того, как элементы очереди удаляются из очереди, начало указателя очереди перемещается назад.Предполагая, что указатель хвоста уже находится в позиции maxsize-1, в это время, хотя в очереди все еще есть место для хранения, хвост указателя очереди очередь больше не может войти в очередь, как показано на следующем рисунке.


Хотя на позициях с нижними индексами 0 и 1 еще есть место, новые элементы больше не могут поступать в очередь в конце очереди. Мы называем эту ситуацию "ложным переполнением". Чтобы решить проблему этого ложного переполнения, мы предложить Концепция циклической очереди позволяет соединить голову и хвост очереди.Эта последовательная структура хранения с соединенными головой и хвостом называется циклической очередью.

Циклическая очередь должна терять определенное количество пустого пространства, поэтому переднее = заднее происходит только тогда, когда очередь пуста.

Элементы кольцевой очереди:

Два состояния:
Статус команды пустой:

qu.rear = qu.front

Полный статус команды:

(qu.rear+1)%maxsize == qu.front

Две операции:
Операция добавления элемента x в очередь (перемещение указателя хвоста)

qu.rear = (qu.rear+1)%maxSize;
qu.data[qu.rear] = x;

Операция удаления из очереди элемента x (перемещение указателя заголовка очереди)

qu.front = (qu.front+1)%maxSize;
x = qu.data[qu.front];

Инициализируйте алгоритм очереди:

void initQueue(SqQueue &qu)
{
    qu.front = qu.rear = 0;队首和队尾指针重合,并且指向0
}

Алгоритм очереди:

int enQueue(SqQueue &qu,int x)
{
    if ((qu.rear + 1) % maxSize == qu.front)    //队满的判断条件,如果队满则不能进队,返回0
        return 0;
    qu.rear = (qu.reat+1)%maxSize;              //若队不满,先移动队尾指针
    qu.data[qu.rear] = x;                       //元素x进队
    return 1;
}

Алгоритм удаления из очереди:

int enQueue(SqQueue &qu,int &x)
{
    if (qu.rear == qu.front)    //队空的判断条件,如果队空则不能出队,返回0
        return 0;
    qu.front = (qu.front+1)%maxSize;              //若队不空,先移动队首指针
    x = qu.data[qu.front] ;                       //元素x出队
    return 1;
}

2.2 Сетевая команда:

Команда цепочки должна использовать структуру хранения цепочки для хранения очереди. В команде цепочки четыре элемента: пустой и полный, а также элементы, входящие и выходящие из очереди.


Статус команды пустой:

lqu -> rear == NULL; or lqu -> front == NULL

Полный статус команды:
Вообще говоря, не бывает ситуации, когда команда заполнена, если памяти достаточно.

Операция постановки элемента в очередь (указатель p указывает на элемент постановки в очередь)

lqu -> rear -> next = p;
lqu -> rear = p;

Операция удаления элемента из очереди (x сохраняет элемент, удаленный из очереди)

p = lqu -> front;
lqu -> front = p -> next;
x = p -> data;
free(p);

Инициализируйте цепной алгоритм

void initQueue(LiQuene *&lqu)
{
    lqu = (LiQueue*)malloc(sizeof(LiQueue));
    lqu -> front = lqu -> rear = NULL;
}

Алгоритм оценки пустой очереди

int isQueueEmpty(LiQueue *lqu)
{
    if(lqu -> rear == NULL || lqu -> front == NULL)
        return 1;
    else
        return 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;           //将新结点链接到队尾,rear指向该结点
        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(q);
    return 1;
}