Stack implementation in C and Python with singly linked lists
The straighforward way to do it is to have a global pointer to the top of the stack:
#include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; } *top; // the scope of *top is now global typedef struct node node; void push(int value) { node *new = malloc(sizeof(node)); assert(new != NULL); new->data = value; new->next = top; top = new; } void pop() { node *temp = top; top = top->next; free(temp); } void display() { node *sp = top; while (sp != NULL) { printf("%d ", sp->data); sp = sp->next; } printf("(over)\n\n"); } int main() { top = NULL; push(10); push(20); pop(); push(30); display(); pop(); display(); push(99); display(); return 0; }
However, it is also possible to get rid of the global variable by passing around the address of the stack pointer:
#include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { int value; struct node *next; }; typedef struct node node; void display(node *n) { while (n->next != NULL) { printf("%d --> ", n->value); n = n->next; } printf("%d (end).\n\n", n->value); } void push(node **sp, int v) { node *newNode = malloc(sizeof(node)); assert(newNode != NULL); newNode->value = v; newNode->next = *sp; *sp = newNode; } void pop(node **sp) { node *temp = *sp; *sp = (*sp)->next; free(temp); printf("pop!\n\n"); } int main() { node *stackPointer = NULL; push(&stackPointer, 10); push(&stackPointer, 20); push(&stackPointer, 30); display(stackPointer); pop(&stackPointer); display(stackPointer); push(&stackPointer, 99); display(stackPointer); return 0; }
A nice diagram showing the push() function:
The Python version is pretty much the first C version written in OOP style.
#!/usr/bin/env python class Node: def __init__(self, value): self.value = value self.next = None class Stack: def __init__(self): self.stack = None def push(self, value): new = Node(value) new.next = self.stack self.stack = new def pop(self): self.stack = self.stack.next print 'pop!\n' def display(self): i = self.stack while i != None: print i.value i = i.next print '(end)\n' def main(): s = Stack() s.push(10) s.push(20) s.push(30) s.push(40) s.push(50) s.display() s.pop() s.pop() s.display() s.push(99) s.display() if __name__ == '__main__': main()