栈定义:

仅限在标为进行插入删除操作的线性表

栈顶为表尾,栈底为表头


栈的操作性质:

先入后出

  1. 操作序列问题:
  • 已知入栈序列与操作序列:
    入栈序列1,2,3,4
    操作序列PPQPQQPPQQ
    求出栈序列(直接模拟)

  • 已知入栈序列和出栈序列求操作序列:
    模拟

  • 已知入栈序列, 什么样的出栈序列是不可能的:
    求解方法\(1\):
    出栈序列看作\(1...n\)的一个排列, 设为\(p_{1}p_{2}...p_{n}\),若存在\(i < j < k\)使得:\(p_{j} < p_{k} < p_{i}\),该序列不合法

口诀:312

求解方法\(2\):
依次检查所给的出栈序列:\(p_{1} ... p_{n}\)
对于\(p_{1}\),对应入栈序列\(p_{1}\)之前都必须入栈...
直至推出矛盾


栈的实现

线性表

struct Stack{
	int *data;
	int bufferlen;
	int top;
}

初始化及撤销:

  1. 初始化\(top = 0\)表示为空栈, 这里\(top\)表示将要插入元素位置
int InitStack(Stack &S, int n)
{
	S.data = new int[n];
	S.bufferlen = n;
	S.top = 0;
	return 0;
}

int DestoryStack(Stack &S)
{
	delete []S.data;
	S.datas = nullptr;
	S.bufferlen = 0;
	S.top = 0;
	return 0;
}

链表实现

  1. 初始化:

PS:栈的链表实现不需要头结点

int Init(Stack &S)
{
	S = nullptr;
	return 0;
}

int Delete(Stack &S)
{
	while (!Is_empty(S))
		Pop(S);
	return 0;
}
  1. 判断是否为空
int Is_empty(Stack &S)
{
	if (S == nullptr)
		return 1;
	return 0;
}
  1. 入栈及出栈操作
int Push(Stack &S, int x)
{
	Stack p = new struct SNode;
	p -> data = x;
	p -> next = S;
	S = p;
	return 0;
}

int Pop(Stack &S)
{
	Stack p = S;
	S = S->next;
	delete p;
	return 0;
}

int Top(Stack &S)
{
	return S->data;
}

应用

栈的操作代码实现

栈的操作问题

进制转换

算法3-1:八进制数

括号匹配问题

问题 I: 括号匹配问题

表达式计算

  1. 算符优先顺序: \(*、/\) \(>\) \(+、-\)
  2. 括号优先顺序:先算括号内的,再算括号外的:
  • \((op\): \(op\)优先级高
  • \(op(\): \((\)优先级高
  • \()op\): \()\)优先级高
  • \(op)\): \(op\)优先级高

\(()\)相遇,括号内运算结束

  1. 从左到右运算

推荐这些文章:

Stack栈的基本功能数组实现

鉴于STL的栈有或多或少的功能缺失,于是我们就来手写一个栈。
以下是代码,功能有待完善。

1 //栈的简单操作 数组实现
2 int s[100001]; //创建栈
3 int top = 0; //创建头指针,一开始在底部
4
5 void Push(int x){
6 s[++top] = x; //先移动top 再赋值
7 }
8
9 void Pop(){
10 if (top == 0){
11 return;
12 }
13 else{
1...

C语言 简单线栈

#include<stdio.h>
int push(int*a, int top, int x){ a[top]=x;
top++;
return top;}//进栈
 
int pop(int *a,int top){
top--;
return top;}//出栈
int main()
{
int top=0;
top=push(    )//in
top=pop(  )//out
int a[1005]={0};
return 0;}
 

...

Leetcode:剑指 Offer 06. 从尾到头打印链表

while比for的效率更低
class Solution {
public int[] reversePrint(ListNode head) {
Stack<Integer> stack=new Stack<Integer>();
if(head==null){
return new int[0];
}
int count=0;
while(head!=null){
stack.push(head.val);
...

[LeetCode] 225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top o...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.size();
int m=mat[0].size();
vector<vector<int>> ans(n, vector<int>...

32. 最长有效括号

自己使用堆栈没有成功,主要原因是很久没有敲代码,再加上没有演算整个过程,凭空想象,非常的不好
贴自己没成功的代码吧
class Solution {
public:
int longestValidParentheses(string s) {
stack<string>temp;
int number=0;
int number_temp=0;
int length = s.size();
if(length == 0){
return 0;
}
...

括号匹配(栈)

 
二、思路
如果当前元素为[或者(则入栈,如果当前元素为]或者)则判断当前元素与栈顶元素是否匹配,如果匹配则出栈,如果不匹配则输出No。在最后应判断栈是否为空,若为空则整个匹配,若不为空则整个不匹配
三、代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxsize 100
using namespace std;

typedef struct {
char data[maxsize];//元素
...

[ UVa 12096 详解] The Set Stack Computer 集合栈计算机 | map、set、vector、stack、宏函数等知识点简单应用

题目
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且支持以下操作:

PUSH:空集“{}”入栈

DUP:把当前栈顶元素复制一份后再入栈

UNION:出栈两个集合,然后把两者的并集入栈

INTERSECT:出栈两个集合,然后把二者的交集入栈

ADD:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈

每次操作后,输出栈顶集合的大小(即元素个数)。
例如栈顶元素是A={ {}, {{}} }, 下一个元素是B={ {}, {{{}}} },
则:
UNION 操作将得到{ {}, {{}}, {{{}}} },输出 3
INT...

【模拟 + 栈】AcWing 151. 表达式计算4

这题括号多余的情况好恶心 orz,以及负数的情况也增加了这题的难度。
分析
首先,解决一般的中缀表达式转后缀表达式问题:

这里的运算符包括 +,-,*,/,^,当然,扩大运算符包含的集合的时候我们也可以类似推广。

考虑用一个答案栈 res 以及运算符栈 ops 来操作。

遇到数字的时候,将它丢入 res。
遇到左括号的时候,将它丢入 ops。
遇到右括号的时候,开始对 ops 执行出栈操作直到遇到左括号。
遇到运算符的时候,只要 ops 栈顶的运算符优先级高于当前运算符,就一直对 ops 执行出栈操作。

这样我们就可以将中缀转后缀了。
下面对后缀表达式求值:
考虑用一个栈维护,
遍历...

L2-033 简单计算器

#include <bits/stdc++.h>

using namespace std;

int cal(int a, int b, char c) {
int t;
if (c == '/' && b == 0) t = -1;
else if (c == '+') t = a + b;
else if (c == '-') t = a - b;
else if (c == '*') t = a * b;
else if (c == '/') t = a / b;
return t;
}

int m...

文章标题:栈
文章链接:https://www.dianjilingqu.com/4107.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>