Stack

1. Definition
A stack is a special type of list that removing or adding 1 element takes place at the top of bottom of list. In other way, stack is a data structure having two basic functions: push (adding one more element) and pop (getting and removing last element). Because of that features, stacks are called rule data structure LIFO (Last In First Out)

LIFO structure

2. Some examples of stack
A stack of books in a tale, a stack of CD in a box, ... When you add one book into the stack, the book will be in the top of the stack. When you get the book out of the stack, it will be put out first.

A stack of books

There are two general types of stack: a stack installed on an array (array stack), a stack installed on a linked list (linked list stack)

3. Stack installed on an array
An array stack is simple to install, but size is fixed so it is not flexible with a large amount of data
The structure of an array stack could be defined somethings like this:

#define MAX 100
typedef struct {
 int top;
 int data[MAX];
} stack;

3.1 Initial empty array, check if the array is empty or full

void StackInitial(stack *s) 
{
 s->top = -1;
 return;
}

int isStackEmpty(stack s)
{
 return (s.top == -1);
}

int isStackFull(stack s){
 return (s.top == MAX - 1);
}

3.2 Push function

Push funtion of a stack

void Push(stack *s, int x)
{
 if(isStackFull(*s))
 {
  printf("Stack is full!\n");
  return;
 }
 else
 {
  s->top++;
  s->data[s->top] = x;
  return;
 }
}

3.3 Pop function

Pop function of a stack

int Pop(stack *s)
{
 if(isStackEmpty(*s))
 {
  printf("Stack is empty\n");
  return;
 }
 else
 {
  return s->data[s->top--];
 }
}

3.4 Create a main function to test the stack type installed

int main()
{
 int a;

 // Creating stack and initialing
 stack *s = (stack *) malloc(sizeof(stack));
 StackInitial(s);
 printf("%d\n", isStackEmpty(*s));

 // Push and Pop
 Push(s, 10);
 Push(s, 20);
 Push(s, 50);

 a = Pop(s);
 printf("%d\n", a);
 a = Pop(s);
 printf("%d\n", a);
 
 return 0;
}

3.5 Full code You can download the full code here
Full code

4. Stack installed on a Linked List
Because an array stack has fixed size, so we need a type of stack that can be change, for some purposes, to avoid wasting memories or lacking of memories. We use linked list stack

A linked list stack Structure

struct node
{
 int data;
 struct node *next;
};
typedef struct node *stacknode;
typedef struct {
 stacknode top;
} stack;

4.1 Initial empty array, check if the array is empty

void StackInitial(stack *s)
{
 s->top = NULL;
 return;
}
int StackEmpty(stack s)
{
 return (s.top == NULL);
}

4.2 Push function

Push function of a linked list stack

void Push(stack *s, int x)
{
 stacknode p;
 p = (stacknode) malloc(sizeof(struct node));
 p->data = x;
 p->next = s->top;
 s->top = p;
 return;
}

4.3 Pop function

Pop function of a linked list stack

struct node
int Pop(stack *s)
{
 stacknode p;
 if (StackEmpty(*s))
 {
  printf("Stack is empty\n");
 }
 else
 {
  p = s->top;
  s->top = s->top->next;
  return p->data;
 }
}

4.4 Create a main function to test the stack type installed

int main()
{
 int a = 0;
 stack *s = (stack *) malloc(sizeof(stack));
 StackInitial(s);
 printf("%d\n", StackEmpty(*s));
 Push(s, 10);
 Push(s, 20);
 Push(s, 30);
 a = Pop(s);
 printf("%d\n", a);
 a = Pop(s);
 printf("%d\n", a);

 return 0;
}

4.5 Full code You can download the full code here
Full code

Reference:
http://www.nguyenvanquan7826.com/2014/12/29/lap-trinh-c-bai-15-cai-dat-ngan-xep-stack/
http://www.tutorialspoint.com/data_structures_algorithms/stack_program_in_c.htm
http://www.sanfoundry.com/c-programming-examples-stacks/