Over the last three posts, we created a tailless linked list, extended it into a tailed list, and finally we implemented a double linked list that solved the O(n) complexity hurdles. Each step added speed, but with that came some tradeoffs along with complexity. <\/p>\n\n\n\n
For Day 4, I have decided that the next logical step is to implement a Stack data structure, but instead of starting from raw memory and building everything from scratch, we\u2019re going to focus on behavior and benchmarks first (this will all make sense at the end of the blog post so hang with me).<\/p>\n\n\n\n
A stack is one of the simplest and most fundamental data structures in computer science.<\/p>\n\n\n\n
It follows a single rule:<\/p>\n\n\n\n
Last In, First Out (LIFO)<\/strong><\/p>\n\n\n\n If you push items onto a stack:<\/p>\n\n\n\n Then popping removes them in reverse order:<\/p>\n\n\n\n A stack usually exposes a very small API, and we will keep the operations to just these to make our lives easy:<\/p>\n\n\n\n Notice something important here:<\/p>\n\n\n\n A stack only ever interacts with one end<\/strong> of the structure \u2014 the top.<\/p>\n\n\n\n This turns out to matter a lot when choosing how to implement one. For the astute among you, you can probably see where we are going with this given our last few posts. <\/p>\n\n\n\n Stacks show up everywhere:<\/p>\n\n\n\n \u2022 Function call stacks Before we talk about how this stack is implemented, let\u2019s look at real performance numbers.<\/p>\n\n\n\n These benchmarks are:<\/p>\n\n\n\n Each push allocates memory. This is the \u201chonest\u201d cost of dynamic allocation, and this performance readout follows the same general structure as the ones in our last posts: <\/p>\n\n\n\n Ignore the censored part of the metrics \ud83d\ude42<\/p>\n\n\n\n The key takeaways:<\/p>\n\n\n\n This is exactly what we want from a stack, and it is also identical to the previous charts for our tailless, tailed, and doubly linked list implementations. <\/p>\n\n\n\n Here\u2019s the key concept for this post:<\/p>\n\n\n\n A data structure is defined by its behavior and guarantees \u2014 not by how it is stored internally.<\/p>\n<\/blockquote>\n\n\n\n If another structure already provides the complexity guarantees we need\u2026<\/p>\n\n\n\n We can reuse it.<\/p>\n\n\n\n This entire stack implementation is built on top of our tailless singly linked list<\/strong>.<\/p>\n\n\n\n No new node structures. Just restricted access.<\/p>\n\n\n\n That\u2019s it.<\/p>\n\n\n\n A stack is literally:<\/p>\n\n\n\n A linked list where you are only allowed to touch the head.<\/p>\n<\/blockquote>\n\n\n\n Because of this, our tailless linked list fits the bill perfectly. Here is ALL the code for your reference:<\/p>\n\n\n\n stack.h<\/strong><\/p>\n\n\n\n stack.c<\/strong><\/p>\n\n\n\nPush A\nPush B\nPush C<\/code><\/pre>\n\n\n\nPop \u2192 C\nPop \u2192 B\nPop \u2192 A<\/code><\/pre>\n\n\n\n
\n\n\n\nCore Stack Operations<\/h2>\n\n\n\n
push() \/\/ Add item to top\npop() \/\/ Remove item from top\npeek() \/\/ Read top without removing\nis_empty() \/\/ Check if stack is empty<\/code><\/pre>\n\n\n\n
\n\n\n\nWhy Stacks Matter in Real Systems<\/h1>\n\n\n\n
\u2022 Undo\/redo systems
\u2022 Expression parsing
\u2022 DFS graph traversal
\u2022 Embedded buffering patterns
\u2022 Temporary working memory in algorithms<\/p>\n\n\n\n
\n\n\n\nPerformance First \u2014 Benchmarking the Implementation<\/h1>\n\n\n\n
\n
Each pop frees memory.<\/p>\n\n\n\n=== Stack (L****d L**t) Benchmark ===\nReal implementation timing (includes malloc\/free)\n\n=============================\nBENCH N=1000\n=============================\npush O(1)\/op total O(N) | 0.031 ms | 30.9 ns\/op\npeek O(1)\/op | 0.987 ms | 0.5 ns\/op (REPS=2000000)\npop O(1)\/op (+free) | 0.008 ms | 8.3 ns\/op\n\n=============================\nBENCH N=3000\n=============================\npush O(1)\/op total O(N) | 0.089 ms | 29.6 ns\/op\npeek O(1)\/op | 1.112 ms | 0.6 ns\/op (REPS=2000000)\npop O(1)\/op (+free) | 0.026 ms | 8.7 ns\/op\n\n=============================\nBENCH N=10000\n=============================\npush O(1)\/op total O(N) | 0.272 ms | 27.2 ns\/op\npeek O(1)\/op | 1.023 ms | 0.5 ns\/op (REPS=2000000)\npop O(1)\/op (+free) | 0.087 ms | 8.7 ns\/op\n\n=============================\nBENCH N=30000\n=============================\npush O(1)\/op total O(N) | 0.699 ms | 23.3 ns\/op\npeek O(1)\/op | 0.939 ms | 0.5 ns\/op (REPS=2000000)\npop O(1)\/op (+free) | 0.235 ms | 7.8 ns\/op\n\n=============================\nBENCH N=100000\n=============================\npush O(1)\/op total O(N) | 2.360 ms | 23.6 ns\/op\npeek O(1)\/op | 0.935 ms | 0.5 ns\/op (REPS=2000000)\npop O(1)\/op (+free) | 0.786 ms | 7.9 ns\/op\n<\/code><\/pre>\n\n\n\nOperation<\/th> Complexity<\/th><\/tr><\/thead> push<\/td> O(1)<\/td><\/tr> pop<\/td> O(1)<\/td><\/tr> peek<\/td> O(1)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\nThe Important Engineering Idea<\/h1>\n\n\n\n
\n
\n\n\n\nSurprise! \u2014 The Stack Is Just Our Linked List!<\/h1>\n\n\n\n
No new memory management.
No new traversal logic.<\/p>\n\n\n\n
\n\n\n\nMapping Stack Operations \u2192 Linked List Operations<\/h2>\n\n\n\n
Stack<\/th> Linked List<\/th><\/tr><\/thead> push<\/td> push_front<\/td><\/tr> pop<\/td> pop_front<\/td><\/tr> peek<\/td> front<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n \n
\n\n\n\n#ifndef STACK_H\n#define STACK_H\n\n#include "linked_list.h"\n\n\/\/ our stack is literally just wrapping our tailless linked list\nstruct Stack {\n struct Node* head;\n size_t size;\n};\n\nvoid stack_init(struct Stack* s);\nvoid stack_destroy(struct Stack* s);\n\nint stack_push(struct Stack* s, struct Node* n);\nint stack_pop(struct Stack* s);\nstruct Node* stack_peek(const struct Stack* s);\n\nint stack_is_empty(const struct Stack* s);\nsize_t stack_size(const struct Stack* s);\n\n#endif<\/code><\/pre>\n\n\n\n#include "stack.h"\n\nvoid stack_init(struct Stack* s) {\n if (!s) return;\n s->head = NULL;\n s->size = 0;\n}\n\nvoid stack_destroy(struct Stack* s) {\n if (!s) return;\n list_destroy(&s->head); \/\/ uses linked_list.c\n s->size = 0;\n}\n\nint stack_push(struct Stack* s, struct Node* n) {\n if (!s || !n) return -1;\n push_front(n, &s->head); \/\/ uses linked_list.c\n s->size++;\n return 0;\n}\n\nint stack_pop(struct Stack* s) {\n if (!s || !s->head) return -1;\n pop_front(&s->head); \/\/ uses linked_list.c (and frees node)\n s->size--;\n return 0;\n}\n\nstruct Node* stack_peek(const struct Stack* s) {\n if (!s) return NULL;\n return front(s->head); \/\/ uses linked_list.c\n}\n\nint stack_is_empty(const struct Stack* s) {\n return (!s || s->head == NULL);\n}\n\nsize_t stack_size(const struct Stack* s) {\n return s ? s->size : 0;\n}<\/code><\/pre>\n\n\n\n