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()
