Рубрики

Структура данных стека (введение и программа)

Массивы, Связанный список, Стек

Стек — это линейная структура данных, которая следует определенному порядку, в котором выполняются операции. Порядок может быть LIFO (первым пришел — первым вышел) или FILO (первым пришел последним вышел).

В основном в стеке выполняются следующие три основные операции:

  • Push: Добавляет элемент в стек. Если стек заполнен, это называется условием переполнения.
  • Pop: удаляет элемент из стека. Элементы появляются в обратном порядке, в котором они помещены. Если стек пуст, то говорят, что это условие Underflow.
  • Peek или Top: возвращает верхний элемент стека.
  • isEmpty: возвращает true, если стек пуст, иначе false.

Как понять стек практически?
Есть много реальных примеров стека. Рассмотрим простой пример тарелок, наложенных друг на друга в столовой. Пластина, которая находится сверху, является первой, которая должна быть удалена, то есть пластина, которая была помещена в самое нижнее положение, остается в стопке в течение самого длительного периода времени. Таким образом, можно просто наблюдать за порядком LIFO / FILO.

Время Сложности операций над стеком:

push (), pop (), isEmpty () и peek () — все занимают O (1) время. Мы не запускаем цикл ни в одной из этих операций.

Приложения стека:

Реализация:
Существует два способа реализации стека:

  • Используя массив
  • Использование связанного списка

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

C ++

/ * C ++ программа для реализации базового стека

   операции * /

#include <bits/stdc++.h>

  

using namespace std;

  
#define MAX 1000

  

class Stack {

    int top;

  

public:

    int a[MAX]; // Максимальный размер стека

  

    Stack() { top = -1; }

    bool push(int x);

    int pop();

    int peek();

    bool isEmpty();

};

  

bool Stack::push(int x)

{

    if (top >= (MAX - 1)) {

        cout << "Stack Overflow";

        return false;

    }

    else {

        a[++top] = x;

        cout << x << " pushed into stack\n";

        return true;

    }

}

  

int Stack::pop()

{

    if (top < 0) {

        cout << "Stack Underflow";

        return 0;

    }

    else {

        int x = a[top--];

        return x;

    }

}

int Stack::peek()

{

    if (top < 0) {

        cout << "Stack is Empty";

        return 0;

    }

    else {

        int x = a[top];

        return x;

    }

}

  

bool Stack::isEmpty()

{

    return (top < 0);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    class Stack s;

    s.push(10);

    s.push(20);

    s.push(30);

    cout << s.pop() << " Popped from stack\n";

  

    return 0;

}

С

// C программа для реализации массива стека
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

  
// Структура для представления стека

struct Stack {

    int top;

    unsigned capacity;

    int* array;

};

  
// функция для создания стека заданной емкости. Инициализирует размер
// складывается как 0

struct Stack* createStack(unsigned capacity)

{

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

    stack->capacity = capacity;

    stack->top = -1;

    stack->array = (int*)malloc(stack->capacity * sizeof(int));

    return stack;

}

  
// стек заполнен, когда вершина равна последнему индексу

int isFull(struct Stack* stack)

{

    return stack->top == stack->capacity - 1;

}

  
// Стек пуст, когда вершина равна -1

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

  
// Функция для добавления элемента в стек. Это увеличивает вершину на 1

void push(struct Stack* stack, int item)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = item;

    printf("%d pushed to stack\n", item);

}

  
// Функция для удаления элемента из стека. Это уменьшает вершину на 1

int pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return INT_MIN;

    return stack->array[stack->top--];

}

  
// Функция для возврата вершины из стека без ее удаления

int peek(struct Stack* stack)

{

    if (isEmpty(stack))

        return INT_MIN;

    return stack->array[stack->top];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Stack* stack = createStack(100);

  

    push(stack, 10);

    push(stack, 20);

    push(stack, 30);

  

    printf("%d popped from stack\n", pop(stack));

  

    return 0;

}

Джава

/ * Java-программа для реализации базового стека
операции * /

class Stack {

    static final int MAX = 1000;

    int top;

    int a[] = new int[MAX]; // Максимальный размер стека

  

    boolean isEmpty()

    {

        return (top < 0);

    }

    Stack()

    {

        top = -1;

    }

  

    boolean push(int x)

    {

        if (top >= (MAX - 1)) {

            System.out.println("Stack Overflow");

            return false;

        }

        else {

            a[++top] = x;

            System.out.println(x + " pushed into stack");

            return true;

        }

    }

  

    int pop()

    {

        if (top < 0) {

            System.out.println("Stack Underflow");

            return 0;

        }

        else {

            int x = a[top--];

            return x;

        }

    }

  

    int peek()

    {

        if (top < 0) {

            System.out.println("Stack Underflow");

            return 0;

        }

        else {

            int x = a[top];

            return x;

        }

    }

}

  
// Код драйвера

class Main {

    public static void main(String args[])

    {

        Stack s = new Stack();

        s.push(10);

        s.push(20);

        s.push(30);

        System.out.println(s.pop() + " Popped from stack");

    }

}

питон

# Python-программа для реализации стека

  
# импорт maxsize из модуля sys
# Используется для возврата -infinite, когда стек пуст

from sys import maxsize

  
# Функция для создания стека. Инициализирует размер стека как 0

def createStack():

    stack = []

    return stack

  
# Стек пуст, когда размер стека равен 0

def isEmpty(stack):

    return len(stack) == 0

  
# Функция для добавления элемента в стек. Увеличивает размер на 1

def push(stack, item):

    stack.append(item)

    print(item + " pushed to stack ")

      
# Функция для удаления элемента из стека. Уменьшает размер на 1

def pop(stack):

    if (isEmpty(stack)):

        return str(-maxsize -1) # возврат минус бесконечность

      

    return stack.pop()

  
# Функция для возврата вершины из стека без ее удаления

def peek(stack):

    if (isEmpty(stack)):

        return str(-maxsize -1) # возврат минус бесконечность

    return stack[len(stack) - 1]

  
# Драйверная программа для проверки вышеуказанных функций

stack = createStack()

push(stack, str(10))

push(stack, str(20))

push(stack, str(30))

print(pop(stack) + " popped from stack")

C #

// C # программа для реализации базового стека
// операции

using System;

  

namespace ImplementStack {

class Stack {

    private int[] ele;

    private int top;

    private int max;

    public Stack(int size)

    {

        ele = new int[size]; // Максимальный размер стека

        top = -1;

        max = size;

    }

  

    public void push(int item)

    {

        if (top == max - 1) {

            Console.WriteLine("Stack Overflow");

            return;

        }

        else {

            ele[++top] = item;

        }

    }

  

    public int pop()

    {

        if (top == -1) {

            Console.WriteLine("Stack is Empty");

            return -1;

        }

        else {

            Console.WriteLine("{0} popped from stack ", ele[top]);

            return ele[top--];

        }

    }

  

    public int peek()

    {

        if (top == -1) {

            Console.WriteLine("Stack is Empty");

            return -1;

        }

        else {

            Console.WriteLine("{0} popped from stack ", ele[top]);

            return ele[top];

        }

    }

  

    public void printStack()

    {

        if (top == -1) {

            Console.WriteLine("Stack is Empty");

            return;

        }

        else {

            for (int i = 0; i <= top; i++) {

                Console.WriteLine("{0} pushed into stack", ele[i]);

            }

        }

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

class Program {

    static void Main()

    {

        Stack p = new Stack(5);

  

        p.push(10);

        p.push(20);

        p.push(30);

        p.printStack();

        p.pop();

    }

}
}

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

Выход :

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack

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

C ++

// C ++ программа для реализации стека в связанном списке
#include <bits/stdc++.h>

using namespace std;

  
// Структура для представления стека

class StackNode {

public:

    int data;

    StackNode* next;

};

  

StackNode* newNode(int data)

{

    StackNode* stackNode = new StackNode();

    stackNode->data = data;

    stackNode->next = NULL;

    return stackNode;

}

  

int isEmpty(StackNode* root)

{

    return !root;

}

  

void push(StackNode** root, int data)

{

    StackNode* stackNode = newNode(data);

    stackNode->next = *root;

    *root = stackNode;

    cout << data << " pushed to stack\n";

}

  

int pop(StackNode** root)

{

    if (isEmpty(*root))

        return INT_MIN;

    StackNode* temp = *root;

    *root = (*root)->next;

    int popped = temp->data;

    free(temp);

  

    return popped;

}

  

int peek(StackNode* root)

{

    if (isEmpty(root))

        return INT_MIN;

    return root->data;

}

  

int main()

{

    StackNode* root = NULL;

  

    push(&root, 10);

    push(&root, 20);

    push(&root, 30);

  

    cout << pop(&root) << " popped from stack\n";

  

    cout << "Top element is " << peek(root) << endl;

  

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// C программа для реализации стека связанных списков
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

  
// Структура для представления стека

struct StackNode {

    int data;

    struct StackNode* next;

};

  

struct StackNode* newNode(int data)

{

    struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));

    stackNode->data = data;

    stackNode->next = NULL;

    return stackNode;

}

  

int isEmpty(struct StackNode* root)

{

    return !root;

}

  

void push(struct StackNode** root, int data)

{

    struct StackNode* stackNode = newNode(data);

    stackNode->next = *root;

    *root = stackNode;

    printf("%d pushed to stack\n", data);

}

  

int pop(struct StackNode** root)

{

    if (isEmpty(*root))

        return INT_MIN;

    struct StackNode* temp = *root;

    *root = (*root)->next;

    int popped = temp->data;

    free(temp);

  

    return popped;

}

  

int peek(struct StackNode* root)

{

    if (isEmpty(root))

        return INT_MIN;

    return root->data;

}

  

int main()

{

    struct StackNode* root = NULL;

  

    push(&root, 10);

    push(&root, 20);

    push(&root, 30);

  

    printf("%d popped from stack\n", pop(&root));

  

    printf("Top element is %d\n", peek(root));

  

    return 0;

}

Джава

// Java-код для реализации связанного списка

  

public class StackAsLinkedList {

  

    StackNode root;

  

    static class StackNode {

        int data;

        StackNode next;

  

        StackNode(int data)

        {

            this.data = data;

        }

    }

  

    public boolean isEmpty()

    {

        if (root == null) {

            return true;

        }

        else

            return false;

    }

  

    public void push(int data)

    {

        StackNode newNode = new StackNode(data);

  

        if (root == null) {

            root = newNode;

        }

        else {

            StackNode temp = root;

            root = newNode;

            newNode.next = temp;

        }

        System.out.println(data + " pushed to stack");

    }

  

    public int pop()

    {

        int popped = Integer.MIN_VALUE;

        if (root == null) {

            System.out.println("Stack is Empty");

        }

        else {

            popped = root.data;

            root = root.next;

        }

        return popped;

    }

  

    public int peek()

    {

        if (root == null) {

            System.out.println("Stack is empty");

            return Integer.MIN_VALUE;

        }

        else {

            return root.data;

        }

    }

  

    public static void main(String[] args)

    {

  

        StackAsLinkedList sll = new StackAsLinkedList();

  

        sll.push(10);

        sll.push(20);

        sll.push(30);

  

        System.out.println(sll.pop() + " popped from stack");

  

        System.out.println("Top element is " + sll.peek());

    }

}

питон

# Python-программа для реализации стека в связанном списке

  
# Класс для представления узла

class StackNode:

  

    # Конструктор для инициализации узла

    def __init__(self, data):

        self.data = data 

        self.next = None

  

class Stack:

      

    # Конструктор для инициализации корня связанного списка

    def __init__(self):

        self.root = None

  

    def isEmpty(self):

        return True if self.root is None else  False 

  

    def push(self, data):

        newNode = StackNode(data)

        newNode.next = self.root 

        self.root = newNode

        print "% d pushed to stack" %(data)

      

    def pop(self):

        if (self.isEmpty()):

            return float("-inf")

        temp = self.root 

        self.root = self.root.next 

        popped = temp.data

        return popped

      

    def peek(self):

        if self.isEmpty():

            return float("-inf")

        return self.root.data

  
# Драйвер программы для тестирования над классом

stack = Stack()

stack.push(10)        

stack.push(20)

stack.push(30)

  

print "% d popped from stack" %(stack.pop())

print "Top element is % d " %(stack.peek())

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// код C # для реализации связанного списка

using System;

  

public class StackAsLinkedList {

  

    StackNode root;

  

    public class StackNode {

        public int data;

        public StackNode next;

  

        public StackNode(int data)

        {

            this.data = data;

        }

    }

  

    public bool isEmpty()

    {

        if (root == null) {

            return true;

        }

        else

            return false;

    }

  

    public void push(int data)

    {

        StackNode newNode = new StackNode(data);

  

        if (root == null) {

            root = newNode;

        }

        else {

            StackNode temp = root;

            root = newNode;

            newNode.next = temp;

        }

        Console.WriteLine(data + " pushed to stack");

    }

  

    public int pop()

    {

        int popped = int.MinValue;

        if (root == null) {

            Console.WriteLine("Stack is Empty");

        }

        else {

            popped = root.data;

            root = root.next;

        }

        return popped;

    }

  

    public int peek()

    {

        if (root == null) {

            Console.WriteLine("Stack is empty");

            return int.MinValue;

        }

        else {

            return root.data;

        }

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

  

        StackAsLinkedList sll = new StackAsLinkedList();

  

        sll.push(10);

        sll.push(20);

        sll.push(30);

  

        Console.WriteLine(sll.pop() + " popped from stack");

  

        Console.WriteLine("Top element is " + sll.peek());

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

Плюсы: реализация связанного списка стека может расти и уменьшаться в зависимости от потребностей во время выполнения.
Минусы: Требуется дополнительная память из-за использования указателей.

Мы расскажем о реализации приложений стека в отдельных постах.

Набор стеков -2 (инфикс в постфикс)

Тест : вопросы о стеке

Ссылки:
http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#Problem_Description

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Структура данных стека (введение и программа)

0.00 (0%) 0 votes