栈

称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象资料型别，其特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。
由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作

栈的基本特点

• 先入后出，后入先出。
• 除头尾节点之外，每个元素有一个前驱，一个后继。

  顺序栈C++实现

  MyStack.h

  #ifndef STACK_MYSTACK_H
  #define STACK_MYSTACK_H
  
  class MyStack
  {
  public:
      explicit MyStack(int size);             //初始化栈
      void Destroy_MyStack();                 //清除栈
      bool Stack_Empty();                     //判空
      bool Stack_Full();                      //判满
      void Clear_Stack();                     //清空栈
      int Stack_Length();                     //返回长度
      bool Push(int elem);                    //push
      bool Pop(int &elem);                    //pop
      void Stack_Traverse(bool Button);       //遍历栈
      int Get_Top(int &elem);                 //获取栈顶元素
  
  private:
      int *m_pBuffer;
      int m_Size;
      int m_Top;
  };
  
  #endif //STACK_MYSTACK_H

MyStack.cpp

#include "MyStack.h"
#include <iostream>
using namespace std;

MyStack::MyStack(int size) {
    m_Size = size;
    m_pBuffer = new int[m_Size];
    m_Top = 0;
}

void MyStack::Destroy_MyStack() {
    delete []m_pBuffer;
}

bool MyStack::Stack_Empty() {
    return !m_Top;
}

bool MyStack::Stack_Full() {
    return (m_Top == m_Size) != 0;
    // return (m_Top == m_Size) ? true : false;
}

void MyStack::Clear_Stack() {
    m_Top = 0;
}

int MyStack::Stack_Length() {
    return m_Top;
}

bool MyStack::Push(int elem) {
    if(Stack_Full()){
        return false;
    }
    else{
        m_pBuffer[m_Top] = elem;
        m_Top++;
        return true;
    }
}

bool MyStack::Pop(int &elem) {
    if(Stack_Empty()){
        return false;
    }
    else{
        m_Top--;
        elem = m_pBuffer[m_Top];
        return true;
    }
}

void MyStack::Stack_Traverse(bool Button) {
    if(Button)
    {
        for (int i= 0; i < m_Top; i++) {
            cout << m_pBuffer[i] << endl;
        }
    }
    else
    {
        for (int i = m_Top-1; i >=0 ; i--) {
            cout << m_pBuffer[i] << endl;
        }
    }

}

int MyStack::Get_Top(int &elem) {
    elem = m_pBuffer[m_Top-1];
    return elem;
}

main.cpp

#include <iostream>
#include "MyStack.h"
using namespace std;
#define B 2
#define O 8
#define H 16

int main() {

    // 初始化操作
    auto *pStack = new MyStack(3);

    //栈判空
    if(pStack->Stack_Empty()){
        cout << "栈空" << endl;
    }

    // 入栈
    pStack->Push(1);
    pStack->Push(2);
    pStack->Push(3);

    //遍历栈
    pStack->Stack_Traverse(false);

    //栈判满
    if(pStack->Stack_Full()){
        cout << "栈满" << endl;
    }



    // 取栈顶元素
    int top = 0;
    cout << "栈顶元素: " << pStack->Get_Top(top) << endl;

    //出栈
    int elem = 0;
    pStack->Pop(elem);
    pStack->Stack_Traverse(false);

    // 取栈顶元素
    cout << "栈顶元素: " << pStack->Get_Top(top) << endl;

    //栈判空
    if(pStack->Stack_Empty()){
        cout << "栈空" << endl;
    }
    return 0;
}

Output

栈空
3
2
1
栈满
栈顶元素: 3
2
1
栈顶元素: 2

栈的应用

进制转换 10->2

#include <iostream>
#include "MyStack.h"
using namespace std;
#define B 2
#define O 8
#define H 16

int main() {
    auto *pStack = new MyStack(32);

    // 转换的数N
    int N = 2017;
    int mod = 0;

    // 短除法
    while (N !=0){
        mod = N % B;
        pStack->Push(mod);
        N = N / B;
    }

    int elem = 0;
    cout << pStack->Get_Top(elem) << endl;
    pStack->Stack_Traverse(false);

    return 0;
}

Output

1
1
1
1
1
1
1
0
0
0
0
1

源码文件

zip