This passage provides a description about stack and an implement for the stack in C.

Introduction

Stack is a data structure that follows one principle - "first in, last out". Any data structure that fits this principle is stack.

Thus, we can create a stack based on linkedList or arrayList(rarely use). The reason why we use linkedList is that it can dynamically enlarge its size. However, the size of arrayList is determined during the initialization.

A stack contains two variables: top and down. "Top" points to the top of the stack; "Down" points to the bottom of the stack. Its working priciples can be seen in the following animation:

Workflow of stack

Code

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
	int data;
	struct Node * pNext;
}Node, *pNode;

typedef struct Stack {
	pNode Top;
	pNode Bottom;
}Stack, *pStack;

bool isEmpty(pStack);
void initStack(pStack);
void push(pStack, int);
void pop(pStack);
void traverse(pStack);
void clear(pStack);

int main(void) {

	Stack s;

	initStack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	pop(&s);
	traverse(&s);
	clear(&s);
	traverse(&s);

	return 0;
}

bool isEmpty(pStack ps) {
	if (ps->Bottom == ps->Top)
		return true;
	return false;
}

void initStack(pStack ps) {
	pNode pTemp = (pNode)malloc(sizeof(Node));
	if (pTemp == NULL) {
		printf("Fail to allocate memory");
		exit(0);
	}
	ps->Bottom = pTemp;
	ps->Top = pTemp;
	pTemp->pNext = NULL;
}

void push(pStack ps, int val) {
	pNode pTemp = (pNode)malloc(sizeof(Node));
	pTemp->data = val;
	pTemp->pNext = ps->Top;
	ps->Top = pTemp;
}

void pop(pStack ps) {
	if (isEmpty(ps)) {
		printf("Stack is empty");
		return;
	}
	pNode pTemp = ps->Top;
	ps->Top = ps->Top->pNext;
	free(pTemp);
}

void traverse(pStack ps) {
	if (isEmpty(ps)) {
		printf("Stack is empty");
		return;
	}
	pNode pHead = ps->Top;
	while (pHead != ps->Bottom) {
		printf("%d\n",pHead->data);
		pHead = pHead->pNext;
	}
}

void clear(pStack ps) {
	while (ps->Top != ps->Bottom) {
		pNode pTemp = ps->Top;
		ps->Top = ps->Top->pNext;
		free(pTemp);
	}
}