1、前言

栈在很多地方都有涉及，它也是作为一种最基本的数据结构而存在。它的特点是，越后进来的元素越先出去。即，我们对栈进行插入，删除操作，都是通过栈顶元素来操作的。栈其实在逻辑结构上就是线性表，但是它的运算却是受到限制的。在栈中，允许插入删除的一端叫做栈顶，还有另一个固定端作为栈底，如果栈中没有元素则叫做空栈。因为栈是后进先出的，并且是线性表的一种，所以栈也称为后进先出线性表。由于线性表按存储的物理结构来划分可以分为顺序表和链式表，所以，栈也可以分为顺序栈和链式栈。接下俩会讲解两种结果的实现

2、栈的基本运算

根据栈的数据结构特点，下面给出基本的运算。 ①、初始化栈，取名 init_stack ②、判断栈空，取名isEmpty_stack ③、入栈，取名push_stack ④、出栈，此方法会返回栈顶元素并将其从栈中去除，取名pop_stack ⑤、读取栈顶元素，此方法仅仅是读取栈顶元素，取名top_stack

3、顺序栈

顺序栈是一种物理上采取一段连续的存储空间来存储元素的栈。和顺序表一样，它也需要一个数组用于存放元素，并且需要一个指标用来指示栈顶元素。下面根据顺序栈的结构给出基本运算的实现。

4、 C语言实现基本运算

/* 顺序栈的基本运算的实现 */ #include <stdio.h> #include <stdlib.h> //设置元素容量 # define MAXSIZE 100 /* 定义栈的基本结构 */ typedef struct node { int data[MAXSIZE];//数据元素 int top;//栈顶位置 }stack; /* 声明基本运算 */ stack* init_stack(); int isEmpty_stack(stack * pStack); int push_stack(stack *pStack, int data); int top_stack(stack *pStack); int pop_stack(stack *pStack); int main(void) { stack *pStack = init_stack(); printf("将1-50压入栈中\n"); for (int i = 1; i <= 50; i++) { push_stack(pStack, i); } printf("读取栈顶元素：%d\n",top_stack(pStack)); //移除50 pop_stack(pStack); printf("移除50后读取栈顶元素：%d\n", top_stack(pStack)); system("pause"); return 0; } /* 初始化一个空栈 */ stack* init_stack() { //申请存储空间 stack *pStack = (stack *)malloc(sizeof(stack *)); //至栈顶标记为-1，表示空栈 pStack->top = -1; return pStack; } /* 判断是否栈空，返回1表示是，0表示false */ int isEmpty_stack(stack * pStack) { if (pStack->top == -1) { printf("栈空\n"); return 1; } else { return 0; } } /* 将数据插入栈顶，成功返回1，失败返回0 */ int push_stack(stack *pStack, int data) { int top = pStack->top; top++; if (top == (MAXSIZE - 1)) { printf("表满了\n"); return 0; } pStack->data[top] = data; pStack->top++; return 1; } /* 读取栈顶元素 */ int top_stack(stack *pStack) { if (isEmpty_stack(pStack)!=1) { return pStack->data[pStack->top]; } return -1; } /* 弹出栈顶元素 */ int pop_stack(stack *pStack) { if (isEmpty_stack(pStack) != -1) { int topData = pStack->data[pStack->top]; pStack->top--; return topData; } return -1; } 运算逻辑比较简单就不讲了，运行效果如下：

5、 C++的实现顺序栈的基本运算

Node.h #include <iostream> # define MAXSIZE 100 class Stack { public: Stack(); ~Stack(); int isEmpty_stack(Stack pStack); Stack push_stack(Stack pStack, int data); int top_stack(Stack pStack); int pop_stack(Stack *pStack); int data[MAXSIZE]; int top; private: }; Stack::Stack() { } Stack::~Stack() { } /* 初始化一个空栈 */ Stack init_stack() { //申请存储空间 Stack *pStack = new Stack(); //至栈顶标记为-1，表示空栈 pStack->top = -1; return *pStack; } /* 判断是否栈空，返回1表示是，0表示false */ int isEmpty_stack(Stack pStack) { if (pStack.top == -1) { std::cout << "栈空" << std::endl; return 1; } else { return 0; } } /* 将数据插入栈顶，成功返回1，失败返回0 */ Stack push_stack(Stack pStack, int data) { int top = pStack.top; top++; if (top == (MAXSIZE - 1)) { std::cout<<"表满了"<<std::endl; return pStack; } pStack.data[top] = data; pStack.top++; return pStack; } /* 读取栈顶元素 */ int top_stack(Stack pStack) { if (isEmpty_stack(pStack) != 1) { return pStack.data[pStack.top]; } return -1; } /* 弹出栈顶元素 */ int pop_stack(Stack *pStack) { if (isEmpty_stack(*pStack) != -1) { int topData = pStack->data[pStack->top]; pStack->top--; return topData; } return -1; } Main.cpp /* c++实现顺序栈的基本运算 */ #include <iostream> #include "Node.h" using namespace std; int main() { Stack pStack = init_stack(); cout<<"将1-50压入栈中"<<endl; for (int i = 1; i <= 50; i++) { pStack=push_stack(pStack, i); } cout<<"读取栈顶元素："<< top_stack(pStack)<<endl; //移除50 pop_stack(&pStack); cout<<"移除50后读取栈顶元素："<< top_stack(pStack)<<endl; system("pause"); return 0; } 运行结果：

6、java实现基本运算

SequenceStack.java /** * 顺序栈 * @author Myy * */ public class SequenceStack { private int data[]=new int [100]; private int top=-1; public int[] getData() { return data; } public void setData(int[] data) { this.data = data; } public int getTop() { return top; } public void setTop(int top) { this.top = top; } } SequenceStackUtils.java public class SequenceStackUtils { /* 判断是否栈空 */ public static boolean isEmpty_stack(SequenceStack pStack) { if (pStack.getTop() == -1) { System.out.println("栈空" ); return true; } else { return false; } } /* 将数据插入栈顶，成功返回1，失败返回0 */ public static SequenceStack push_stack(SequenceStack pStack, int data) { int top = pStack.getTop(); top++; if (top == 99) { System.out.println("表满了"); return pStack; } pStack.getData()[top] = data; pStack.setTop(pStack.getTop()+1); return pStack; } /* 读取栈顶元素 */ public static int top_stack(SequenceStack pStack) { if (!isEmpty_stack(pStack)) { return pStack.getData()[pStack.getTop()]; } return -1; } /* 弹出栈顶元素 */ public static int pop_stack(SequenceStack pStack) { if (!isEmpty_stack(pStack)) { int topData = pStack.getData()[pStack.getTop()]; pStack.setTop(pStack.getTop()-1); return topData; } return -1; } } Stack.java public class Stack { public static void main(String args[]) { SequenceStack pStack = new SequenceStack(); System.out.println("将1-50压入栈中"); for (int i = 1; i <= 50; i++) { pStack=SequenceStackUtils.push_stack(pStack, i); } System.out.println("读取栈顶元素："+SequenceStackUtils.top_stack(pStack)+""); //移除50 System.out.println("移除50后读取栈顶元素："); SequenceStackUtils.pop_stack(pStack); System.out.println(SequenceStackUtils.top_stack(pStack)+""); } } 运行结果：

7、链式栈

链式栈和顺序栈的区别在于，链式栈不要求用连续存储的一块空间去存储数据，因而为了知道栈中完整的元素，需要定义两个成员，一个是数据成语存放数据，另一个是指针成员，存放下一个元素的地址。链式表的结构，本身来说，首元素作为栈顶是最合适的，因此每次有新的元素加入，都把他作为首元素就ok了，即我们说的头节点。在实现操作中，就不需要记录栈顶的位置了，所以只要处理指针域的数据即可。关于链式表的具体实现和顺序表差不多的，这里不再讲述，有兴趣可以自己些例子。

---------文章写自：HyHarden---------

--------博客地址：http://blog.csdn.net/qq_25722767-----------