data-structures
стек

Введение в стек

Стек представляет собой структуру данных LIFO (last-in, first-out), то есть самый последний (или последний) элемент, добавленный в стек, будет первым удаленным элементом («first out»).

Рассмотрим пример книг в коробке. Только одна книга может быть добавлена ​​или удалена из коробки за раз, и ее можно только добавить и удалить сверху.

Теперь ящик с двумя двумя книгами выглядит так:

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

Если мы добавим книгу 3, она будет наверху. Остальные книги, которые были добавлены перед книгой 3, останутся ниже:

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

Коробка похожа на стек, а книги - это элементы данных. Добавление книги в окно - это операция нажатия, в то время как удаление / получение книги из верхней части окна является поп-операцией. Если мы выполним поп-операцию, мы получим книгу 3, и ящик вернется к тому, как это было до того, как мы подтолкнули книгу 3. Это означает, что последний (или последний) элемент, который мы положили, был первым элементом, который мы вышел (LIFO). Чтобы получить книгу 1, нам нужно выполнить еще два попса: один для удаления книги 2, а второй - для получения книги 1.

Реализация стека с использованием массива. Для этого нам нужен указатель, указывающий на верхнее местоположение (tos). Каждый раз, когда элемент вставляется в стек, tos увеличивается на единицу, и всякий раз, когда выполняется операция pop, индекс, указывающий верхнюю часть стека (tos), уменьшается на единицу.

ОТ СЕБЯ:

Перед выполнением операции PUSH

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

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

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP: поп-операция удаляет содержимое из верхней части стека и обновляет значение tos путем уменьшения на 1

Перед поп-операцией:

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

dataElment pop(){
    dataElment value = stack[tos--];
    return value;
}

После поп-операции:

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.
    

Использование стеков для поиска палиндромов

Палиндром - это слово, которое можно читать в обоих направлениях, например «байдарка».

В этом примере будет показано, как определить, является ли данное слово палиндром с использованием Python3.

Во-первых, нам нужно превратить строку в стек (мы будем использовать массивы в виде стеков).

str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element

Теперь мы должны инвертировать слово.

def invert(str):
    stk = [c for c in str]
    stk2 = []
    while len(stk) > 0:
        stk2.append(stk.pop())
    #now, let's turn stk2 into a string
    str2 = ""
    for c in stk2:
        str2 += c
    return str2

Теперь мы можем сравнить слово и перевернутую форму.

def palindrome(str):
    return str == invert(str)

Реализация стека с использованием массива и связанного списка

Реализация массива

#include<stdio.h>

#define MAX 100000                    //Global variables
int top = -1;
int a[MAX];

void push(int x){
    
    if(top == MAX-1){                         // Check whether stack is full
        printf("Stack Overflow\n");
        return;
    }
    
    a[++top] = x;                            // Otherwise increment top and insert x
}

void pop(){
    if(top == -1){                                     // if top = -1, empty stack
        printf("Empty stack\n");
        return;
    }
    top--;        
}

void print(){                         //printing stack values
    
    for(int i=0;i <= top;i++){
        printf("%d ",a[i]);        
    }        
    printf("\n");        
}

void topValue(){                        // Method can print the top value of a stack
    printf("%d",a[top]);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();
    topValue();    
    
}

Внедрение Linked List

#include<stdio.h>
#include<malloc.h>

 struct node{
    int data;
    node* link;
};
node* top = NULL;

void push(int data){
    
    node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->link = top;
    top = temp;
}

void pop(){
    
    if(top == NULL) return;
    node* temp = top;
    top = top->link;
    free(temp);
}
void print(){
    
    node* t = top;
    while(t != NULL){
        printf("%d ",t->data);
        t=t->link;
    }
    printf("\n");
}

void topValue(){
    printf("%d ",top->data);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();            
    topValue();    
}

Проверка сбалансированных скобок

Скобкой считается любой из следующих символов: ( , ) , { , } , [ или ] .

Две скобки считаются сопряженной парой, если открывающая скобка (т. Е. ( , [ , Или { ) встречается слева от закрывающей скобки (т. Е. ) , ] Или } ) того же самого типа. Существует три типа совпадающих пар скобок: [] , {} и () .

Соответствующая пара скобок не сбалансирована, если набор скобок, которые он заключает, не согласован. Например, {[(])} не сбалансирован, потому что содержимое между { и } не сбалансировано. Пара квадратных скобок заключает в себе один несбалансированный открывающий кронштейн ( и пара скобок заключает в себе одиночную, несбалансированную закрывающуюся квадратную скобку ] .

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

Он не содержит непревзойденных скобок.

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

Алгоритм:

1. Объявите стек (скажем, stack ).
2. Теперь перемещаем строковый ввод.

• a) Если текущий символ является стартовым скобком (т.е. ( или { или [ )), то нажмите его для стека.
• b) Если текущий символ является закрывающей скобкой (то есть ) или } или ] ), то поп из стека. Если всплывающий символ является подходящим стартовым скобком, то мелкие скобки еще not balanced .
• c) Если текущий символ является закрывающей скобкой (т.е. ) или } или ] ), и стек пуст, то скобки not balanced .

3. После полного обхода, если в стеке есть некоторая стартовая скобка, тогда строка not balanced у нас есть balanced строка.