【数据结构】栈(C++ )-摩杜云开发者社区

顺序存储结构实现栈
链接存储结构实现栈
实际应用

迷宫求解
表达式求值

栈

只能在一边进出，先进的后出。

进出的一端叫做栈顶，另一端叫做栈底。

栈可以使用顺序存储结构，也能使用链式存储结构。

注意：栈只能在一端进行操作，这是栈的关键特征，也就是说栈不允许在中间进行查找、插入、删除等操作，(但是在实际应用中我们可以打破它)。

这里掌握初始化、入栈、出栈、取栈顶元素操作即可。

顺序存储结构实现栈

#include<iostream>
using namespace std;

#define MAX_SIZE 128
typedef int DataType;

//栈的结构有多重方式定义，不用局限于这一种
/*
  例如:
    定义两个int型，并且直接开辟好数组空间
    定义一个指针，一个int top
*/
typedef struct _Stack
{
  DataType* top;  //栈顶指针
  DataType* base;//栈底指针
  //其实没有必要定义一个来标记元素的个数。
  //两个指针指向同一个数组，他们两个相减得到是中间元素的个数。
  //否则两个地址相减没有意义
}Stack;

//栈的初始化
bool initStack(Stack& S)
{
  //先用栈底指针来拿到这个刚开辟好空间的数组
  S.base = new int[MAX_SIZE];//指针来定位这个数组
  if (!S.base)
  {
    return false;
  }
   = S.base;
  return true;
}

//入栈
bool pushStack(Stack& S, DataType data)
{
  if (!S.base)
  {
    return false;
  }
  if ( - S.base == MAX_SIZE)
  {
    //栈满
    return false;
  }

  //栈中还有空位置
  *() = data;
  ++;
  return true;
}

//出栈-栈顶元素出栈
DataType popStack(Stack& S)
{
  //不为空
  if ( != S.base)
  {
    return *(--S .top);
  }
  else
  {
    return -1;
  }
}
//返回栈顶元素         
DataType getTop(Stack& S)
{
  if ( - S.base == 0)
  {
    return -1;
  }
  return *(-1);
}
int main(void)
{
  Stack S;
  initStack(S); 
  int n = 0;
  int m = 0;
  cin >> n;
  m = n;
  while (n)
  { 
    pushStack(S, n);
    n--;
  }
  cout << "____" << endl;
  cout << getTop(S) << endl;
  cout << "____" << endl;
  while (m)
  {
    cout << popStack(S) << endl;
    m--;
  }
  return  0;
}

入栈操作图示:

【数据结构】栈(C++ )

链接存储结构实现栈

#include<iostream>
using namespace std;

//数据类型
typedef int DataType;
//最大存储数量
#define  MAX_SZIE 128
//结点结构
typedef struct _Snode
{
  DataType data;
  struct _Snode* next;
}Snode;

//栈(头)结构
typedef struct _Stack
{
  int count;
  Snode* base;
  Snode* top;
}Stack;

//初始化
bool initStack(Stack* S)
{
  if (!S)
  {
    return false;
  }
  S->base = S->top = NULL;
  S->count = 0;
  return true;
}

//入栈
bool pushStack(Stack* S, Snode* node)
{
  if (!S || !node)
  {
    return false;
  }

  //第一次插入元素
  if (S->count == 0)
  {
    S->base = S->top = node;
    S->top->next = NULL;
    S->count++;
  }
  else
  {
    S->top->next = node;
    S->top = node;
    S->count++;
  }
  return false;
}
//出栈
bool popStack(Stack* S)
{
  if (!S || S->count == 0)
  {
    return false;
  }
  Snode* tempnode = S->base;

  while (tempnode->next != S->top && S->count != 1)
  {
    tempnode = tempnode->next;
  }
  if (S->count == 1)//如果栈中只剩下一个结点可以删除
  {
    S->base = NULL;
  }
  //现在tempnode是top的前一个结点
  delete S->top;
  S->top = tempnode;//如果是最后一个结点的话base和top都被置空了
  S->top->next = NULL;
  
  S->count--;
  return true;
}
//拿到栈顶元素
bool getTop(Stack* S,DataType* m_data)
{
  if (!S || S->count == 0)
  {
    return S;
  }
  *m_data = S->top->data;
  return false;
}
//判断栈是否为空
bool isEmpty(Stack* S)
{
  if (S->count == 0)
  {
    return true;
  }
  return false;
}
int main(void)
{
  Stack* S = new Stack;
  initStack(S);

  int n = 5;
  int m = n;
  while (n)
  {
    Snode* tempnode = new Snode;
    tempnode->data = n;
    pushStack(S, tempnode);
    n--;
  }

  while (m >0)
  { 
    m--;
  }

  cout << S->top->data << " ";
  popStack(S);

  cout << S->top->data << " ";
  popStack(S);

  cout << S->top->data << " ";
  popStack(S);
  
  cout << S->top->data << " ";
  popStack(S);

  cout << S->top->data << " ";
  popStack(S);

  if (!isEmpty(S))
  {
    cout << S->top->data << " ";
  }


  int temp = 0;
  getTop(S, &temp);
  cout << temp << endl;

  delete S;
  return  0; 
}

补充:要修改指针指向地址，可以传递二级指针。

一级指针修改值。

栈

顺序存储结构实现栈

链接存储结构实现栈

实际应用

迷宫求解

表达式求值