C语言数据结构之栈（STACK）的实现

C语言数据结构之栈（STACK）的实现

先入后出原则（FILO，FIRST IN LAST OUT），也就是木柴堆原则，太史公史记汲郑列传：陛下用群臣如积薪耳，后来者居上。可见汉武帝是懂得如何使用栈这一数据结构的！😃

实现一个简单的保存整数的栈

• 定义存贮空间 stackelts
• 定义栈指针 top
• 定义入栈操作函数 stack_push
• 定义出栈操作函数 stack_pop
• 定义输出栈相关信息函数 stack_info
• 定义判断是否为空／是否为满函数 stack_is_empty stack_is_full
• 默认栈长度为8，测试函数向栈中推入8个整数，然后弹出

代码如下：

/* filename : stack.c */
#include <stdio.h>

/* compile : gcc stack.c -o stack */
/*     run : ./stack              */

/* define stack size */
#define STSIZE 8

/* define var stackelts to save val and top pointer */
static int stackelts[STSIZE] = {0};
static int top = -1;

/* if stack is empty return 1 else return 0 */
int
stack_is_empty (void)
{
  if (top == -1) return 1;
  return 0;
}

/* if stack is full return 1 else return 0 */
int
stack_is_full (void)
{
  if (top == STSIZE - 1) return 1;
  return 0;
}

/* push val into stack if stack is full out warning and do nothing */
void
stack_push (int val)
{
  if (top >= STSIZE)
    {
      printf ("Warning : stack is full!\n");
      top = STSIZE - 1;
    }
  else
    {
      top = top + 1;
      stackelts[top] = val;
    }
}

/* pop val from stack if stack is empty out warning and do nothing */
int
stack_pop (void)
{
  int tmp = 0;
  if (top <= -1)
    {
      printf ("Warning : stack is empty!\n");
      top = -1;
    }
  else
    {
      tmp = stackelts[top];
      stackelts[top] = 0;
      top = top - 1;
    }
  return tmp;
}

/* out content int stack and infomation */
void
stack_info (void)
{
  printf ("Stack top is %d\n[ ", top);
  for (int i = 0; i < STSIZE; i++)
    printf ("%d ", stackelts[i]);
  printf ("]\n--------------------\n");
}

/* ------------------------------ */

/**/
void
test_stack (void)
{
  if (stack_is_empty())
    printf ("Stack is empty now!\n");
  printf ("--------------------\n");

  for (int i = 999; i >= 200; i = i - 111)
    stack_push (i);
  stack_info ();

  if (stack_is_full())
    printf ("Stack is full now!\n");
  printf ("--------------------\n");

  for (int j = 0; j < STSIZE; j++)
    printf ("%d\n", stack_pop());
  printf ("--------------------\n");
}

/**/
int
main (int argc, char *argv[])
{
  test_stack ();
  return 0;
}
/* [>>>>>>>>] */

编译运行，结果如下，基本达到预期：

songvm@ubuntu:~/works/xdn/loo$ gcc stack.c -o stack
songvm@ubuntu:~/works/xdn/loo$ ./stack 
Stack is empty now!
--------------------
Stack top is 7
[ 999 888 777 666 555 444 333 222 ]
--------------------
Stack is full now!
--------------------
222
333
444
555
666
777
888
999
--------------------
songvm@ubuntu:~/works/xdn/loo$ 

封装成为Stack数据类型

• Stack包含三个成员
• 无类型的指针数组 elts，无类型指针，可以向栈中推入多种类型的数据
• 栈的长度 size，初始为0
• 栈顶指针 top
• 创建 stack_new 与释放 stack_free
• 推入 stack_push 与弹出 stack_pop
• 是否为空是否为满 stack_is_empty stack_is_full
• 输出信息 stack_info
• 默认栈长度为8，测试向栈中推入8个字符串，然后弹出，同时判断栈是否为空／满

代码如下：

/* filename : stack.c */
#include <stdio.h>
#include <stdlib.h>

/* define stack size */
#define STSIZE 8

/* define function pointer to out content in stack */
typedef void (*STFunc) (void *val);

/* define the Stack datatype */
typedef struct _Stack Stack;
struct _Stack {
  void **elts;
  int size;
  int top;
};

/* create a new stack */
Stack*
stack_new (int size)
{
  Stack *st = (Stack*) malloc (sizeof(Stack));
  st->elts = (void**) malloc (size * sizeof(void*));
  for (int i = 0; i < size; i++)
    st->elts[i] = NULL;
  st->size = size;
  st->top = -1;
  return st;
}

/* free the stack */
void
stack_free (Stack *st)
{
  free (st->elts);
  free (st);
}

/* push val into stack */
void
stack_push (Stack *st, void *val)
{
  if (st->top >= st->size)
    {
      printf ("Warning : stack is full!\n");
      st->top = st->size - 1;
    }
  else
    {
      st->top = st->top + 1;
      st->elts[st->top] = val;
    }
}

/* pop val from stack */
void*
stack_pop (Stack *st)
{
  void *tmp = NULL;
  if (st->top <= -1)
    {
      printf ("Warning : stack is empty!\n");
      st->top = -1;
    }
  else
    {
      tmp = st->elts[st->top];
      st->elts[st->top] = NULL;
      st->top = st->top - 1;
    }
  return tmp;
}

/* if stack is empty return 1 else return 0 */
int
stack_is_empty (Stack *st)
{
  if (st->top == -1) return 1;
  return 0;
}

/* if stack if full return 1 else return 0 */
int
stack_is_full (Stack *st)
{
  if (st->top == st->size - 1) return 1;
  return 0;
}

/* output stack information */
void
stack_info (Stack *st, STFunc stfunc)
{
  printf ("Stack size is %d\n", st->size);
  printf ("Stack top  is %d\n[ ", st->top);
  for (int i = 0; i <= st->top; i++)
    stfunc (st->elts[i]);
  printf ("]\n------------------------------\n");
}

/* ------------------------- */

/* function of *STFunc */
void
out_string (void *val)
{
  printf ("%s ", (char*)val);
}

/**/
void
test_stack (void)
{
  char *buf[8] = {"OOOO", "PPPP", "QQQQ", "RRRR",
		  "SSSS", "TTTT", "UUUU", "VVVV"};
  Stack *st = stack_new (STSIZE);

  if (stack_is_empty (st))
    printf ("Stack is empty now!\n");
  printf ("------------------------------\n");

  for (int i = 0; i < 8; i++)
    stack_push (st, buf[i]);

  stack_info (st, out_string);

  if (stack_is_full (st))
    printf ("Stack is full now!\n");
  printf ("------------------------------\n");

  for (int i = 0; i < 8; i++)
    printf ("%s\n", (char*)stack_pop(st));

  stack_free (st);
}

/**/
int
main (int argc, char *argv[])
{
  test_stack ();
  return 0;
}
/* [>>>>>>>>] */

编译运行，达到预期，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc stack.c -o stack
songvm@ubuntu:~/works/xdn/loo$ ./stack
Stack is empty now!
------------------------------
Stack size is 8
Stack top  is 7
[ OOOO PPPP QQQQ RRRR SSSS TTTT UUUU VVVV ]
------------------------------
Stack is full now!
------------------------------
VVVV
UUUU
TTTT
SSSS
RRRR
QQQQ
PPPP
OOOO
songvm@ubuntu:~/works/xdn/loo$ 

• 下一步研究一下队列（Queue）！！！