堆栈操作

1、利用静态数组实现堆栈

/*
 * 利用静态数组实现堆栈
 */

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

#define STACK_TYPE int
#define STACK_SIZE 100

static STACK_TYPE stack[STACK_SIZE];
static int top_element = -1;

int is_empty(void)
{
    return top_element == -1;
}

int is_full(void)
{
    return top_element == STACK_SIZE - 1;
}

void push(STACK_TYPE value)
{
    assert(!is_full());
    stack[++top_element] = value;
}

STACK_TYPE pop(void)
{
    assert(!is_empty());
    return stack[top_element--];
}

int main()
{
    int i;
    push(0);
    push(1);
    push(2);
    push(3);
    push(4);

    for(i=0; i <= top_element; i++)
        printf("%4d", stack[i]);
    printf("\n");

    printf(" pop=%d\n", pop());

    for(i=0; i <= top_element; i++)
        printf("%4d", stack[i]);
    printf("\n");

  exit(0);
}

2、利用动态数组实现堆栈

/*
 * 利用动态数组实现堆栈
 */

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

#define STACK_TYPE int
#define STACK_SIZE 100

static STACK_TYPE *stack;
static size_t stack_size;
static int top_element = -1;

/*
 * malloc 动态分配数组，由 stack 指针指向的内存区是连续的
 * 可以通过 stack[] 这种数组的形式来对分配的内存进行操作。
 */
void creat_stack(size_t size)
{
    assert(stack ==0); //确保堆栈只创建一次
    stack_size = size;
    stack = malloc(stack_size * sizeof(STACK_TYPE));
    assert(stack != NULL); //确保内存分配成功
}

void destroy_stack(void)
{
    assert(stack_size > 0); //确保堆栈已存在
    stack_size = 0;
    free(stack);
    stack = NULL;
}

int is_empty(void)
{
    assert(stack_size > 0); //确保堆栈已存在，测试一个不存在的堆栈是否为空是没有意义的。
    return top_element == -1;
}

int is_full(void)
{
    assert(stack_size > 0); //确保堆栈已存在，测试一个不存在的堆栈是否为满是没有意义的。
    return top_element == stack_size - 1;
}

void push(STACK_TYPE value)
{
    assert(!is_full());
    stack[++top_element] = value;
}

STACK_TYPE pop(void)
{
    assert(!is_empty());
    return stack[top_element--];
}

int main()
{
    int i;
    creat_stack(10);

    push(5);
    push(6);
    push(7);
    push(8);
    push(9);

    for(i=0; i <= top_element; i++)
        printf("%4d", stack[i]);
    printf("\n");

    printf(" pop=%d\n", pop());
    printf(" pop=%d\n", pop());

    for(i=0; i <= top_element; i++)
        printf("%4d", stack[i]);
    printf("\n");

    destroy_stack();
  exit(0);
}

3、利用单链表实现堆栈，这个堆栈没有长度限制

/*
 * 利用单链表实现堆栈，这个堆栈没有长度限制。
 */

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

#define STACK_TYPE int
#define FALSE     0

typedef struct STACK_NODE{
    STACK_TYPE value;
    struct STACK_NODE *next;
}StackNode;

static struct STACK_NODE *stack = NULL;

int is_empty(void)
{
    return stack == NULL;
}

int is_full(void)
{
    return FALSE;//堆栈没有长度限制，永远都不会满
}

void push(STACK_TYPE value)
{
    struct STACK_NODE *new_node;
    new_node = malloc(sizeof(StackNode));
    assert(new_node != NULL);

    new_node->value = value;
    new_node->next = stack;
    stack = new_node;
}

void pop(void)
{
    struct STACK_NODE *first_node;
    assert(!is_empty());
    first_node = stack;
    stack = first_node->next;
    free(first_node);
}

void destroy_stack(void)
{
    while (stack != NULL)
        pop();
}

STACK_TYPE top()
{
    assert(!is_empty());
    return stack->value;
}

int main(void)
{
    struct STACK_NODE *ptr;

    push(10);
    push(20);
    push(30);
    push(40);

    for (ptr = stack; ptr != NULL; ptr = ptr->next)
        printf("%4d", ptr->value);
    printf("\n");

    printf(" pop=%d\n", top());
    pop();

    for (ptr = stack; ptr != NULL; ptr = ptr->next)
        printf("%4d", ptr->value);
    printf("\n");

    destroy_stack();
  exit(0);
}