栈的实现——链表和数组

数据结构

C语言（打印函数采用的c++）：
栈的链表实现—— 栈的初始化（创建||清空）、入栈、出栈（获取栈顶元素）
栈的数组实现——初始化、入栈、出栈、清空栈
参考资料：《数据结构与算法分析——C语言描述》 P46

一. 栈的链表实现

StackLinkList.cpp

/* 
功能：栈的链表实现: 栈的初始化（创建||清空）、入栈、出栈（获取栈顶元素） 
Date: 2015/01/23 
Author : quinn 
*/  
#include <iostream>  
#include <stdlib.h>  
using namespace std;  
typedef int Item;  
typedef struct Node Node;  
typedef Node* Stack;  
struct Node  
{  
    Item item;  
    Node* next;  
};  
void StackPop(Stack s);  
Stack StackInit(Stack s) //创建或清空（初始化）  
{  
    if (s == NULL) //创建  
    {  
        s = (Stack)malloc(sizeof(*s));  
        s->next = NULL;  
    }  
    else //清空  
        while(s->next != NULL)  
            StackPop(s);  
    cout << "初始化成功！" <<endl;  
    return s;  
}  
void StackPush(Stack s, Item item) //入栈  
{  
    Node* tmpNode = (Node*)malloc(sizeof(*tmpNode));  
    tmpNode->item = item;  
    tmpNode->next = s->next;  
    s->next = tmpNode;  
    cout << "PUSH: " << item <<endl;  
}  
Item StackPopAndTop(Stack s) //出栈并返回栈顶元素值  
{  
    if (s->next == NULL)  
    {  
        cout << "空栈，POPAndTop失败" <<endl;  
        return -1; //返回-1作警告  
    }  
    else  
    {  
        Node* firstNode = s->next;  
        s->next = s->next->next;  
        return firstNode->item;  
    }  
}  
void StackPop(Stack s) //出栈  
{  
    if (s->next == NULL)  
    {  
        cout << "空栈，POP失败" <<endl;  
    }  
    else  
    {  
        Node* firstNode = s->next;  
        s->next = s->next->next;  
        free(firstNode);  
    }  
}  
Item StackTop(Stack s) //仅获取栈顶元素  
{  
    if (s->next == NULL)  
    {  
        cout << "空栈，获取栈顶元素失败" <<endl;  
    }  
    return (s->next)->item;  
}  
int main()  
{  
    Stack s = NULL;  
    s = StackInit(s);  
    for(int i = 0; i < 10; i++)  
        StackPush(s, i);  
    for(int i = 0; i < 5; i++)  
        cout << StackPopAndTop(s) <<endl;  
    StackInit(s);  
    cout << StackPopAndTop(s) <<endl;  
    system("pause");  
    return 0;  
} 

运行结果：

二. 栈的数组实现

StackArray.cpp

/* 
功能：栈的数组实现——初始化、入栈、出栈、清空栈 
注： 定义栈为空时，栈顶index为 -1；栈满时，栈顶index为栈的长度-1 
Date：2015/01/23 
Author ： quinn 
*/  
#include <iostream>  
#include "item.h"  
#define STACK_SIZE 10 //认为设定栈的长度为10  
#define FULL_STACK (STACK_SIZE - 1)  
#define EMPTY_STACK (-1)  
using namespace std;  
typedef struct stack stack;  
typedef int Item;  
struct stack  
{  
    Item *stackItem;  
    int stackTop;  
};  
void Error(const char* str) //异常时输出提示  
{  
    cout << "Error: " << str << endl;  
}  
int IsFull(stack* s) //判断是否栈满  
{  
    if (s->stackTop == FULL_STACK)  
        return 1;  
    else  
        return 0;  
}  
int IsEmpty(stack* s) //判断是否空栈  
{  
    if (s->stackTop == EMPTY_STACK)  
        return 1;  
    else  
        return 0;  
}  
stack* StackInit( stack* s, int maxN) //初始化栈空间  
{  
     s->stackTop = -1; //空栈初始化 Top = -1  
     s->stackItem = (Item*)malloc(maxN * sizeof(Item)); //分配栈空间  
     return s;  
}  
void StackMakeEmpty(stack* s) //清空栈  
{  
    if (!IsEmpty(s))  
        s->stackTop = EMPTY_STACK;  
}  
void StackPush(stack* s, Item item) //入栈  
{  
    if (!IsFull(s))  
    {  
        s->stackItem[++(s->stackTop)] = item;  
        cout << "PUSH: " << item <<endl;  
    }  
    else  
        Error("栈已满，push失败");  
}  
Item StackPop(stack *s) //出栈  
{  
    if (!IsEmpty(s))  
    {  
        return s->stackItem[(s->stackTop)--];  
    }  
    else  
        Error("空栈，pop失败");  
}  
int main()  
{  
    stack *s = (stack*)malloc(sizeof(*s));  
    StackInit(s, STACK_SIZE);  
    for (int i = 0; i < 11; i++)  
    {  
        StackPush(s, i);  
    }  
    cout << "POP: " << StackPop(s) << endl;  
    cout << "POP: " << StackPop(s) << endl;  
    StackPush(s, 20);  
    cout << "POP: " << StackPop(s) << endl;  
    StackMakeEmpty(s);  
    StackPop(s);  
    StackPush(s, 30);  
    cout << "POP: " << StackPop(s) << endl;  
    system("pause");  
    return 0;  
} 

运行结果：