Очистить стэк
Стэк..
Ребят помогите написать ещё одну, по идее простую, задачу на си. Нужно перевернуть слово задом.
СТЭК
Необходимо реализовать метод класса СТЭК метод должен возвращать true в случае удачного завершения.
СТЭК не фурычит
Привет! Такая проблема, решил написать стэк, в элементах которого лежат указатели на массив.
Стэк из автобусов
Здравствуйте форумчане, я тут человек новый, уповаю на помощь знающих людей, так как обратится.
1392 / 1021 / 325
Регистрация: 28.07.2012
Сообщений: 2,810
Сообщение от Dimidr 
Как очистить стек?
Извлеч все элементы из стека, либо просто s=stack
Регистрация: 18.09.2015
Сообщений: 36
Что-то не хочет, можно пожалуйста поподробней?
Регистрация: 02.10.2015
Сообщений: 12
Сам реализовывал стек или это стандартный контейнер? Если сам, то стек на массиве или на списке?
Регистрация: 18.09.2015
Сообщений: 36
Получилось, спасибо за поддержку!)
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Инвертировать стэк
Тектс взял товарища с этого форума копирайты ему и респект вот этот чувак Monte-Cristo .
Стэк и связные списки
Товарищи, помогите задание на зачёт: нужно запрограммировать связный список, в котором объект.
Разработать класс стэк
Разработать класс стэк. Класс должен содержать набор методов для поддержки основных операций работы.
Реализация класса стэк
Необходимо реализовать методы класса СТЭК. Все методы должны возвращать true в случае удачного.
Или воспользуйтесь поиском по форуму:
Как очистить stack c
Класс Stack представляет коллекцию, которая использует алгоритм LIFO («последний вошел — первый вышел»). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции происходит в обратном порядке — извлекается тот элемент, который находится выше всех в стеке.
Стек — довольно часто встречаемая структура данных в реальной жизни. Банальные примеры стеков — стопка книг или тарелок, где каждую новую книгу или тарелку помещают поверх предыдущей. А извлекают из этой стопки книги/тарелки в обратном порядке — сначала самую верхнюю и так далее. Другой пример — одежда: допустим, человек выходит на улицу в зимнюю погоду и для этого сначала одевает майку, потом рубашку, затем свитер, и в конце куртку. Когда человек снимает с себя одежду — он делает это в обратном порядке: сначала снимает куртку, потом свитер и так далее.
Создание стека
Для создания стека можно использовать один из трех конструкторов. Прежде всего можно создать пустой стек:
Stack people = new Stack();
При создании пустого стека можно указать емкость стека:
Stack people = new Stack(16);
Также можно инициализировать стек элементами из другой коллекции или массивом:
var employees = new List < "Tom", "Sam", "Bob" >; Stack people = new Stack(employees); foreach (var person in people) Console.WriteLine(person); Console.WriteLine(people.Count); // 3
Для перебора стека можно использовать стандартный цикл foreach . Причем в цикле в соответствии с аалгоритмом стека LIFO данные извлекаются в порядке, обратном их добавлению. Консольный вывод в данном случае:
Bob Sam Tom 3
Для получения количества элементов стека применяется свойство Count .
Методы Stack
В классе Stack можно выделить следующие методы:
- Clear : очищает стек
- Contains : проверяет наличие в стеке элемента и возвращает true при его наличии
- Push : добавляет элемент в стек в верхушку стека
- Pop : извлекает и возвращает первый элемент из стека
- Peek : просто возвращает первый элемент из стека без его удаления
Посмотрим на примере:
var people = new Stack(); people.Push("Tom"); // people = < Tom >people.Push("Sam"); // people = < Sam, Tom >people.Push("Bob"); // people = < Bob, Sam, Tom >// получаем первый элемент стека без его удаления string headPerson = people.Peek(); Console.WriteLine(headPerson); // Bob string person1 = people.Pop(); // people = < Sam, Tom >Console.WriteLine(person1); // Bob string person2 = people.Pop(); // people = < Tom >Console.WriteLine(person2); // Sam string person3 = people.Pop(); // people = < >Console.WriteLine(person3); // Tom Работу стека можно представить следующей иллюстрацией:
Стоит отметить, что если с помощью методов Peek или Pop мы попытаемся получить первый элемент стека, который пуст, то программа выдаст исключение. Соответственно перед получением элемента мы можем проверять количество элементов в стеке:
if(people.Count > 0)
Либо можно использовать пару методов:
- bool TryPop(out T result) : удаляет из стека первый элемент и передает его в переменную result, возвращает true , если очередь не пуста и элемент успешно получен.
- bool TryPeek(out T result) : передает в переменную result первый элемент стека без его извлечения, возвращает true , если элемент успешно получен.
var people = new Stack(); people.Push("Tom"); // people = < Tom >// удаляем элементы var success1 = people.TryPop(out var person1); // success1 = true if (success1) Console.WriteLine(person1); // Tom var success2 = people.TryPeek(out var person2); // success2 = false if (success2) Console.WriteLine(person2); Стек
С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.
Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:
- PUSH – кладёт элемент на вершину стека
- POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу
Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.
Стек является одной из базовых структур данных и используется не только в программировании, но и в схемотехнике, и просто в производстве, для реализации технологических процессов и т.д.; стек используется в качестве вспомогательной структуры данных во многих алгоритмах и в других более сложных структурах.
Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.
Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.
Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.
Стек состоит из трёх элементов, вершина стека указывает на 7.
Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.
Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.
Вернёт 3, стек станет пуст.
Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.
Когда мы будем работать со стеком, возможны две основные и часто встречающиеся ошибки:
- 1. Stack Underflow: Попытка снять элемент с пустого стека
- 2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)
Программная реализация
- 1) Стек фиксированного размера на массиве
- 2) Динамически растущий стек на массиве
- 3) Динамически растущий стек на односвязном списке
Стек фиксированного размера, построенный на массиве
О тличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.
Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:
#define STACK_MAX_SIZE 20 typedef int T;
Теперь сама структура
typedef struct Stack_tag < T data[STACK_MAX_SIZE]; size_t size; >Stack_t;
Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.
Кладём новый элемент на стек.
void push(Stack_t *stack, const T value) < stack->data[stack->size] = value; stack->size++; >
Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) < if (stack->size >= STACK_MAX_SIZE) < exit(STACK_OVERFLOW); >stack->data[stack->size] = value; stack->size++; >
Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему
T pop(Stack_t *stack) < if (stack->size == 0) < exit(STACK_UNDERFLOW); >stack->size--; return stack->data[stack->size]; >
И функция peek, возвращающая текущий элемент с вершины
T peek(const Stack_t *stack) < if (stack->size return stack->data[stack->size - 1]; >
Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size
Вспомогательные функции для печати элементов стека
void printStackValue(const T value) < printf("%d", value); >void printStack(const Stack_t *stack, void (*printStackValue)(const T)) < int i; int len = stack->size - 1; printf("stack %d > ", stack->size); for (i = 0; i < len; i++) < printStackValue(stack->data[i]); printf(" | "); > if (stack->size != 0) < printStackValue(stack->data[i]); > printf("\n"); > Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |
Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch(); Рассмотрим также ситуации, когда есть ошибки использования. Underflow
void main()
void main() < Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) < push(&stack, i); >_getch(); >
Динамически растущий стек на массиве
Д инамически растущий стек используется в том случае, когда число элементов может быть значительным и не известно на момент решения задачи. Максимальный размер стека может быть ограничен каким-то числом, либо размером оперативной памяти.
Стек будет состоять из указателя на данные, размера массива (максимального), и числа элементов в массиве. Это число также будет и указывать на вершину.
typedef struct Stack_tag < T *data; size_t size; size_t top; >Stack_t;
Для начала понадобится некоторый начальный размер массива, пусть он будет равен 10
#define INIT_SIZE 10
Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER
#define MULTIPLIER 2
Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.
Во-первых, функции для создания и удаления стека и несколько ошибок
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() < Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) < exit(OUT_OF_MEMORY); >out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) < free(out); exit(OUT_OF_MEMORY); >out->top = 0; return out; > void deleteStack(Stack_t **stack) < free((*stack)->data); free(*stack); *stack = NULL; >
Всё крайне просто и понятно, нет никаких подвохов. Создаём стек с начальной длиной и обнуляем значения.
Теперь напишем вспомогательную функцию изменения размера.
void resize(Stack_t *stack) < stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) < exit(STACK_OVERFLOW); >>
Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.
Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер
void push(Stack_t *stack, T value) < if (stack->top >= stack->size) < resize(stack); >stack->data[stack->top] = value; stack->top++; >
Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера
T pop(Stack_t *stack) < if (stack->top == 0) < exit(STACK_UNDERFLOW); >stack->top--; return stack->data[stack->top]; > T peek(const Stack_t *stack) < if (stack->top return stack->data[stack->top - 1]; >
void main() < int i; Stack_t *s = createStack(); for (i = 0; i < 300; i++) < push(s, i); >for (i = 0; i < 300; i++) < printf("%d ", peek(s)); printf("%d ", pop(s)); >deleteStack(&s); _getch(); > Напишем ещё одну функцию, implode, которая уменьшает массив до размера, равного числу элементов в массиве. Она может быть использована тогда, когда уже известно, что больше элементов вставлено не будет, и память может быть частично освобождена.
void implode(Stack_t *stack) < stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); >
Можем использовать в нашем случае
for (i = 0; i < 300; i++) < push(s, i); >implode(s); for (i = 0; i
Эта однопоточная реализация стека использует мало обращений к памяти, достаточно проста и универсальна, работает быстро и может быть реализована, при необходимости, за несколько минут. Она используется всегда в дальнейшем, если не указано иное.
У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 2 раза (в нашем случае) требуется мало обращений к памяти, но при этом каждое последующее увеличение может привести к ошибке, особенно при маленьком количестве памяти в системе. Если же использовать более щадящий способ выделения памяти (например, каждый раз прибавлять по 10), то число обращений увеличится и скорость упадёт. На сегодня, проблем с размером памяти обычно нет, а менеджеры памяти и сборщики мусора (которых нет в си) работают быстро, так что агрессивное изменение преобладает (на примере, скажем, реализации всей стандартной библиотеки языка Java).
Реализация стека на односвязном списке
Ч то такое односвязный список, будет подробнее рассказано дальше. Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.
Никакого максимального и минимального размеров у нас не будет (хотя в общем случае может быть). Каждый новый элемент создаётся заново. Для начала определим структуру узел
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag < T value; struct Node_tag *next; >Node_t;
Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.
void push(Node_t **head, T value) < Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) < exit(STACK_OVERFLOW); >tmp->next = *head; tmp->value = value; *head = tmp; >
Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции
Node_t* pop1(Node_t **head) < Node_t *out; if ((*head) == NULL) < exit(STACK_UNDERFLOW); >out = *head; *head = (*head)->next; return out; >
T pop2(Node_t **head) < Node_t *out; T value; if (*head == NULL) < exit(STACK_UNDERFLOW); >out = *head; *head = (*head)->next; value = out->value; free(out); return value; >
Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.
Простая функция peek
T peek(const Node_t* head) < if (head == NULL) < exit(STACK_UNDERFLOW); >return head->value; >
Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца
void printStack(const Node_t* head) < printf("stack >"); while (head) < printf("%d ", head->value); head = head->next; > > И ещё одна проблема – теперь нельзя просто посмотреть размер стека. Нужно пройти от начала до конца и посчитать все элементы. Например, так
size_t getSize(const Node_t *head) < size_t size = 0; while (head) < size++; head = head->next; > return size; >
Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.
void main() < int i; Node_t *head = NULL; for (i = 0; i < 300; i++) < push(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); printf("%d ", pop2(&head)); >_getch(); > void main() < int i; Node_t *head = NULL; Node_t *tmp; for (i = 0; i < 300; i++) < push(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); tmp = pop1(&head); printf("%d ", tmp->value); free(tmp); > _getch(); > ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Достаточно полное определение, но возможно для новичков оно будет немного трудным для понимания.
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Код на C++
struct comp < //Структура с названием comp(от слова component) int Data; //Какие-то данные(могут быть любыми, к примеру можно написать int key; char Data; так-же можно добавить еще какие-либо данные) comp *next;//Указатель типа comp на следующий элемент >; Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
- Стек пуст, и нужно создать его
- Стек уже есть и нужно лишь добавить в него новый элемент
Код на C++
void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q типа структуры comp. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем необходимое число в Data элемента if (top == NULL) < //Если вершины нет, то есть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Обозначаем, что вершиной теперь является новый элемент > > Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
- Ячейка, которую нам нужно удалить является вершиной стека
- Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками
Код на C++
void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чтение памяти невозможно" или числа "-2738568384" или другие, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > Указатель q в данном случае играет такую же роль, что и указатель в блокноте, он бегает по всему стеку, пока не станет равным NULL(while(q != NULL)), другими словами, пока стек не закончится.
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Код на C++
void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Код на C++
void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Код на C++
#include ; #include ; struct comp < //Структура с именем comp int Data; //Кикие то данные(могут быть любими, к примеру можно написать int key; char Data; или добавить еще какие то данные) comp *next;//Указатель типа comp на следующий эелемент >; void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q, который приравниваем к вершине стека. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем D в Data элемента if (top == NULL) < //Если вершины нет, тоесть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Пишем, что вершиной теперь является новый элемент > > void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чение памяти невозможно" или числа "-2738568384" или других, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >54321
5321
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.