- 栈的定义--Stack
栈是只允许在末端进行插入和删除的线性表。栈具有后进先出的特性(LIFO ,Last In Fast Out)。
学过数据结构的人都知道：栈可以用两种方式来实现，一种方法是用数组实现栈，这种栈成为静态栈；另外一种方法是用链表实现栈，这种栈叫做动态栈。
- 栈提供如下操作
s.empty() 如果栈为空返回true，否则返回false
s.size() 返回栈中元素的个数
s.pop() 删除栈顶元素但不返回其值
s.top() 返回栈顶的元素，但不删除该元素
s.push() 在栈顶压入新元素
- 栈的实现
下面是用C++实现的一个栈结构的源码(顺序表)
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<typename T>
class Stack
{
public:
Stack()
:array(NULL)
, size()
, capacity()
{}
~Stack()
{
if (array != NULL)
{
delete[] array;
}
capacity = ;
size = ;
}
Stack(const Stack<T>& s)
{
array = new T[s.size];
memcpy(array, s.array, sizeof(T)*s.size);
size =s.size;
capacity = s.capacity;
}
Stack<T>& operator=( const Stack<T>& s)
{
capacity = s.capacity;
size = s.size;
this->array =s.array;
return *this;
}
void Print()
{
for (int index = ; index < size; index++)
{
cout << array[index] << " ";
}
cout << endl;
}
void Push(const T& x)
{
_CheckCapacity(); array[size++] = x;
} void Pop()
{
assert(size > );
--size;
} size_t Size()
{
return size;
} bool Empty()
{
return size == ;
} const T& Top()
{
assert(size > ); return array[size - ];
}
protected:
void _CheckCapacity()
{
if (size >= capacity)
{
T *temp = new T[capacity * + ];
for (int index = ; index < size; index++)
{
temp[index] =array[index];
}
delete[] array;
array = temp;
capacity = capacity * + ;
} } protected:
T * array;
size_t size;
size_t capacity;
};
void fun()
{
Stack<int> s;
s.Push();
s.Push();
s.Push();
s.Push();
s.Print();
cout << s.Top() << " ";
s.Pop();
}
void main()
{
fun();
system("pause");
}
- 栈的应用
1.算术表达式求值。波兰表达式（后缀表达式）
实现:
#include <iostream>
#include <assert.h>
#include"stack"
using namespace std; enum Type
{
OP_NUM,
OP_SYMBOL
}; enum OP_SMB
{
ADD,
SUB,
MUL,
DIV,
}; struct Cell
{
Type _type;
int _value;
}; Cell RNPArray[] =
{
{ OP_NUM, },
{ OP_NUM, },
{ OP_NUM, },
{ OP_SYMBOL, ADD },
{ OP_SYMBOL, MUL },
{ OP_NUM, },
{ OP_SYMBOL, SUB },
{ OP_NUM, },
{ OP_NUM, },
{ OP_SYMBOL, DIV },
{ OP_SYMBOL, ADD },
}; int CountRNP(Cell* a, size_t size)
{
stack<int> s;
for (int i = ; i < size; ++i)
{
if (a[i]._type == OP_NUM)
{
s.push(a[i]._value);
}
else if (a[i]._type == OP_SYMBOL)
{
int right = s.top();
s.pop();
int left = s.top();
s.pop(); switch (a[i]._value)
{
case ADD:
s.push(left + right);
break;
case SUB:
s.push(left - right);
break;
case MUL:
s.push(left * right);
break;
case DIV:
s.push(left / right);
break;
}
}
}
return s.top();
}
void test()
{ int ret=CountRNP(RNPArray, sizeof(RNPArray) / sizeof(RNPArray[]));
cout << ret;
}
int main()
{
test();
return ;
}
2.迷宫问题
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;
//从文件获取初始迷宫地图
void GetMazeMap(int *maze, int rows, int cols)
{
assert(maze);
FILE *fOut = fopen("MazeMap.txt", "r");
assert(fOut);
for (int i = ; i < rows; i++)
{
for (int j = ; j < cols;)
{
char ch = fgetc(fOut);
if (ch == '' || ch == '')
{
maze[i*cols + j] = ch - '';
j++;
}
}
}
fclose(fOut);
}
//打印迷宫地图
void PrintMazeMap(int*maze, int rows, int cols)
{
assert(maze);
for (int i = ; i < rows; i++)
{
for (int j = ; j < cols; j++)
{
cout << maze[i*cols + j] << " ";
}
cout << endl;
}
cout << endl;
}
struct Point
{
size_t row;
size_t col;
};
//检查该点是否为可通行
bool CheckIsAccess(int *maze, int rows, int cols,Point cur)
{
assert(maze);
if (cur.row < rows&&cur.col < cols&& (maze[cur.row*cols + cur.col] == ))
{
return true;
}
return false;
}
//获取走出迷宫路径
stack<Point> GetMazePath(int* maze, int rows, int cols, Point entry)
{
assert(maze);
stack<Point> path;
Point cur = entry;
path.push(entry);
maze[cur.row*cols + cur.col] = ; while (!path.empty())
{
Point cur = path.top();
Point next = cur;
if (next.row ==rows-)
{
return path;
}
//试探 上
next = cur;
next.row--;
if (CheckIsAccess(maze, , , next))
{
path.push(next);
maze[next.row*cols + next.col] = ;
continue;
}
//下
next = cur;
next.row++;
if (CheckIsAccess(maze, , , next))
{
path.push(next);
maze[next.row*cols + next.col] = ;
continue;
}
//左
next = cur;
next.col--;
if (CheckIsAccess(maze, , , next))
{
path.push(next);
maze[next.row*cols + next.col] = ;
continue;
}
//右
next = cur;
next.col++;
if (CheckIsAccess(maze, , , next))
{
path.push(next);
maze[next.row*cols + next.col] = ;
continue;
}
}
cout << "Not have exit" << endl;
return path;
}
void TestMaze()
{
int maze[][] = {}; GetMazeMap((int *)maze, , );
PrintMazeMap((int*)maze, , );
Point entry = { , };
GetMazePath((int*)maze, , , entry);
PrintMazeMap((int*)maze, , );
}
int main()
{
TestMaze();
//system("pause");
getchar();
return ;
}