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

21.03.2008, 19:44. **Показов** 12886. **Ответов** 2

Студворк — интернет-сервис помощи студентам

Необходимо на простом С реализовать структуру данных стэк с помошью связного списка.
Так же реализовать работу с записью\выводом чисел из списка (IN\OUT)

Но это в идеале. А вообще, буду очень благодарен, если просто объясните как на Си шке организовать стэк через двусторонний связный список.

23.03.2008, 18:11

Вот Вам пример реализаци простейшего стека элементов типа MyStackType (в данном случае это int). Реализованы функции добавление элемента в конец стека, получения указателя на последний элемент стека, и удаления последнего элемента из стека, а также функции создания и удаления самого стека. Данный стек односвязанный.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*MyStack.h*/
 
#include "stdlib.h"
#include "windows.h"
 
typedef int MyStackType;
typedef struct MyStack *pMyStack;
 
/*<Создание стека.*/
pMyStack MyStackCreate();
 
/*Добавление элемента в конец стека.*/
BOOL MyStackPush( pMyStack  This, MyStackType Value);
 
/*Получение указателя на последний элемент в стеке.*/
MyStackType* MyStackTop( pMyStack  This );
 
/*Удаление последнего элемента  в стеке.*/
void MyStackPop( pMyStack  This );
 
/*Проверка: Пуст ли стек.*/
BOOL MyStackEmply( pMyStack  This );
 
/*Уничтожение стека.*/
void MyStackDel( pMyStack  This );

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*MyStack.c*/
 
#include "MyStack.h" 
struct MyStackIterator
{
    struct MyStackIterator *Last;   /*<Указатель на предыдущий элемент в стеке.*/
    MyStackType             Value;  /*<Значение.*/
};
 
struct MyStack  /*<Структура описывающая стек.*/
{
    struct MyStackIterator *TopIter;    /*<Указатель на последний элемент в стеке.*/
};
 
/*<Создание стека.*/
pMyStack MyStackCreate()
{
    pMyStack Stack;
    Stack = malloc(sizeof(struct MyStack));
    if ( Stack != NULL )
        Stack->TopIter = NULL;
    return Stack;
}
 
/*Добавление элемента в конец стека.*/
BOOL MyStackPush( pMyStack  This, MyStackType Value)
{
    struct MyStackIterator  *NewIter;
    
    if( This == NULL )
        return FALSE;
 
    NewIter = malloc( sizeof(struct MyStackIterator) );
    if( NewIter == NULL )
        return FALSE;
    
    NewIter->Last       = This->TopIter;
    NewIter->Value      = Value;
    This->TopIter   = NewIter;
 
    return TRUE;
}
 
/*Получение указателя на последний элемент в стеке.*/
MyStackType* MyStackTop( pMyStack  This )
{   
    if( This == NULL )
        return NULL;
 
    return &(This->TopIter->Value);
}
 
/*Удаление последнего элемента  в стеке.*/
void MyStackPop( pMyStack  This )
{   
    struct MyStackIterator  *Iter;
 
    if( This == NULL )
        return;
 
    Iter = This->TopIter;
 
    This->TopIter = This->TopIter->Last;
 
    if ( Iter != NULL )
        free( Iter );
}
 
/*Проверка: Пуст ли стек.*/
BOOL MyStackEmply( pMyStack  This )
{
    if( This == NULL )
        return TRUE;
 
    if( This->TopIter == NULL )
        return TRUE;
    
    return FALSE;
}
 
/*Уничтожение стека.*/
void MyStackDel( pMyStack  This )
{
    if( This == NULL )
        return;
 
    /*Пока стек не пуст, удаляем из него элементы.*/
    while( MyStackEmply( This ) == FALSE )
        MyStackPop( This );
 
    /*Удаляем сам стек.*/
    free(This);
}

Вот небольхой тест (пример использования):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*test.c*/
 
#include "MyStack.h" 
#include "stdio.h" 
 
int main()
{
    unsigned int i;
    pMyStack Stack = MyStackCreate();
    if( Stack == NULL )
        return -1;
    
    /*Кладем данные в стек.*/
    for(i=0; i<9; ++i)
        MyStackPush( Stack, i );
    
    /*Пока стек не пуст бкерем из него данные.*/
    while(  MyStackEmply( Stack ) == FALSE )
    {
        printf("%i ", *MyStackTop( Stack ) );
        MyStackPop( Stack );
    }
 
    MyStackDel( Stack );
    return 0;
}

PS. Вобще для этого дела язык С++ подходит гораздо лучше, к тому же в STL уже есть сласс для стека.

27.02.2010, 21:33

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include "stack.h"
struct Stack
{
    struct item *top;
    DWORD count;
    HANDLE hHeap;
    CRITICAL_SECTION sec;
};
struct item
{
    PVOID data;
    struct item *next;
    DWORD tag;
    SIZE_T size;
};
BOOL CreateStack(struct Stack **stack)
{
    HANDLE hHeap;
    hHeap = HeapCreate(HEAP_NO_SERIALIZE, 0, 0);
    if (!hHeap)
    {
        return FALSE;
    }
    *stack = HeapAlloc(hHeap, 0, sizeof **stack);
    if (!*stack)
    {
        HeapDestroy(hHeap);
        return FALSE;
    }
    (*stack)->hHeap = hHeap;
    (*stack)->top = NULL;
    (*stack)->count = 0;
    InitializeCriticalSection(&(*stack)->sec);
    return TRUE;
}
BOOL StackPush(struct Stack **stack, PVOID data, SIZE_T size, DWORD tag)
{
    struct item *cr;
    EnterCriticalSection(&(*stack)->sec);
    cr = HeapAlloc((*stack)->hHeap, 0, sizeof *(*stack)->top);
    if (!cr)
    {
        LeaveCriticalSection(&(*stack)->sec);
        return FALSE;
    }
    cr->data = HeapAlloc((*stack)->hHeap, 0, size);
    if (!cr->data)
    {
        HeapFree((*stack)->hHeap, 0, cr);
        LeaveCriticalSection(&(*stack)->sec);
        return FALSE;
    }
    memmove(cr->data, data, size);
    cr->size = size;
    cr->tag = tag;
    cr->next = (*stack)->top;
    (*stack)->top = cr;
    (*stack)->count++;
    LeaveCriticalSection(&(*stack)->sec);
    return TRUE;
}
BOOL StackPop(struct Stack **stack, PVOID data, PSIZE_T size, PDWORD tag, void(*pfndel)(PVOID data, DWORD tag, SIZE_T size))
{
    struct item *cr;
    EnterCriticalSection(&(*stack)->sec);
    if (!(*stack)->top)
    {
        LeaveCriticalSection(&(*stack)->sec);
        return FALSE;
    }
    cr = (*stack)->top->next;
    memmove(data, (*stack)->top->data, (*stack)->top->size);
    if (size)
    {
        *size = (*stack)->top->size;
    }
    if (tag)
    {
        *tag = (*stack)->top->tag;
    }
    if (pfndel)
    {
        (*pfndel)((*stack)->top->data, (*stack)->top->tag, (*stack)->top->size);
    }
    HeapFree((*stack)->hHeap, 0, (*stack)->top->data);
    HeapFree((*stack)->hHeap, 0, (*stack)->top);
    (*stack)->top = cr;
    (*stack)->count--;
    LeaveCriticalSection(&(*stack)->sec);
    return TRUE;
}
VOID DestroyStack(struct Stack **stack)
{
    HANDLE hHeap;
    hHeap = (*stack)->hHeap;
    DeleteCriticalSection(&(*stack)->sec);
    HeapFree((*stack)->hHeap, 0, *stack);
    HeapDestroy(hHeap);
    *stack = NULL;
}
DWORD GetStackCountItem(struct Stack **stack)
{
    return (*stack)->count;
}

C++
1
2
3
4
5
6
7
8
9
#if !defined (stack_h_)
#define stack_h_
#include <windows.h>
BOOL CreateStack(struct Stack **stack);
BOOL StackPush(struct Stack **stack, PVOID data, SIZE_T size, DWORD tag);
BOOL StackPop(struct Stack **stack, PVOID data, PSIZE_T size, PDWORD tag, void(*pfndel)(PVOID data, DWORD tag, SIZE_T size));
VOID DestroyStack(struct Stack **stack);
DWORD GetStackCountItem(struct Stack **stack);
#endif /* stack_h_ */

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

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

Решение

Решение

Curator

	Реализовать стэк с помощью связного списка 21.03.2008, 19:44. Показов 12886. Ответов 2 Метки нет (Все метки) Необходимо на простом С реализовать структуру данных стэк с помошью связного списка. Так же реализовать работу с записью\выводом чисел из списка (IN\OUT) Но это в идеале. А вообще, буду очень благодарен, если просто объясните как на Си шке организовать стэк через двусторонний связный список.