大发快三_快三最新网址_大发快三最新网址 - 由大发快三,快三最新网址,大发快三最新网址社主办的《大发快三,快三最新网址,大发快三最新网址》是我国消费领域中一张全国性、全方位、大容量的综合性日报。其立足消费网投领域,依托轻工行业,面向城乡市场,最先发布相关的专业权威资讯。

纸上谈兵: 栈 (stack)

  • 时间:
  • 浏览:1

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

栈(stack)是简单的数据形态学 ,但在计算机中使用广泛。它是有序的元素集合。栈最显著的形态学 是LIFO (Last In, First Out, 后进先出)。当当我们都当当我们 往箱子里存放一叠书时,先存放的书在箱子下面,当当我们当当我们 时需将后存放的书取出来,才能就看和拿下早先存放的书。

栈中的每个元素称为有两个 frame。而最上层元素称为top frame。栈只支持有两个 操作, pop, top, push。

pop取出栈中最上层元素(8),栈的最上层元素变为早先进入的元素(9)。

top查看栈的最上层元素(8)。

push将有两个 新的元素(5)放到栈的最上层。

栈不支持某些操作。但会 想取出元素12, 时需进行3次pop操作。

栈以及pop, push, top操作

栈最经典的计算机应用是函数调用。每个系统系统进程后该有有两个 栈,每个frame中记录了调用函数的参数,自动变量和返回地址。当该函数调用有两个 新的函数时,栈中会 push有两个 frame。当函数执行完毕返回时,该frame会pop,从而进入调用该函数的原函数,继续执行。完整篇 请参阅Linux从系统系统进程到系统系统进程

实际使用的栈从不一定符合数据形态学 的栈。比如说,有的语言允许被调用函数查看非top frame的记录。另有两个 的栈更相似于下面的经典游戏

 

栈的C实现 (基于表)

但会 栈是限定了操作的有序的元素集合,也不有当当我们当当我们 既都时需在数组的基础上来实现栈,也都时需在表的基础上来实现栈。但会 使用数组来实现栈,当当我们当当我们 时需预留充裕的空间供栈使用,并时需有两个 下标来记录最上层元素的位置。

当当我们当当我们 这里使用单向链表来实现栈。当当我们当当我们 都时需利用介绍表(list)的文章中但会 定义的操作来实现有两个 操作,但这里相对独立的重写了代码。

/* By Vamei */
/* use single-linked list to implement stack */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

// point to the  head node of the list
typedef struct node *STACK;
 
struct node {
    ElementTP element;
    position next;
};

STACK init_stack(void);
void delete_stack(STACK);
ElementTP top(STACK);
void push(STACK, ElementTP);
ElementTP pop(STACK);
int is_null(STACK);

void main(void)
{
    ElementTP a;
    int i;
    STACK sk;
    sk = init_stack();
    push(sk, 1);
    push(sk, 2);
    push(sk, 8);
    printf("Stack is null? %d\n", is_null(sk));
    for (i=0; i<3; i++) {
        a = pop(sk);
        printf("pop: %d\n", a);
    }

    printf("Stack is null? %d\n", is_null(sk));    
    delete_stack(sk);
}

/*
 * initiate the stack
 * malloc the head node.
 * Head node doesn't store valid data
 * head->next is the top node
 */
STACK init_stack(void)
{
    position np;
    STACK    sk;
    np = (position) malloc(sizeof(struct node));
    np->next     = NULL;  // sk->next is the top node
    sk = np; 
    return sk;
}

/* pop out all elements 
 * and then delete head node
 */
void delete_stack(STACK sk)
{
    while(!is_null(sk)) {
        pop(sk);
    }
    free(sk);
}
/* 
 * View the top frame
 */
ElementTP top(STACK sk)
{
    return (sk->next->element);
}

/*
 * push a value into the stack
 */
void push(STACK sk, ElementTP value) 
{
    position np, oldTop;
    oldTop = sk->next;    

    np = (position) malloc(sizeof(struct node));
    np->element  = value;
    np->next     = sk->next;

    sk->next     = np; 
}

/* 
 * pop out the top value
 */
ElementTP pop(STACK sk)
{
    ElementTP element;
    position top, newTop;
    if (is_null(sk)) {
        printf("pop() on an empty stack");
        exit(1);
    } 
    else {
        top      = sk->next;
        element  = top->element;     
        newTop   = top->next;
        sk->next     = newTop;
        free(top);
        return element;
    } 
}

/* check whether a stack is empty*/
int is_null(STACK sk)
{
    return (sk->next == NULL);
}

输出结果:

Stack is null? 0

pop: 8pop: 2pop: 1Stack is null? 1

总结

栈, LIFO

pop, push, top

欢迎继续阅读“纸上谈兵: 算法与数据形态学 ”系列。

Update:

我以后是用双向循环链表实现的栈,以后发现另有两个 这么 必要。它只能给栈带来额外的好处,后该增加所需的内存空间。