Stack

Created by Clark

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:

?

1 2 3 4 5

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

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

?

1 2 3 4 5

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

?

1 2 3 4

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

?

1 2 3

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

3.2 Push function 

Push funtion of a stack

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

?

1 2 3 4 5 6 7 8 9 10 11 12

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 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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

?

1 2 3 4 5 6 7 8 9

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

?

1 2 3 4 5 6 7 8 9

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

?

1 2 3 4 5 6 7 8 9

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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/