Stack ---- Implementation in C and Python

Stack

            In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop.[1] The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. Often a peek or top operation is also implemented, returning the value of the top element without removing it.

   A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.

   A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition. Therefore, the lower elements are those that have been on the stack the longest.

linked list代码实现：

stack.h

#ifndef _STACK_H
#define _STACK_H 1

#define EMPTY     0
#define NON_EMPTY 1

struct node
{	
	int data;
	struct node* next;
};

#ifndef _CREAT_STACK_H
#define _CREAT_STACK_H 1
	#include "creat_stack.h"
#endif

#ifndef _PUSH_STAKC_H
#define _PUSH_STACK_H 1
	#include "push_stack.h"
#endif

#ifndef _IS_EMPTY_H
#define _IS_EMPTY_H 1
	#include "is_empty.h"
#endif

#endif
           

stack_test.c

/*****************************************************************************
code writer : EOF
code date : 2014.03.03
e-mail:[email protected]
code purpose :
		This is just a test code for stack that I created.
If there is something wrong with my code, please touche me by e-mail.

*****************************************************************************/
#include <stdio.h>
#include "stack.h"

#define ARRAYSIZE 10

int main()
{
	int temp = 0;
	int array[ARRAYSIZE] = {1,2,3,4,5,6,7,8,9,10};
	
	struct node* p_top = NULL;	

	p_top = creat_stack();
	
	for(temp = 0;temp < ARRAYSIZE; temp++)
	{
		push_stack(&p_top,array[temp]);
	}

	for(temp = 0;temp < ARRAYSIZE; temp++)
	{
		pop_stack(p_top);
	}
	
	return 0;
}
           

creat_stack.c

/*********************************************************************
code writer : EOF
code date : 2014.03.03
e-mail : [email protected]
code purpose : 
		This code is my implementation for function creat_stack.
functin creat_stack would creat a the first node of the stack and just only
the first node. You must know what is stack...

If there is something wrong with my code, please touch me by e-mail.

**********************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

struct node* creat_stack(void)
{
	struct node* p_top = NULL;

	p_top = (struct node*)malloc(sizeof(struct node));
	
	if(p_top == NULL)
	{
		printf("malloc failed\n");
	}
	
	p_top->next = NULL;

	while(is_empty(p_top) == NON_EMPTY)
	{
		pop_stack(p_top);	
	}
	
	return p_top;
}
           

push_stack.c

/*******************************************************************
code writer : EOF
code date:2014.03.03
e-mail:[email protected]
code purpose :
	This is my implementaion for function push_stack
If there is somrthing wrong with my code, please touche me by e-mail.

*******************************************************************/
#include "stdlib.h"
#include "stack.h"
#include "stdio.h"

int push_stack(struct node** pp_top,int number)
{
	struct node* temp = NULL;
	struct node* new_node = NULL;
	
	new_node = (struct node*)malloc(sizeof(struct node));
	
	if(new_node == NULL)
	{
		printf("malloc failed\nprocess end\n");
		return 0;
	}
	
	new_node->data = number;
	new_node->next = (*pp_top)->next;
	(*pp_top)->next = new_node;
}
           

pop_stack.c

/*****************************************************************
code writer: EOF
code date: 2014.03.03
e-mail: [email protected]
code purpose :
	This code is a implementation for function pop_stack
If there is something wrong with my code, please touch me by e-mail

*****************************************************************/
#include "stdlib.h"
#include "stdio.h"
#include "stack.h"

int pop_stack(struct node* p_top)
{
	struct node* temp = NULL;
	
	if(is_empty(p_top) == EMPTY)
	{
		printf("empty stack!\nprocess end");
		return EMPTY;
	}
	else
	{
		temp = p_top->next;
		p_top->next = p_top->next->next;
		printf("%d\n",temp->data);
		free(temp);
	}
}
           

is_empty.c

/**********************************************************************
code writer: EOF
code date : 2014.03.03
e-mail: [email protected]
code purpose :
	This code is a implementation for function is_empty
If there is something wrong with my code, please touch me by e-mail.

**********************************************************************/
#include "stdio.h"
#include "stack.h"

int is_empty(struct node* p_node)
{
	if(p_node->next == NULL)
	{
		return EMPTY;
	}
	else
	{
		return NON_EMPTY;
	}
}
           

如果代码有值得改进的地方请联系我，谢谢。同样希望我的代码能够为大家的学习做出一点贡献。

update: 2014.09.13

给出数组版本的stack实现

stack.h

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	stack.h
e-mail		:	[email protected]

code purpose	:
	This file("stack.h") a header file  for
sources file which are used for a implementation
of ADT-stack in array-type.

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#ifndef _STACK_H
#define _STACK_H 1

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

	#define FAILED_RET   -1
	#define SUCCESS_RET   0

	#define FULL_STACK    1
	#define UNFULL_STACK  0

	#define EMPTY_STACK   1
	#define UNEMPTY_STACK 0

	#define STACK_SIZE 1024

	/*
	**	This is a beautiful abstract of "stack".
	*/
	struct stack
	{
		int top_of_stack;
		int stack_size;
		int array[STACK_SIZE];
	};

	struct stack* init_stack(void);
	void stack_release(struct stack* p_stack);

	int pop(struct stack* p_stack);
	int push(struct stack* p_stack,int num);

	int is_empty(struct stack* p_stack);
	int is_full(struct stack* p_stack);

#endif
           

init_stack.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	init_stack.h
e-mail		:	[email protected]

code purpose	:
	This file("init_stack.c") a source file  for
a implementation of ADT-stack in array-type.

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

struct stack* init_stack(void)
{

	struct stack* p_stack = NULL;
 
	p_stack = (struct stack*)malloc(sizeof(struct stack));

	if(!p_stack)
	{
		printf("In %s: line:%d malloc failed\n",__FUNCTION__,__LINE__);
		return 0;
	}
	else
	{
		p_stack->top_of_stack = STACK_SIZE;
		p_stack->stack_size   = STACK_SIZE;
	}

	return p_stack;
}
           

is_empty.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	is_empty.c
e-mail		:	[email protected]

code purpose	:
	This file("is_empty.c") a implementation for 
function "is_empty()".

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

int is_empty(struct stack* p_stack)
{
	if(p_stack->top_of_stack >= p_stack->stack_size)
	{
		return EMPTY_STACK;
	}
	else
	{
		return UNEMPTY_STACK;	
	}
}
           

is_full.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	is_full.c
e-mail		:	[email protected]

code purpose	:
	This file("is_full.c") a implementation for 
functin "is_full()".

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

int is_full(struct stack* p_stack)
{
	if(p_stack->top_of_stack < 0)
	{
		return FULL_STACK;
	}
	else
	{
		return UNFULL_STACK;
	}
}
           

pop.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	pop.c
e-mail		:	[email protected]

code purpose	:
	This file("pop.c") a implementation for
functin "pop()".

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

int pop(struct stack* p_stack)
{
	int index = p_stack->top_of_stack;
	int ret   = 0;

	if(is_empty(p_stack) == UNEMPTY_STACK)
	{
		
		ret = p_stack->array[index];

		(p_stack->top_of_stack)++;

		return ret;
	}
	else
	{
		printf("ATTENTION! empty stack can't pop anything!\n");

	}
	
	return FAILED_RET;
}
           

push.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	push.c
e-mail		:	[email protected]

code purpose	:
	This file("push.c") a implementation for 
functin "is_full()".

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

int push(struct stack* p_stack,int num)
{

	int index = p_stack->top_of_stack;
	int ret   = 0;

	if(is_full(p_stack) == FULL_STACK)
	{
		printf("ATTENTION! Stack is full and can't be pushed.");
	}
	else
	{
		index = --(p_stack->top_of_stack);

		p_stack->array[index] = num;

		return SUCCESS_RET;
	}
		

	return FAILED_RET;
}
           

stack_release.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	stack_release.c
e-mail		:	[email protected]

code purpose	:
	This file("stack_release.c") a source file
which is used for implementation of stack_release().

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

void stack_release(struct stack* p_stack)
{
	free(p_stack);
}
           

stack_release.c

/*****************************************************
Code writer	:	EOF
Code date	:	2014.09.13
code file	:	stack_test.c
e-mail		:	[email protected]

code purpose	:
	This file("stack_test.c") a source file  which
contain a main-function which is used for testing
my stack.

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

*****************************************************/
#include "stack.h"

int main()
{
	struct stack* my_stack = init_stack();

	int tmp = 0;

	for(tmp = 0; tmp < 10; tmp++)
	{
		printf("%3d ",tmp+1);
		push(my_stack,tmp+1);
	}
	printf("\n");

	for(tmp = 0; tmp < 10; tmp++)
	{
		printf("%3d ",pop(my_stack));
	}
	printf("\n");

	stack_release(my_stack);

	return 0;
}
           

最后Makefile也贴了...

SOURCE_FILE:=	init_stack.c is_empty.c is_full.c pop.c push.c stack_test.c stack_release.c

OBJECT_FILE:=	init_stack.o is_empty.c is_full.o pop.o push.o stack_test.o stack_release.o

a.out:$(OBJECT_FILE)

compile:
	gcc -c $(SOURCE_FILE)

link:
	gcc $(OBJECT_FILE) -o ./a.out

clean:
	rm -r ./*.o ./a.out
           

Python 实现:

"""
Code writer	:	EOF
Code date	:	2015.01.12
code file	:	stack.h
e-mail		:	[email protected]

code purpose	:
	Stack is implemented in Python.

	If there is something wrong with my code, 
please touch me by e-mail. Thank you.

#BUG-fix-up 2015.02.09
          self.S[0] -= 1
          return self.S[self.S[0]] 


"""


class Stack() :

      S = []
      def __init__(self, arg = []):
          self.S = [len(arg)] + arg

      def stack_empty(self) :
          if self.S[0] == 0 :
             return True
          else :
             return False

      def push(self,x) :

          self.S[0] += 1

          if len(self.S) > self.S[0] :
             self.S[self.S[0]] = x
          else :
                self.S = self.S + [x]

          return self.S

      def pop(self) :
          if self.stack_empty() == True :
             print "underflow"
          else :
                temp = self.S[0]
                self.S[0] -= 1
                return self.S[temp] 

      def show_stack(self) :
          print "stack status:",self.S[1 : self.S[0] + 1]


#------------------------------------------

input_num = [1,2,3,4,5]

stk = Stack(input_num)

print "initial status"
stk.show_stack()

stk.push(10)
stk.push(1)
stk.push(-1)
stk.push(0)

print " stk.push(10)" + \
      " stk.push(1)"  + \
      " stk.push(-1)" + \
      " stk.push(0)"

stk.show_stack()

print " stk.pop() " + \
      " stk.pop() " 

stk.pop()
stk.pop()
stk.show_stack()